CONCEPTS USED:

Binary Search

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given an array H of lengths of Magical Ropes and array R of the rate by which rope increases daily, print the minimum number of days required to collect ropes that sum up to length X

Restrictions:

  1. You cannot cut the rope, you have to take complete rope for collecting it.

  2. You cannot take a rope with length less than K.

See original problem statement here

For Example:

Input : N = 4, X = 100, K = 45
        Heights[] = [2, 5, 2, 6]
           Rate[] = [10, 13, 15, 12]
Output : 4

Explanation :

Day 0 = [2, 5, 2, 6]

Day 1 = [2 + 10, 5 + 13, 2 + 15, 6 + 12]         = [12, 18, 17, 18]

Day 2 = [12 + 10, 18 + 13, 17 + 15, 18 + 12]     = [22, 31, 32, 30]

Day 3 = [22 + 10, 31 + 13, 32 + 15, 30 + 12]     = [32, 44, 47, 42]

Day 4 = [32 + 10, 44 + 13, 47 + 15, 42 + 12]     = [42, 57, 62, 54]

Ans : Day 4 as (57, 62, 54 are all greater than 45 and sum up to value that is greater than equal to 100)

Can we use Binary Search here ?

We need to find the minimum days required to collect ropes that sum up to length X. The required day can be any day between 0 to 10^18. We can use Binary Search by referring the best online course for data structures and algorithms for finding the right day efficiently in Logarithmic Time Complexity.

SOLVING APPROACH:

NOTE: As the length of rope is increasing by a given pace so we can calculate its length at any particular day by :-

Lenght at ith day = ith day * Rate of Growth + Initial length

  1. The idea is to go through the best online programming courses and perform a Binary Search such that whenever we find a day in which ropes length sum up to X, we will save it and search for a even lower value (as Minimum days are needed).

  2. initialize low as 0 and high as 10^{18}, by this we understand that minimum days can be as low as value of low and as high as value of high.

  3. Calculate mid = (low + high)/2, say mid is our desired day.

  4. Now, Linearly traverse and check for all ropes if their length at mid day is greater than or equal to K, if Yes add its value to a variable Sum.

  5. After traversal if Sum becomes greater or equal to X, simply save it, and check for a even lower value in the left half i.e. (low - (mid - 1)).

  6. Else, search in the right half i.e. ((mid + 1) - high).

SOLUTIONS:


#include <stdio.h>
#define ll long long

int main()
{
  ll N, X, K; scanf("%lld %lld %lld", &N, &X, &K);
  ll height[N], rate[N];

  //input heights of ropes
  for(ll i=0; i<N; i++)
    scanf("%lld", &height[i]);

  //input rate of growth of ropes
  for(ll i=0; i<N; i++)
    scanf("%lld", &rate[i]);

  //initialize minimum and maximum days that can be possible as low and high
  ll low = 0;
  ll high = 1000000000000000000;
  ll min_days = 0;

  //Check for a mid value if it is satisfying the conditions
  while(low <= high){
    ll mid = (low + high)/2;
    ll sum = 0, flag = 0;
    for(ll i=0 ;i<N; i++){
      if(K <= (mid*rate[i] + height[i])){
        sum += (mid*rate[i] + height[i]);
        if(sum >= X){
          flag = 1;
          break;
        }
      }
    }

    /* if mid is one of the possible day, save it and 
    keep on checking for more lower values in the left half */
    if(flag == 1){
      min_days = mid;
      high = mid - 1;
    }
    /* if mid is not a possible day skip it and 
      go on searching in the right half */ 
    else
      low = mid + 1;
  }
  printf("%lld", min_days);

  return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
  ll N, X, K; cin>>N>>X>>K;
  ll height[N], rate[N];

  //input heights of ropes
  for(ll i=0; i<N; i++)
    cin>>height[i];

  //input rate of growth of ropes
  for(ll i=0; i<N; i++)
    cin>>rate[i];

  //initialize minimum and maximum days that can be possible as low and high
  ll low = 0;
  ll high = 1000000000000000000;
  ll min_days = 0;

  //Check for a mid value if it is satisfying the conditions
  while(low <= high){
    ll mid = (low + high)/2;
    ll sum = 0, flag = 0;
    for(ll i=0 ;i<N; i++){
      if(K <= (mid*rate[i] + height[i])){
        sum += (mid*rate[i] + height[i]);
        if(sum >= X){
          flag = 1;
          break;
        }
      }
    }

    /* if mid is one of the possible day, save it and 
    keep on checking for more lower values in the left half */
    if(flag == 1){
      min_days = mid;
      high = mid - 1;
    }
    /* if mid is not a possible day skip it and 
      go on searching in the right half */ 
    else
      low = mid + 1;
  }
  cout<<min_days;

  return 0;
}

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
    public static void main(String args[]){

      Scanner sc = new Scanner(System.in);
      long N = sc.nextLong();
      long X = sc.nextLong();
      long K = sc.nextLong();

      long height[] = new long[(int)N];
      long rate[] = new long[(int)N];

      //input heights of ropes
      for(int i=0; i<N; i++)
        height[i] = sc.nextLong();

      //input rate of growth of ropes
      for(int i=0; i<N; i++)
        rate[i] = sc.nextLong();

      //initialize minimum and maximum days that can be possible as low and high
      long low = 0;
      long high = 1000000000000000000L;
      long min_days = 0;

      //Check for a mid value if it is satisfying the conditions
      while(low <= high){
        long mid = (low + high)/2;
        long sum = 0, flag = 0;
        for(int i=0 ;i<N; i++){
          if(K <= (mid*rate[i] + height[i])){
            sum += (mid*rate[i] + height[i]);
            if(sum >= X){
              flag = 1;
              break;
            }
          }
        }

        /* if mid is one of the possible day, save it and 
        keep on checking for more lower values in the left half */
        if(flag == 1){
          min_days = mid;
          high = mid - 1;
        }
        /* if mid is not a possible day skip it and 
          go on searching in the right half */ 
        else
          low = mid + 1;
      }
      System.out.print(min_days);  
  }
}

Space Complexity: O(1)

Previous post Floor of a number
Next post Maximize The Boxes

Leave a Reply

Your email address will not be published. Required fields are marked *