My simple accepted C++ solution


  • 12
    Y

    Idea: 1. Check the content if the current one is within sum +1, which is the total sum of all previous existing numbers. If yes, we proceed and update sum. If not, we patch one number that is within sum + 1.

    1. Keep updating the sum until it reaches n.
     int minPatches(vector<int>& nums, int n) {
        
        int len = nums.size();
        int sum = 0;
        int patch = 0;
        int count = 0;
    
        while (sum < n) {
            if (count != len && nums[count] <= sum + 1) {
                sum += nums[count];
                count ++;
            }
            else {
                patch ++;
                if (sum > (INT_MAX - 1) / 2) {
                    sum = INT_MAX;
                }
                else {
                    sum = sum * 2 + 1;
                }
            }
        }
        
        return patch;
    }

  • 0
    O

    this is incredible simple and working solution!


  • 1
    B

    You can avoid unnecessary if else in case of patches by taking sum as long


  • 0
    S
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.