## Wednesday, January 27, 2016

### Leetcode 330 - Patching Array

https://leetcode.com/problems/patching-array/
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range `[1, n]` inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.
Example 1:
nums = `[1, 3]`n = `6`
Return `1`.
Combinations of nums are `[1], [3], [1,3]`, which form possible sums of: `1, 3, 4`.
Now if we add/patch `2` to nums, the combinations are: `[1], [2], [3], [1,3], [2,3], [1,2,3]`.
Possible sums are `1, 2, 3, 4, 5, 6`, which now covers the range `[1, 6]`.
So we only need `1` patch.
Example 2:
nums = `[1, 5, 10]`n = `20`
Return `2`.
The two patches can be `[2, 4]`.
Example 3:
nums = `[1, 2, 2]`n = `5`
Return `0`.
think about `nums = [1,1,1,1,...]`. Then you'll go through all those before you ever get to doubling. It's O(k+log(n)), where k is the size of the array.
``````int minPatches(vector<int>& nums, int n) {
long miss = 1, added = 0, i = 0;
while (miss <= n) {
if (i < nums.size() && nums[i] <= miss) {
miss += nums[i++];
} else {
miss += miss;
}
}
}
``````
Let `miss` be the smallest sum in `[1,n]` that we might be missing. Meaning we already know we can build all sums in `[1,miss)`. Then if we have a number `num <= miss` in the given array, we can add it to those smaller sums to build all sums in `[1,miss+num)`. If we don't, then we must add such a number to the array, and it's best to add `miss` itself, to maximize the reach.
Another implementation, though I prefer the above one.
``````int minPatches(vector<int>& nums, int n) {
int count = 0, i = 0;
for (long miss=1; miss <= n; count++)
miss += (i < nums.size() && nums[i] <= miss) ? nums[i++] : miss;
return count - i;
}``````

https://discuss.leetcode.com/topic/35709/share-my-thinking-process
The question asked for the "minimum number of patches required". In other words, it asked for an optimal solution. Lots of problems involving optimal solution can be solved by dynamic programming and/or greedy algorithm. I started with greedy algorithm which is conceptually easy to design. Typically, a greedy algorithm needs selection of best moves for a subproblem. So what is our best move?
Think about this example: nums = [1, 2, 3, 9]. We naturally want to iterate through nums from left to right and see what we would discover. After we encountered 1, we know 1...1 is patched completely. After encountered 2, we know 1...3 (1+2) is patched completely. After we encountered 3, we know 1...6 (1+2+3) is patched completely. After we encountered 9, the smallest number we can get is 9. So we must patch a new number here so that we don't miss 7, 8. To have 7, the numbers we can patch is 1, 2, 3 ... 7. Any number greater than 7 won't help here. Patching 8 will not help you get 7. So we have 7 numbers (1...7) to choose from. I hope you can see number 7 works best here because if we chose number 7, we can move all the way up to 1+2+3+7 = 13. (1...13 is patched completely) and it makes us reach n as quickly as possible. After we patched 7 and reach 13, we can consider last element 9 in nums. Having 9 makes us reach 13+9 = 22, which means 1...22 is completely patched. If we still did't reach n, we can then patch 23, which makes 1...45 (22+23) completely patched. We continue until we reach n.
``````    public int minPatches(int[] nums, int n) {
if (n <= 0) return 0;
nums = nums == null ? new int[0] : nums;
int current_ind = 0, ret = 0;
long boundary_val = 1, sum = 0;
while (boundary_val <= n) {
if (current_ind < nums.length && nums[current_ind] <= boundary_val) {
sum += nums[current_ind++];
boundary_val = sum + 1;
} else {
ret++;
sum += boundary_val;
boundary_val = sum + 1;
}
}
return ret;
}``````
https://leetcode.com/discuss/82827/o-log-n-time-o-1-space-java-with-explanation-trying-my-best
https://leetcode.com/discuss/82832/java-here-is-my-greedy-version-with-brief-explanations-1ms
Greedy idea: add the maximum possible element whenever there is a gap
Iterating the nums[], and keeps adding them up, and we are getting a running sum. At any position, if nums[i] > sum+1, them we are sure we have to patch a sum+1 because all nums before index i can't make sum+1 even add all of them up, and all nums after index i are all simply too large.
``````public class Solution {
public int minPatches(int[] nums, int n) {
long sum = 0;
int count = 0;
for (int x : nums) {
if (sum >= n) break;
while (sum+1 < x && sum < n) {
++count;
sum += sum+1;
}
sum += x;
}
while (sum < n) {
sum += sum+1;
++count;
}
return count;
}
}
``````

``````    def minPatches(self, nums, n):
"""
:type nums: List[int]
:type n: int
:rtype: int
"""
idx, total, ans = 0, 1, 0
size = len(nums)
while total <= n:
if idx < size and nums[idx] <= total:
total += nums[idx]
idx += 1
else:
total <<= 1
ans += 1
return ans
```

```
https://www.hrwhisper.me/leetcode-patching-array/
public int minPatches(int[] nums, int n) {
int cnt = 0,i=0;
for(long known_sum = 1;known_sum <= n;){
if(i < nums.length && known_sum >= nums[i]){
known_sum += nums[i++];
}else{
known_sum <<= 1;
cnt++;
}
}
return cnt;
}
http://www.zrzahid.com/patching-array/
Basically, as long as cumulative sum so far is greater than the number we need to create , we are good. But id cumsum falls below the current number (between 1 to n) we need to create , then we have to add the current cumsum to itself (why?). This is because we assumed at any particular time cumsum is equal or greater than the current element we need to create. That is we doubling the cumsum when we add a missing element.
```public static int minPatches(int[] nums, int n) {
int sum = 1;
int i = 0;
int count = 0;

while(sum <= n){
if(i < nums.length && nums[i] <= sum){
sum+=nums[i++];
}
else{
sum<<=1;
count++;
}
}

return count;
}```

Example 1：
nums =
`[1, 3]`n = `6`

Example 2:
nums =
`[1, 5, 10]`n = `20`

```    public int minPatches(int[] nums, int n) {
long sum = 0;
int ans = 0;
int index = 0;
if (nums.length > 0 && nums[0] == 1) {
sum = 1;
index = 1;
}
while (sum < n)
{
while (index < nums.length && nums[index] <= sum)
{
sum += nums[index];
index++;
}
if (sum < n) {
if (index < nums.length && nums[index] == sum + 1)
index++;
else {
ans++;
}
sum ＝ 2 ＊ sum + 1;
}
}
return ans;
}```