Google Interview Question
Software Engineer / DevelopersCountry: United States
Oh that's because my main method calls findSubset(numbers, 2*len), meaning it looks for multiples of 2N.
If you looking for multiples of N then you should change that to just len and recompile first.
Sorry if I didn't make this clear.
i don't think the complexity is O(n^2), your inner loop iterates over all the subsets which means it is 2^n, therefore the complexity is O(n(2^n)).
@mee: The inner loop doesn't iterate over all the subsets. It iterates over each distinct subset sum mod M, which means the inner loop executes O(MN) times. If M = N or M = 2N, the inner loop executes O(N^2) times.
Now, it does appear at first that maybe the solution is actually O(N^3), because the line LinkedList<Integer> list = (LinkedList<Integer>)subsets.get(i).clone(); actually takes O(N) time to execute. However, that line is only hit if the current subset sum mod M is distinct from any other subset sum mod M seen so far. Since there can only be M different subset sums mod M, the line can only be executed M times, for a total of O(MN) time spent on that line.
Solution to (1):
Let Fk (1<=k<=N) be the first k elements in the list. Let sk be the sum of elements in Fk.
If there exists k such that sk%N = 0, then return elements in Fk.
Otherwise, every sk%N is between 1 and N-1. So, among s1%N, s2%N, ..., sN%N, there must exist i, j, si%N = sj%N. Return elements in Fj but not in Fi (suppose j > i).
This takes O(N) time. The same solution doesn't apply for question (2). But it seems a BFS approach should still use O(N) time.
I think both the questions have a similar solution. We would need to change the target variable below from N to 2N
static int[] input = new int[] { 3, 5, 2, 7, 6, 1, 8 };
static int target = input.Length;
static void Main(string[] args)
{
int output = new int[input.Length];
sOSAddingToMultipleOfLen(0, 0, 0, output);
}
static bool sOSAddingToMultipleOfLen(int currIndex, int sumSoFar,int filled, int[] output)
{
if (input == null || currIndex >= input.Length)
return false;
if ((sumSoFar) % target == 0 && output[0] != 0)
{
Console.WriteLine("--------");
foreach (int i in output)
Console.Write(i + ", ");
return true;
}
if (currIndex < input.Length)
{
output[filled] = input[currIndex];
bool with = SOSAddingToMultipleOfLen(currIndex + 1, sumSoFar + Input[currIndex], filled + 1, output);
output[filled] = 0;
bool wo = SOSAddingToMultipleOfLen(currIndex + 1, sumSoFar, filled, output);
return with || wo;
}
return false;
}
import java.util.ArrayList;
public class SubsetSumMultiOfN {
public static void findSumMultiOfN(ArrayList<Integer> list, int n) {
// start from the first number in the list.
ArrayList<Integer> subset = new ArrayList<Integer>();
int allowed_complement = n;
for (int i=0; i<n; i++) {
int current = list.get(i);
// if a number is already a multi of n, then stop and
// return a subset contain only that number
if (current % n == 0) {
// print out the result
System.out.println("Subset element: "+current);
return;
}
int complement = current % n;
if (complement <= allowed_complement) {
subset.add(current);
allowed_complement -= complement;
}
// check if subset found
if (allowed_complement == 0) {
// print out the result
System.out.print("Subset element:");
for (int j=0; j<subset.size(); j++) {
System.out.print(" "+subset.get(j));
}
System.out.println();
return;
}
}
// if none found
System.out.println("None found!");
}
public static void findSumMultiOf2N(ArrayList<Integer> list, int n) {
findSumMultiOfN(list, n*2);
}
public static void main(String[] args) {
// args contains the input numbers
// put them in an ArrayList
ArrayList<Integer> list = new ArrayList<Integer>();
int length = args.length;
for (int i=0; i<length; i++) {
list.add(Integer.parseInt(args[i]));
}
// give the list to the functions
System.out.println("Result for N:");
findSumMultiOfN(list, length);
System.out.println("Result for 2N:");
findSumMultiOf2N(list, length);
}
}
Brute force solution.
Go through all subsets (there are 2^n - 1) until you find one that is divisible by N (or 2N).
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool contains(vector<int> &v, int value) {
return find(v.begin(), v.end(), value) != v.end();
}
vector<int> findSubset(vector<int> A, int divisibleBy) {
for(auto i = 0; i < pow(2, A.size()) - 1; i++) {
vector<int> subset;
int sum = 0;
for(decltype(A.size()) idx = 0; idx < A.size(); idx++) {
if(i & (1 << idx) && !contains(subset, A[idx])) {
sum += A[idx];
subset.push_back(A[idx]);
if(sum > 0 && (sum % divisibleBy) == 0) {
return subset;
}
}
}
}
return vector<int>();
}
int main() {
for(auto i : findSubset({2,3,3,6,1}, 10))
cout << i << " ";
return 0;
}
1. Find the minimum element in Array. this will give the minimum multiple of N call it min
2. Find the sum of all elements = > This will give us maximum element of N for that array call it max
3.Apply Find all subsets of an int array whose sums equal a given target for all multiple from min to max
still O(n^2) solution, but simpler code
public static ArrayList<Integer> findSubset(ArrayList<Integer> lst){
int N = lst.size();
int[] arr = new int[N];
int i = 0,j=0;
for(; i<N;i++){
for(j=0;j<=i;j++){
arr[j] = (arr[j] + lst.get(i))%N;
if(arr[j] == 0)
return new ArrayList<Integer>(lst.subList(j, i+1));
}
}
return null;
}
public static void main(String[] args) {
ArrayList<Integer> lst = new ArrayList<>();
lst.add(1);
lst.add(2);
lst.add(1);
lst.add(4);
lst.add(5);
ArrayList<Integer> lst2=findSubset(lst);
}
That's dynamic programming problem, can be solved in O(n^2) - time with O(n^2) memory usage
import java.util.*;
import java.io.*;
public class Main{
BufferedReader in;
StringTokenizer str = null;
PrintWriter out;
private String next() throws Exception{
if (str == null || !str.hasMoreElements())
str = new StringTokenizer(in.readLine());
return str.nextToken();
}
private int nextInt() throws Exception{
return Integer.parseInt(next());
}
public void run() throws Exception{
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
int n = nextInt();
int []a = new int[n];
for(int i = 0; i < n; ++i) a[i] = nextInt();
List<Integer> first = dp(a, n);
out.println(first);
List<Integer> second = dp(a, 2 * n);
out.println(second);
out.close();
}
boolean [][]dp;
int N;
int []a;
private List<Integer> dp(int []a, int N) {
this.a = a;
int n = a.length;
this.N = N;
dp = new boolean[n][N];
dp[0][a[0] % N] = true;
for(int i = 1; i < n; ++i) {
dp[i][a[i] % N] = true;
for(int j = 0; j < N; ++j) {
dp[i][j] |= dp[i-1][j];
dp[i][(j + a[i]) % N] |= dp[i-1][j];
}
}
// for(int i = 0; i < n; ++i) {
// System.out.println(Arrays.toString(dp[i]));
// }
if (!dp[n-1][0]) return null;
List<Integer> ret = new ArrayList<Integer>();
backtrack(n - 1, 0, ret);
return ret;
}
private void backtrack(int pos, int mod, List<Integer> r) {
if (pos == 0) {
if (mod == 0) return;
r.add(a[pos]);
return;
}
if (dp[pos][mod] == dp[pos - 1][mod]){
backtrack(pos - 1, mod, r);
}else {
int nmod = mod - a[pos];
if (nmod < 0) nmod += N;
r.add(a[pos]);
backtrack(pos - 1, nmod, r);
}
}
public static void main(String args[]) throws Exception{
new Main().run();
}
}
Unfortunately I don't understand what is the difference between N and 2N case. Below 2 general solutions: 1 recursive, 1 iterative.
//Recursive solution O(N!)
//cumSum in first call equals 0
//dstSum is N or 2N
bool FindSubsetRecursive(int dstSum, int cumSum, int *pData, int N)
{
if (N == 0)
return false;
if (N == 1)
return ((cumSum + *pData) % dstSum == 0) ? true : false;
for (int i=0; i<N; i++)
{
if (FindSubsetRecursive(dstSum, cumSum + pData[i], pData+i+1, N-i-1))
return true;
}
return false;
}
//Iterative solution O(N * 2^N)
bool FindSubsetIter(int dstSum, int *pData, int N)
{
for (int i=1; i<(1<<N); i++)
{
int tmp = i, sum = 0, cnt = 0;
while (tmp > 0)
{
sum += (tmp&1) * pData[cnt++];
tmp = tmp >> 1;
}
if (sum % dstSum == 0)
return true;
}
return false;
}
This is a classic problem from Discrete Mathematics. Consider the following sums: a1, a1 + a2, a1 + a2 + a3, ..., a1 + a2 + ... + an. By pigeonhole principle, either one of these sums is exactly 0 mod n or two of these sums have the same remainder mod n. Hence, their difference will be 0 mod n.
This can be translated into a linear time algorithm which computes the sums: a1, a1 + a2, a1 + a2 + a3, ..., a1 + a2 + ...+ an. Also, at the same time computes their remainder modulo n. Then, amongst the remainders we search for 0 or two identical remainders. All of these can be done in linear time
If the array list consists of all the numbers until n. Sum of all numbers including n would be n(n+1)/2. Now, we want to find 'a' subset whose sum is a multiple of n.
When n is odd, n+1 is even, hence, the sum of all the numbers including n would be a multiple of n. Hence, the answer here is a subset with all the numbers including n.
When n is even, sum of all even numbers until and including n is (n)(n+2)/2 which again is a multiple of n. Hence, the answer here is a subset with all the even numbers until and including n.
Same approach can be followed for multiples of 2N.
1) If you make a simple recursive search, it shoul be O (N) because it is likely that amoung N numbers there will be one that is mod N 0, and if not, it is even more likely to have one with remainder N - x mod N where x any of the other number (so they compliment each other) and so on. So the search must stop in O(N) amortized time.
1.5) Is not asked, but lets say the question about devisability on number much larger than N. Than such search is simply exponential.
2) This one is tough. Each of 2N reminder can be as likely as present as not present. Having subset of one number is 50% likely. Complimenting pair is probably very likely. because if you don't find compliment for one number you are likely to find for another. That's seems like O(n^2).
EDIT: See my comment below, 2nd problem is really O (n log n)
The question doesn't say the numbers are distinct, or that they are in order, or that they are sequential. This problem is NP hard with an O(n^2) solution.
I did not say distinct, sequential, in order. On arbitrary input, amortized time complexity can be assumed. Due to the probability of the resulting subset to consist from one integer in problem 1 and from two integers in problem 2, I suggest that amortized time is O(n) in problem 1 and O(n^2) in problem 2.
If we had random integers and did int mod N, we would have distribution of 1 to N numbers whith N elements. For the 2nd problem it would be distribution of 1 to 2N numbers within N elements. Those are the numbers that you can sum up instead of originals.
On the second thought, it will be O (n log n) for the second problem. Because when we look for the pair that is 2N - int mod 2N, you are exponentially more and more likely to find it with every new int.
O(n^2) solution. Basically for each number that is 0 to N-1, we want to keep track of which subsets of the input will add up to that number after modulo N. So that's what my code does below with the HashMap, and the parameter M can actually be N or 2N.
- Sunny November 14, 2014