# 330 Patching Arrays

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.
//figure representing how my arrays work
// Note to self: to optimize this, make and check all the comparisons at the beginning
// rather than finding the patches, and checking them once over again.
// when you come back work on the combinations generator to produce all combinations
// algorithm is correct but not all possible combinations are produced.
// ex. in 1 5 10 2 4, you are missing possibility 1 10 2 because you assumed that
// you need one dynamic counter when in fact you can have to num.size() amount...
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
void print3d(vector<vector<vector<int>>> &nums) {
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.at(i).size(); j++) {
for (int k = 0; k < nums.at(i).at(j).size(); k++) {
cout << nums.at(i).at(j).at(k) << ' ';
}
cout << endl;
}
cout << endl;
}
}
void print1D(vector<int> &nums) {
for (auto i : nums) cout << i << ' '; cout << endl;
}
inline vector<int> sum3D(vector<vector<vector<int>>> *nums) {
vector<int> sum;
for (int i = 0; i < (*nums).size(); i++) {
for (int j = 0; j < (*nums).at(i).size(); j++) {
sum.push_back(accumulate((*nums).at(i).at(j).begin(), (*nums).at(i).at(j).end(), 0));
}
}
return sum;
}
bool confirmRange(vector<int> *sums, int n) {
std::sort((*sums).begin(), (*sums).end());
std::unique((*sums).begin(), (*sums).end());
vector<int> comparisonVect;
for (int i = 1; i <= n; i++) {
comparisonVect.push_back(i);
}
//print1D(comparisonVect);
//print1D((*sums));
if ((*sums).size() < n) return false;
// check if sums have range [1,n]
for (int i = 0; i < n; i++) {
if ((*sums).at(i) == comparisonVect.at(i)) continue;
else return false;
}
return true;
}
/*
matrixSize: number of countable rows or columns in the square matrix + 1
*/
inline vector<vector<int>> combinationMatrix(vector<int> *nums, int matrixSize,
int numPushBacks, int numPushBackStart, int nextColumn) {
vector<vector<int>> matrix;
vector<int> temp;
int numPushBackReset = numPushBackStart;
for (int i = 0; i < matrixSize; i++) {
for (int j = nextColumn; j < matrixSize; j++) {
temp.push_back((*nums).at(i));
for (int k = 0; k < numPushBacks; k++) {
temp.push_back((*nums).at(numPushBackStart));
numPushBackStart++;
}
numPushBackStart = numPushBackReset;
temp.push_back((*nums).at(j));
matrix.push_back(temp);
temp.clear();
}
nextColumn++;
numPushBackReset++;
numPushBackStart = numPushBackReset;
}
return matrix;
}
int minPatches(vector<int>& nums, int n) {
int numPatches = 0;
vector<vector<vector <int>>> combinationMatricies;
vector<int> sumArray;
vector<vector<int>> temp2;
vector<int> temp;
// used at the end with to minimize the number of patches:
vector<int> patches;
vector<int> original = nums;
vector<int> orginalCopy = nums;
while (true) {
std::sort(nums.begin(), nums.end());
int matrixSize = nums.size();
int matrixSizeChange = matrixSize;
int numPushBacks = 0;
int numPushBackStart = 1;
int nextColumn = 1;
temp.clear();
temp2.clear();
for (auto i : nums) {
temp.push_back(i);
temp2.push_back(temp);
combinationMatricies.push_back(temp2);
temp.clear();
temp2.clear();
}
// insert all possible combinations for any nCk
// -2 because we add two edge cases independently
for (int i = 0; i < matrixSize - 2; i++) {
combinationMatricies.push_back(combinationMatrix(&nums, matrixSizeChange, numPushBacks,
numPushBackStart, nextColumn));
numPushBacks++;
nextColumn++;
}
for (auto i : nums) {
temp.push_back(i);
}
temp2.push_back(temp);
combinationMatricies.push_back(temp2);
temp.clear();
temp2.clear();
//print3d(combinationMatricies);
// sum all the elements in the vector
vector<int> sum = sum3D(&combinationMatricies);
//print1D(sum);
//cout << endl;
// success
if (confirmRange(&sum, n)) {
//return numPatches;
break;
}
// add another patch. Doing brute force way
else {
// start from 1!
std::sort(nums.begin(), nums.end());
int patchCounter = 1;
for (int i = 0; i < nums.size(); i++) {
if (nums.at(i) == patchCounter) {
patchCounter++;
}
else {
// if we are here, then the range tested was incomplete
nums.push_back(patchCounter);
// actual numbers inserted into the original vector
patches.push_back(patchCounter);
numPatches++;
sumArray.clear();
combinationMatricies.clear();
break;
}
}
}
}
// minimize the number of patches by finding the minimum number of patches (numbers added)
// that produce range required. Combinations will be returned in increasing vector size, so
// it won't be nessessary to test them all.
// 1) combination of the patches
combinationMatricies.clear(); temp.clear(); temp2.clear();
std::sort(patches.begin(), patches.end());
//print1D(patches);
//cout << endl << endl;
int matrixSize = patches.size();
int matrixSizeChange = matrixSize;
int numPushBacks = 0;
int numPushBackStart = 1;
int nextColumn = 1;
temp.clear();
temp2.clear();
for (auto i : patches) {
temp.push_back(i);
temp2.push_back(temp);
combinationMatricies.push_back(temp2);
temp.clear();
temp2.clear();
}
for (int i = 0; i < matrixSize - 2; i++) {
combinationMatricies.push_back(combinationMatrix(&patches, matrixSizeChange, numPushBacks,
numPushBackStart, nextColumn));
numPushBacks++;
nextColumn++;
}
for (auto i : patches) {
temp.push_back(i);
}
temp2.push_back(temp);
combinationMatricies.push_back(temp2);
// 2) Add each pair of combination patch into nums, and test whether or not it was successful
vector<vector<vector<int>>> combinations_new;
int sizePatch = 0;
// now combinationMatricies is overwritten as the combination of patches
for (int i = 0; i < combinationMatricies.size(); i++) {
for (int j = 0; j < combinationMatricies.at(i).size(); j++) {
for (int k = 0; k < combinationMatricies.at(i).at(j).size(); k++) {
original.push_back(combinationMatricies.at(i).at(j).at(k));
cout << combinationMatricies.at(i).at(j).at(k) << ' ';
sizePatch++;
}
cout << endl;
// test the pair by finding all the new combinations made by the new pair
std::sort(patches.begin(), patches.end());
//print1D(patches);
// find the sum of combinations made afer the pair combination was added.
int matrixSize = original.size();
int matrixSizeChange = matrixSize;
int numPushBacks = 0;
int numPushBackStart = 1;
int nextColumn = 1;
temp.clear();
temp2.clear();
for (auto i : original) {
temp.push_back(i);
temp2.push_back(temp);
combinations_new.push_back(temp2);
temp.clear();
temp2.clear();
}
for (int i = 0; i < matrixSize - 2; i++) {
combinations_new.push_back(combinationMatrix(&original, matrixSizeChange, numPushBacks,
numPushBackStart, nextColumn));
numPushBacks++;
nextColumn++;
}
for (auto i : original) {
temp.push_back(i);
}
temp2.push_back(temp);
combinations_new.push_back(temp2);
cout << "3d print: "; print3d(combinations_new); cout << "_________" << endl;
// sum all the elements in the vector
vector<int> sum = sum3D(&combinations_new);
std::sort(sum.begin(), sum.end());
cout << endl << endl;
print1D(sum);
// success -> return the size of the patch
if (confirmRange(&sum, n)) {
return sizePatch;
}
// otherwise check the next patch, it's guareenteed to be one of them
else {
original = orginalCopy;
combinations_new.clear();
sizePatch = 0;
}
}
}
}
int main()
{
vector<int> test = { 1,5,10 };
vector<int> test2 = { 1,3,4 };
cout << minPatches(test, 20);
}