Google Interview Question SDE1s
Country: United States
This is essentially the same as the coin change problem. Below is a little different approach which works if the required number 'n' is reasonably small. Time Complexity is O(n)
public static boolean combinationSum(int[] items, int sum) {
boolean[] possible = new boolean[sum+1];
possible[0] = true;
for (int i=0; i<=sum; i++) {
if (possible[i]) {
for (int j=0; j<items.length; j++) {
if (i+items[j] <= sum) {
possible[i+items[j]] = true;
}
}
}
}
return possible[sum];
}
/*
A better way to look it using sequences
Define a Sequence S, such that it is strictly increasing
and generated by the rule of sum of non-negative multiples of the numbers in the array.
Thus, S(0) = 0 and we go in a = [6,9,20]
S(1) = 6
S(2) = 9
S(3) = 12 = 6 * 2
S(4) = 15 = 6 + 9
S(5) = 18 = ( 3 * 6 , 9*2 )
We use ZoomBA to solve it and show a nice pattern.
This is solvable by adding 6,9,20 to each item encountered before in the sequence,
and check if the current item is minimum of the larger item than the current max
Then the next item is generated. Thus, the problem is solved when we have
Target n is such that
S(k) < n <= S(k+1)
To generate the this array a from bases is easy, and can be left as an exercise to the reader.
Hint: use the same algorithm and start with 0,min_of_base
*/
bases = [6,9,20]
// first few items of the sequence from the bases till 20
a = [ 0, 6, 9, 12 , 15 , 18, 20 ]
s = seq( a ) -> {
cached = $.p // previous items
last_no = cached[-1] // last item
maxes = list ( bases ) -> {
item = $.o // store the individual base items
ix = index ( cached ) :: { $.o + item > last_no }
cached[ix] + item // we find where we max - so store it
}
#(min,Max) = minmax( maxes ) // find min of the maxes
min // return min as the next item in the sequence
}
// now call
def find_some( n ){
if ( n <= s.history[-1] ) return n @ s.history // obvious
while ( s.history[-1] <= n ){ s.next } // iterate over
return n @ s.history // and then is trivial
}
println( find_some(47) )
println( find_some(23) )
'''
Introduction:
- The sum can be made up of multiple terms
e.g. f[0]*nums[0] + f[1]*nums[1] + f[2]*nums[2] ... f[n-1]*nums[n-1]
note: 0 <= f[i] <= floor(target/nums[i])
- Find a solution that works for big numbers efficiently as well
Solution Brute Force:
try all f[i] and check if any combination would
lead to target. Of course one can stop trying if target is exceeded
runtime: O(target/nums[0]*target/nums[1]*..*target/nums[n-1])
Optimization Idea: keep calculated sums
Idea: keep intermediary sums and check every time if the value needed to
reach target has already been calculcated
--> this can accellerate to find a solution if one exists, but if none exists
it doesn't help
Optimization Idea: try to avoid double work
If we checked target - 14 and know it doesn work, we shouldn't retry if we get to "14" in an other way
Optimization Idea: Recursion with memoization could look like:
It's not neat, but I couldn't come up with something better within 30 Minutes:
- f(t, i) = f(t-k*nums[i], i - 1), as long as i >= 0 for each k between 0 and t >= k*nums[i]
Memoization I would use to avoid rechecking the same sub-problems again and again meaning, with nums in
the range from [0..k] I mark the values i can't construct with
'''
def factorSumRecursion(nums, target, i):
global memo
if target < 0 or i < 0 or target in memo[i]: return False
if target == 0: return True
if target >= nums[i] 0:
if factorSumRecursion(nums, target - nums[i], i): return True
else: memo[i].add(target - nums[i])
if factorSumRecursion(nums, target, i - 1): return True
else: memo[i-1].add(target)
return False
def factorSum(nums, target):
global memo
memo = [set() for i in range(len(nums))]
if len(nums) == 0: return target == 0
return factorSumRecursion(nums, target, len(nums)-1)
print(factorSum([6,9,20], 47)) #3*9 + 20
print(factorSum([6,9,20], 48)) #8*6
print(factorSum([6,9,20], 49)) #2*20 + 9
print(factorSum([6,9,20], 50)) #1*20 + 5*6
print(factorSum([6,9,20], 12)) #2*6
print(factorSum([6,9,20], 13)) #False
print(factorSum([6,9,20], 9)) #9
def Combinations(num,deduct=0,combs=[]):
num = num - deduct
if num == 0:
combs.append(deduct)
return True
elif num < deduct:
return False
else:
if deduct != 0:
combs.append(deduct)
if Combinations(num,20,combs) or Combinations(num,9,combs) or Combinations(num,6,combs):
return True,combs
else:
if len(combs)> 0 :
combs.pop()
return False
print Combinations(24,0,[]) #returns (True, [9, 6, 9])
print Combinations(13,0,[]) #returns False
print Combinations(47,0,[]) #returns (True, [20, 9, 9, 9])
I found 2 solutions, a simple for multiples of 2 elements and recursive approach involving multiples of all elements.
The first and the simplest approach is to build a table of all possible multiplies and sum them with each other, this would work with A={6,9,20} and T=47 but is limited to only multiples of 2 elements. This method will fail with A={7411, 9461, 20161, 1901, 1531, 281} and T=27751.
The second approach would recursively go through all multiples of all elements (without using multiples of the same elements) and so it may engage a multiple element in A. This approach will work if the target T comprises of multiples of 3 and more elements of A.
static void Main(string[] args)
{
int[] arr = new int[6]{7411, 9461, 20161, 1901, 1531, 281};
var target = 27751;
Console.WriteLine($"Values: {string.Join(", ", arr)}; Target = {target}");
// testing with big primes
Console.WriteLine("Simple:");
FindComboSimple(arr, target); // 2 primes can not produce 27751
Console.WriteLine("Recursive:");
FindComboRec(arr, target); // 3 or more primes can prodice 27751
//testing given example
arr = new int[3] { 6,9,20 };
target = 47;
Console.WriteLine($"Values: {string.Join(", ", arr)}; Target = {target}");
Console.WriteLine("Simple:");
FindComboSimple(arr, 47);
Console.WriteLine("Recursive:");
FindComboRec(arr, 47);
Console.ReadLine();
}
public static void FindComboSimple(int[] ar, int target)
{
var mults = new int[ar.Length][];
// calculating all possible multiplies which are less then target
for (int i =0; i < ar.Length; i++)
{
if (ar[i] == 0)
continue;
var maxKoef = target / ar[i];
mults[i] = new int[maxKoef - 1];
for (var k = 0; k < maxKoef - 1; k ++)
mults[i][k] = ar[i] * (k + 1);
}
// adding every possible mults with each other to find target
for(var i = 0; i < mults.Length; i++)
{
for (var j = 0; j < mults[i].Length; j++)
{
for (var ii = i; ii < mults.Length; ii ++)
{
if (ii == i)
continue;
for (var jj = 0; jj < mults[ii].Length; jj ++)
{
if (mults[i][j] + mults[ii][jj] == target)
{
Console.WriteLine($"{target} = {mults[i][0]}*{j + 1} + {mults[ii][0]}*{jj + 1}");
return;
}
}
}
}
}
}
public static bool FindComboRec(int[] arr, int target, int ipos = -1, int val = 0, string currentExpr = "")
{
for(var i = ipos + 1; i < arr.Length; i++)
{
if (arr[i] == 0)
continue;
for(var j = 0; j < target / arr[i] ; j ++)
{
var currentValue = arr[i] * j + val;
if (currentValue == target)
{
Console.WriteLine($"{target} = {arr[i]}*{j}{currentExpr}");
return true;
}
else
{
var expr = (j != 0 ? (currentExpr + $" + {arr[i]}*{j}" ):currentExpr);
if (FindComboRec(arr, target, i, currentValue, expr))
return true;
}
}
}
return false;
}
Output:
Values: 7411, 9461, 20161, 1901, 1531, 281; Target = 27751
Simple:
Recursive:
27751 = 281*5 + 1901*5 + 1531*11
Values: 6, 9, 20; Target = 47
Simple:
47 = 9*3 + 20*1
Recursive:
47 = 20*1 + 9*3
By recursively checking a number multiple times if it contributes to target and going to next numeber in the array recursively
public static boolean isumOfmultiplier(int[] in, int sum) {
return auxIsSumOfmultiplier(in,in.length,sum);
}
public static boolean auxIsSumOfmultiplier(int[] in, int position, int sum) {
if (sum == 0)
return true;
if (position == 0)
return false;
boolean finalResult = false;
int multiplier = 0; // to use number multiple times for the sum
if (in[position - 1] == 0) { // if zero is in the array, skip and goto next
// level i.e position-1 recursively
return auxIsSumOfmultiplier(in, position - 1, sum);
}
while (sum - multiplier * in[position - 1] >= 0) {
finalResult = auxIsSumOfmultiplier(in, position - 1, sum - multiplier * in[position - 1]);
if (finalResult)
break;
multiplier++;
}
return finalResult;
}
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
int main()
{
char ch[20],mask1=0,mask2=0,i=0;
cin>>ch;
while(ch[i])
{
if(ch[i]=='A')
{
mask1++;
}
if(strlen(ch)>(i+2)){
if((ch[i]=='A'||ch[i]=='L')&&(ch[i+1]=='A'||ch[i+1]=='L')&&(ch[i+2]=='A'||ch[i+2]=='L'))
return 0;
}
if(mask1==2)
{
return 0;
}
i++;
}
return 1;
}
If there are other people like me who got confused what the problem actually states, this is what is being asked: given a number like 47 and array A = [6, 9, 20] determine whether the given number can be decomposed as:
47 = 6*a + 9*b + 20*c where a, b, c >= 0.
This is basically a variation of coin changing problem.
C++
bool checkSum(const vector<int>& A, int Sum){
vector <vector<bool>> D(A.size() + 1, vector<bool>(Sum + 1, false);
for(int i = 0; i <= A.size(); i++){
D[i][0] = true;
}
for(int i = 1; i <= Sum; i++){
for(int j = 1; j <= A.size(); j++){
D[i][j] = D[i-1][j];
if(j - A[i - 1] >=0){
D[i][j] = D[i][j] || D[i][j - A[i - 1]];
}
}
}
return D[A.size()][Sum];
}
#include <unordered_map>
#include <vector>
#include <iostream>
using namespace std;
bool CanBeComposed(const vector<int>& a, int target, unordered_map<uint64_t, bool>& memo, int idx = 0)
{
if (idx < 0 || idx > a.size() || target < 0)
{
return false;
}
if (target == 0)
{
return true;
}
if (idx == a.size())
{
return false;
}
if (a[idx] == 1)
{
return true;
}
uint64_t memo_key = (static_cast<uint64_t>(idx) << 32) | target;
auto it = memo.find(memo_key);
if (it != memo.end())
{
return it->second;
}
bool res = false;
if (a[idx] == 0)
{
res = CanBeComposed(a, target, memo, idx + 1);
}
else
{
for (int i = 0; i * a[idx] <= target && !res; ++i)
{
res = CanBeComposed(a, target - i * a[idx], memo, idx + 1);
}
}
memo[memo_key] = res;
return res;
}
bool CanBeComposed2(const vector<int>& a, int target)
{
vector<bool> dp;
dp.resize(target + 1, false);
dp[0] = true;
for (int i = 0; i < a.size(); ++i)
{
if (a[i] == 1)
{
return true;
}
for (int j = 0; j + a[i] < dp.size(); ++j)
{
int k = j + a[i];
dp[k] = dp[k] | dp[j];
}
}
return dp[target];
}
int main()
{
vector<int> a = {6, 9, 20};
int target = 47;
unordered_map<uint64_t, bool> memo;
cout << CanBeComposed(a, target, memo) << "\n";
cout << CanBeComposed2(a, target) << "\n";
return 0;
}
int main()
{
int nums[] = { 6, 9, 20};
int size = sizeof(nums)/sizeof(nums[0]);
int target = 47;
if (combinationSum(nums, size, target)) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
}
bool combinationSum(int a[], int size, int target)
{
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j) {
continue;
}
if (target < a[i]) {
return false;
}
int k = 1;
while ((a[i] * k) < target) {
int diff = target - (a[i] * k);
if (diff % a[j] == 0) {
return true;
}
k++;
}
}
}
return false;
}
int main()
{
int nums[] = { 6, 9, 20};
int size = sizeof(nums)/sizeof(nums[0]);
int target = 47;
if (combinationSum(nums, size, target)) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
}
bool combinationSum(int a[], int size, int target)
{
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j) {
continue;
}
if (target < a[i]) {
return false;
}
int k = 1;
while ((a[i] * k) < target) {
int diff = target - (a[i] * k);
if (diff % a[j] == 0) {
return true;
}
k++;
}
}
}
return false;
}
int main()
{
int nums[] = { 6, 9, 20};
int size = sizeof(nums)/sizeof(nums[0]);
int target = 47;
if (combinationSum(nums, size, target)) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
}
bool combinationSum(int a[], int size, int target)
{
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j) {
continue;
}
if (target < a[i]) {
return false;
}
int k = 1;
while ((a[i] * k) < target) {
int diff = target - (a[i] * k);
if (diff % a[j] == 0) {
return true;
}
k++;
}
}
}
return false;
}
- deep March 17, 2017dp optimal solution in java public static boolean combinationSum(int[] nums, int target) { if(target==0) return true; if(nums.length==0) return false; boolean[][] dp= new boolean[nums.length+1][target+1]; for(int i=0;i<=nums.length;i++) dp[i][0]=true; for(int i=1;i<=nums.length;i++){ for(int j=nums[i-1];j<=target;j++){ if(dp[i-1][j]==true){ dp[i][j]=true; continue; } for(int k=1;k<=j/nums[i-1];k++){ if(dp[i][j-nums[i-1]*k]==true){ dp[i][j]=true; break; } } } } return dp[nums.length][target]; }