Last Updated on March 10, 2022 by Ria Pathak
CONCEPTS USED:
Binary Search
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
Given an array
Hof lengths ofMagicalRopes and arrayRof the rate by which rope increases daily, print the minimum number of days required to collect ropes that sum up to lengthX
Restrictions:
You cannot cut the rope, you have to take complete rope for collecting it.
You cannot take a rope with
lengthless thanK.
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 between0to 1018 We can useBinary Searchfor finding the right day efficiently inLogarithmic 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 Searchsuch that whenever we find adayin which ropes length sum up toX, we will save it and search for a even lower value (asMinimum daysare needed).initialize
lowas0andhighas10^{18}, by this we understand that minimum days can be as low as value oflowand as high as value ofhigh.Calculate
mid = (low + high)/2, saymidis our desired day.Now, Linearly traverse and check for all ropes if their length at
midday is greater than or equal toK, if Yes add its value to a variableSum.After traversal if
Sumbecomes greater or equal toX, 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"]