Untitled

mail@pastecode.io avatar
unknown
plain_text
18 days ago
2.3 kB
0
Indexable
Never
class Solution {
public:

    // a method that given me true or false whether input satisfies
    // we want to check if input is my maximum penalty 
    //9 -> 3 : 2
    // 9-> 3, 6 //1
    // 6 -> 3, 3 //2
    //reaching from nay number to the input you need to devide
    //6/3 -> 2
    //6-> 3, 3 in one step
    //9 -> 2
    //(9-1)/2 -> 4
    //9 -> 2 // 4
    //4, 4 -> 1
    //2, 2, 4 -> 2
    //2, 2, , 3, 2 -> 3
    //if the number is divisable then answer woule be x/y-1
    //8
    // 4, 4
    //2, 2, 4
    //2, 2, 2, 2
    //9
    //4, 5
    //2, 2, 5
    //2, 2, 2, 3
    //2, 2, 2, 2, 1 // answer would be x/y
    //9 -> 2
    bool check(int input, vector<int> &nums, int maxOperations) {

        int num_of_operations=0;
        for(int i=0;i<nums.size();i++) {
            // if(input>nums[i])
            // return false;
            if(nums[i]%input==0) {
                num_of_operations+=(nums[i]/input -1);
            } else {
                num_of_operations+=(nums[i]/input);
            }
            if(num_of_operations>maxOperations)
            return false;
        }
        return true;

    }


    
    int minimumSize(vector<int>& nums, int maxOperations) {
        // whenever you see a problem that tells you maximize the minimum or minimize the maximum
        //one possible solution definitely binary search 

        //2, 4, 8, 2
        //2, 4, 3, 5, 2 -> 1
        //2, 4, 3, 2, 3, 2 -> 2
        //2, 2, 2, 3, 2, 3, 2 -> 3
        //2, 2, 2, 1, 2, 2, 3, 2 -> 4

        // this is all my possible anwers 

        //1 ->10^5
        // if x is valid then it's guranteed that's 1->x all the inputs are guranteed to be valid 

        //1, x, 10^9
        //      x+1, 10^9 -> y belongs to this range satifying the condition
        //           y+1, 10^9 // we don't find anything on the right of y, then this 

        int low = 1;
        int high = 1e9; // this high can be in this case max in the array//10^9
        int ans = -1;
    

        while(low<=high) {
            int  mid = low + (high -low)/2;
           
            if(check(mid, nums, maxOperations)) {
                ans = mid;
                high = mid-1;
            } else {
                low = mid+1;
            }
        }

        return ans;

    }
};
Leave a Comment