Header Ads Widget

Number of steps | Practice problem hackerearth Solution

Rajnish Tripathi 15:27

 Problem:-

You are given two arrays a1,a2,…,an and b1,b2,…,bn. In each step, you can set ai=ai−bi if ai≥bi. Determine the minimum number of steps that are required to make all a's equal.

Input format

  • First line: n 
  • Second line: a1,a2,…,an
  • Third line: b1,b2,…,bn

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≤n, ai, bi≤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:-



Tags:

Post a Comment

3 Comments

  1. Anonymous18:42

    Thanks Bro

    ReplyDelete
  2. Anonymous20:43

    I tried your mentioned C++ code, but it is not working. Some garbage value is being printed.

    ReplyDelete