INFOSYS POWER PROGRAMMER | HARD PROBLEM | Binary Srch

https://leetcode.com/discuss/interview-question/3196203/Infosys-Power-Programmer-or-Online-Assessment-Question

QUESTION ASKED IN INFOSYS POWER PROGRAMMER OA

In a large factory, there are N walls that the owner painted with different types of paints. Due to the humidity and the difference in the type of paints each wall i will take Xi minutes to dry.

However, there is a magic machine that we can set to work for a certain integer number of minutes and put it in front of a certain wall to speed up the drying process.

It is given the machine cannot be moved during its work or it will break. Also, for every minutes of work of this machine, it decreases the time remaining to dry the wall in front of it by K minutes. It is also given that if the remaining drying time for a wall is less than K, it will become 0 and dry up without any problems.

Your task is to find the minimum number of minutes in which all the walls of the factory can be dried.

Note:
We have one machine, but after finishing a wall we can move this machine to another wall.

Input format:

The first line contains an integer N, denoting the number of elements in X.
The next line contains an integer K, denoting the magic machine's acceleration number.
Each line i of the N subsequent lines (where 0 <= i < N) contains an integer describing X[i].

Constraints:
1 <= N <= 10^5
1 <= K <= 10^9
1 <= X[i] <= 10^9

Test cases:

Input:
1  1
1
Output:
1
Explanation:
We will let it dry without using the magic machine

Input:
1 2
1
Output:
1
Explanation:
We will let it dry without using the magic machine

Input:
1 17
35
Output:
3
Explanation:
We will use the magic machine three times in a row on the first element.


arr={5,2,10,7}   ,  k=3
arr        5     2    10    7
-------------------------------
t=0        4     1    7     6    Reduced 10 to 7 by machine
t=1        3     0    4     5    Reduced 7  to 4 by machine
t=2        2     0    3     2    Reduced 5  to 2 by machine
t=3        1     0    0     1    Reduced 3  to 0 by machine
t=4        0     0    0     0
Time required=5 mins



arr={7,9,10,3,15} , k=5
index-  0   1   2     3    4
arr-    7   9   10    3   15
-----------------------------
t=0     6   8    9    2   10  // machine on i=4, 15->10
t=1     5   7    8    1   5   // machine on i=4, 10->5
t=2     4   6    3    0   4  //  machine on i=2, 8->3
t=3     3   1    2    0   3  //  machine on i=1, 6->1
t=4     0   0    1    0   2  //  machine on i=0, 3->0
t=5     0   0    0    0   0  //  machine on i=4, 2->0
Time required= 6 mins


arr={12,11,4,2} , k=3
index-  0     1     2     3
arr-    12    11    4     2
-----------------------------
t=0     9     10    3     1
t=1     8     7     2     0
t=2     5     6     1     0
t=3     4     3     0     0
t=4     1     2     0     0
t=5     0     0     0     0
Time required= 6 mins

-------------------------------------------------------------------------------------------------------------------------------------

PRIORITY QUEUE CODE->

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

vector<int> arr;
int k;

void solve(vector<int> &arr, int k){
    priority_queue<pair<int,int>> pq;
    for(int i=0;i<arr.size();i++){
        pq.push({arr[i],0});
    }

    int runningTime=0;
    while(!pq.empty()){
        auto tp=pq.top();
        pq.pop();
        int currWallTime=tp.first-(runningTime-tp.second);
        if(tp.second!=runningTime){
            if(currWallTime>0){
                pq.push({currWallTime,runningTime});
            }
            continue;
        }
        if(currWallTime>0){
            currWallTime-=k;
            runningTime++;
            if(currWallTime>0){
                pq.push({currWallTime,runningTime});
            }
        }
    }
    cout<<runningTime;
}

int main() {

    arr={35};
    k=17;
    solve(arr,k); //ANSWER ->3


    arr={6,5,4};
    k=2;
    solve(arr,k); //ANSWER ->4


    arr={1,8,10};
    k=1;
    solve(arr,k); //ANSWER ->10


    arr={5,2,10,7};
    k=3;
    solve(arr,k); //ANSWER ->5


    arr={12,11,4,2};
    k=3;
    solve(arr,k); //ANSWER ->6


    arr={10,10,10};
    k=3;
    solve(arr,k); //ANSWER ->6


    arr={7,9,10,3,15};
    k=5;
    solve(arr,k); //ANSWER ->6


    arr={17};
    k=16;
    solve(arr,k); //ANSWER ->2


    arr={5,2,10,7,35};
    k=3;
    solve(arr,k); //ANSWER ->12


    return 0;
}

The above code is correct, BUT, it will fail for larger test cases. The time complexity O(ZlogN), where Z=10^9. So, this approach guarantee would not pass the larger test cases.
---------------------------------------------------------------------------------------------------------------------------------------


Binary Search Code->

This code below was written by someone else. But this will pass all the TC's even the larger ones. The code below uses the idea that min time to dryWalls is actually the time you used the machine on each wall. Minimizing the usage of machine on each wall to get the optimal drying time.

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

bool isOK(vector<int> &X, int k, int time){
    /*
        If y is the minimum time machine is used on ith wall.
        Then k*y is the value, machine reduced and (time-y) is
        the remaining value getting reduced by 1 as time passes.

        X[i]<=k*y+(time-y)
        X[i]<=k(y-1)+time
        X[i]-time<=y(k-1)
        (X[i]-time)/(k-1)<=y

        So, min time a machine is used on wall X[i] is y=(X[i]-time)/(k-1).
    */
    int calculatedTime=0;
    for(auto x: X){
        if(x-time>0){
            calculatedTime+=ceil((double)(x-time)/(double)(k-1));
        }
    }
    return calculatedTime<=time;
}

void solve(vector<int> &arr, int k){
    if(k==1){
        cout<<*max_element(arr.begin(),arr.end())<<endl;
        return;
    }
   /* Binary searching for minTime. The mintime to dry wall can be obtained by minimising the time spent by the machine on drying walls */
    int low=0;
    int high=*max_element(arr.begin(),arr.end());
    int res=-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(isOK(arr,k,mid)==true){
            res=mid;
            high=mid-1;
        }
        else{
            low=mid+1;
        }
    }
    cout<<res<<endl;
}



int main() {
    vector<int> arr;
    int k;

    arr={35};
    k=17;
    solve(arr,k); //ANSWER ->3


    arr={6,5,4};
    k=2;
    solve(arr,k); //ANSWER ->4


    arr={1,8,10};
    k=1;
    solve(arr,k); //ANSWER ->10


    arr={5,2,10,7};
    k=3;
    solve(arr,k); //ANSWER ->5


    arr={12,11,4,2};
    k=3;
    solve(arr,k); //ANSWER ->6


    arr={10,10,10};
    k=3;
    solve(arr,k); //ANSWER ->6


    arr={7,9,10,3,15};
    k=5;
    solve(arr,k); //ANSWER ->6


    arr={17};
    k=16;
    solve(arr,k); //ANSWER ->2


    arr={5,2,10,7,35};
    k=3;
    solve(arr,k); //ANSWER ->12


    arr={1000,500,100,10};
    k=100;
    solve(arr,k); //ANSWER ->16


    return 0;
}