# Magical Ropes Binary Search

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 1018 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`

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

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

[forminator_quiz id="1111"]