De Shaw | SDE | Hard OA | 2023 | Binary Search

Question

Answer 1

public  int getMinDecrement(int arr[],int maxMoves){

        int max=0;

        for(int ele:arr){

            max=Math.max(ele,max);

        }

        int l=1;

        int r=max;

 

        while(l<r){

            int mid=(l+r)>>1;

            int moves=calcMoves(mid,arr);

            if(moves>maxMoves){

                l=mid+1;

            }

            else{

                r=mid;

            }

        }

        return l;

    }

   

    public  int calcMoves(int mid,int arr[]){

        int n=arr.length;

        int moves=0;

        for(int i=0;i<n;i++){

            if(arr[i]<=mid){

                moves+=1;

            }    

            else if(arr[i]%mid==0){

                moves+=(arr[i]/mid);

            }

            else{

                moves+=(arr[i]/mid)+1;

            }

        }

        return moves;

 }