## Saturday, October 15, 2016

### LeetCode OJ - Patching Array

Problem:

Analysis:

This is a hard problem, I got stuck for long trying to solve it.

I have got a couple hints from the discussion forum page. Greedy, $O(n)$.

$O(n)$ strike me because even to list all possible sums takes $O(2^n)$ time, there must be some sort of shortcut to get to the set of all sums.

But no, in the worst case, the set of all sums actually has $O(2^n)$ elements, we need to figure out a way to solve this problem without actually knowing the set of all sums.

Solution:

The key idea is that we do not need the set of all sums. We merely need to know the minimum infeasible number. As time progress, we can do greedy patching.

This is best explained by an example, let say the array is [1, 5, 10] and the goal is 20.

I haven't consider any numbers yet, so the minimum infeasible number if 1, nothing is feasible.

Let's consider 1, it is in the array, so definitely it is feasible. Considering it, the minimum infeasible number is 2.

Let's consider 2, it is not in the array, so definitely it is infeasible. We must patch the array. In this case we have two choice, we could add a 1, or we could add a 2. But adding 2 allow us to form 3 while adding 1 cannot, therefore we will add 2. In general, we always want to simply add the infeasible number. Now, the minimum infeasible number is 4.

Let's consider 4, it is not in the array, so definitely it is infeasible. We must patch the array. In this case we add 4 to the array, and the minimum infeasible number is 8.

Let's consider 5, it is feasible, and it is in the array. We know [1..8) is feasible, and we also know we can add 5 to any of those and still be feasible, so [6..13) is also feasible. Therefore the minimum infeasible number is now 13. In general, when we consider x, we already know [1..M) is feasible, and $M \ge x$, so we can always simply add the number to the minimum infeasible number.

At this point, we have covered all cases, as a last step, we consider 10. It is feasible, it is in the array, so the minimum infeasible number is now 23 > 20. We are done! Now we know we need 2 patches.

Implementation wise, we need to think of 'seeing' as an event. It is the smaller of the minimum infeasible number and the next array element, and we have the special case where the minimum infeasible number is the same as the next array element, and so we advance both pointers.

Special thanks to Sven Bömer who hinted me on this problem, without him I wouldn't have think of the key, the minimum infeasible number.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/patching-array/

#include "LEET_PATCHING_ARRAY.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

// #define LOG

using namespace std;

namespace _LEET_PATCHING_ARRAY
{
class Solution
{
public:
int minPatches(vector<int>& nums, int n)
{
long long minInfeasibleValue = 1;
int patch = 0;
int s = nums.size();
int i = 0;
bool moved = false;
int v = 0;
int f = 0;
while (true)
{
if (moved || i < s)
{
if (!moved)
{
v = nums[i];
f = 1;
while (true)
{
i++;
if (i == s)
{
break;
}
if (nums[i] != v)
{
break;
}
f++;
}
moved = true;
}
if (minInfeasibleValue >= v)
{
#ifdef LOG
cout << v << " is feasible while seeing it" << endl;
#endif
minInfeasibleValue += v * f;
#ifdef LOG
cout << minInfeasibleValue << " = minInfeasibleValue" << endl;
#endif
moved = false;
}
else
{
#ifdef LOG
cout << minInfeasibleValue << " is infeasible while seeing it" << endl;
#endif
patch++;
minInfeasibleValue *= 2;
#ifdef LOG
cout << minInfeasibleValue << " = minInfeasibleValue" << endl;
#endif
}
}
else
{
#ifdef LOG
cout << minInfeasibleValue << " is infeasible while seeing it" << endl;
#endif
patch++;
minInfeasibleValue *= 2;
#ifdef LOG
cout << minInfeasibleValue << " = minInfeasibleValue" << endl;
#endif
}
if (minInfeasibleValue > n)
{
break;
}
}
return patch;
}
};
};

using namespace _LEET_PATCHING_ARRAY;

int LEET_PATCHING_ARRAY()
{
Solution solution;
vector<int> nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(31);
nums.push_back(33);
cout << solution.minPatches(nums, ~(1 << 31)) << endl;
return 0;
}