Number of steps | Practice problem hackerearth Solution

 Problem:-

You are given two arrays $a_1,a_2,\dots ,a_n$ and $b_1,b_2,\dots ,b_n$. In each step, you can set $a_i=a_i-b_i$ if $a_i\ge b_i$. Determine the minimum number of steps that are required to make all $a$'s equal.

Input format

• First line: $n$ 
• Second line: $a_1,a_2,\dots ,a_n$
• Third line: $b_1,b_2,\dots ,b_n$

Output format

Print the minimum number of steps that are required to make all $a$'s equal. If it is not possible, then print -1.

Constraints

$1\le n,a_i,b_i\le 5000$

Sample input

2
5 6
4 3

Sample output

-1

Sample Input

5
5 7 10 5 15
2 2 1 3 5

Sample Output

8

Time Limit: 1

Memory Limit: 256

Source Limit:

Code:-

  Here I am going to give you two solution first by using C language and second by using c++ language . You can submit the second solution in the c++ , c++14 and c++17 also.

So let's go for the code.

C++ (Code):-

 This solution you can submit in the c++ ,c++14 and c++17 . it is acceptable in all these languages.

#include<bits/stdc++.h>

using namespace std;

int main()

{

  int n,k,steps=0;

  cin>>n;

  int i,a[n],b[n];

  for(i=0;i<n;i++)

    cin>>a[i];

  for(i=0;i<n;i++)

    cin>>b[i];

  for(i=0;i<n-1;i++)

  {

    if(a[i]<a[i+1])

    {

      k=a[i];

      a[i]=a[i+1];

      a[i+1]=k;

      k=b[i];

      b[i]=b[i+1];

      b[i+1]=k;

    }

  }

  for(i=0;i<n-1;i++)

  {

    while(a[n-1]!=a[i])

    {

      if(a[i]<=0)

      {

        cout<<"-1"<<endl;;

        exit(0);

      }

      if(a[n-1]<a[i])

      {

        a[i]=a[i]-b[i];

        steps++;

     }

      if(a[n-1]>a[i])

      {

       a[n-1]=a[n-1]-b[n-1];

        steps++;

      }

    }

  }

  cout<<steps;

  return 0;

}

C (Code):-

#include<stdio.h>

int main()

{

    int n,k,steps=0;

    scanf("%d",&n);

    int i,a[n],b[n];

    for(i=0;i<n;i++)

        scanf("%d",&a[i]);

    for(i=0;i<n;i++)

        scanf("%d",&b[i]);

    for(i=0;i<n-1;i++)

    {

        if(a[i]<a[i+1])

        {

            k=a[i];

            a[i]=a[i+1];

            a[i+1]=k;

            k=b[i];

            b[i]=b[i+1];

            b[i+1]=k;

        }

    }

    for(i=0;i<n-1;i++)

    {

        while(a[n-1]!=a[i])

        {

            if(a[i]<=0)

            {

                printf("-1");

                exit(0);

            }

            if(a[n-1]<a[i])

            {

                a[i]=a[i]-b[i];

                steps++;

         }

            if(a[n-1]>a[i])

            {

               a[n-1]=a[n-1]-b[n-1];

                steps++;

            }

        }

    }

   printf("%d",steps);

    return 0;

}

recommended post:-

• Very Cool numbers | Hacker earth solution
• Birthday party | Hacker earth solution
• Most frequent | hacker earth problem solution
• program to find symetric difference of two sets
•  cost of balloons | Hacker earth problem solution
• Chacha o chacha | hacker earth problem solution
• jadu and dna | hacker earth solution
• Bricks game | hacker earth problem
• Anti-Palindrome strings | hacker earth solution
• connected components in the graph | hacker earth data structure
• odd one out || hacker earth problem solution
•   Program to find cycle in the graph
• Implementation of singly link list
• Implementation of queue by using link list
• Algorithm of quick sort
• stack by using link list
• program to find preorder post order and inorder of the binary search tree
• How to set limit in the floating value in python
  
• What is boolean data type
• How to print any character without using format specifier