Last Updated on March 10, 2022 by Ria Pathak

### 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**:

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

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`

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`

The idea is to 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).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`

.Calculate

`mid = (low + high)/2`

, say`mid`

is our desired day.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`

.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))`

.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)`

[forminator_quiz id="1111"]