Google Interview Question
Software DevelopersCountry: United States
Your code is flawed. If you wanted 10 and vect = {1,2,4,6,9} simply adding wouldn't do the trick.
Your code is flawed. If you wanted 10 and vect = {1,2,4,6,9} simply adding wouldn't do the trick.
This is wrong. Does not return LEAST number of additions (it returns the MOST). and N = 10 arr = {1,2,4,6,7,9} will break it.
This is wrong. Does not return LEAST number of additions (it returns the MOST). and N = 10 arr = {1,2,4,6,7,9} will break it.
Minimum floor(Log(N))+1 elements will be needed to make all 1 to N numbers using ADD operation.
2^0 = 1 (if N<=1 then required number of elements is 0+1 = 1)
2^1 = 2 (if N>=2 & N<=3 then required number of elements is 1+1 = 2)
2^2 = 4 (if N>=4 & N<=7 then required number of elements is 2+1 = 3)
2^3 = 8 (if N>=8 & N<=15 then required number of elements is 3+1 = 4)
2^4 = 16 (if N>=16 & N<=31 then required number of elements is 3+1 = 4)
I forgot to mention what exact number we need to add to get all numbers from 1 to N.
Solution is, no matter what set of numbers are given, we will need to add missing numbers from (1,2,4,8,16,32,64....so on) which is nothing but power of 2.
what about given {3,6} and N=9. According to your solution the final list will contain {1,2,3,4,6,8} while the optimal solution is {1,2,3,6}
The representation of a number as the sum of powers of two is optimal but is not the only one. If the initial list is empty or has only powers of two your approach will work otherwise is not guarantied.
No, his solution doesn't tell you what the list will contain afterwards. His solution says that you can make any number, n in [8,15], using 3+1=4 elements in the array. This is the same size as your given optimal solution. The program would then return 2 because the difference between 4 and size({3,6}) is 2.
1. Initialize a bitmap array of size N to 0. Initialize a count variable to 0.
2. Run through the power set of input array, and for every element in power set - sum all elements and set corresponding location in bitmap array.
3. Check if all indices are set in bitmap array. If yes, return count
4. Add first index set to 0 in bitmap to input array. Set this bitmap index. Increment count. Run all combinations of input array with this element - size of 2, 3.. etc and set the bitmap. Go to step 3.
Complexity: O(min(N, 2^array_size)*logN)
Memory: O(N)
Eg: N = 4, input array {}
After iteration 1: add 1. Covers 1
After iteration 2: add 2. Covers 2, 3
After iteration 3: add 4. Covers 4
O(NlogN) in this case.
That works and it results in a relatively nice piece of code in Java 8 (and Guava).
public class Solver {
public static void main(String[] args) {
int input[] = {1, 3, 8};
int n = 70;
new Solver().solve(input, n);
}
private void solve(int[] input, int n) {
BitSet bitSet = new BitSet(n + 1);
Set<Integer> solution = IntStream.of(input).boxed()
.collect(Collectors.toSet());
for (int addedCount = 0; ; addedCount++) {
for (Set<Integer> combination : Sets.powerSet(solution)) {
int sum = combination.stream().mapToInt(i -> i).sum();
if (sum <= n) {
bitSet.set(sum);
}
}
if (bitSet.cardinality() > n) {
System.out.println("Added numbers: " + addedCount);
System.out.println("Final set: "
+ Ordering.natural().sortedCopy(solution));
return;
}
solution.add(bitSet.nextClearBit(1));
}
}
}
This is the right idea. Below is working C++ implementation. Basically, we're adding elements and solving subset sum problem repeatedly until all the elements are covered. Complexity is O(N*(n+k)) where n + k is the overall length of the array including additions.
void updateSubsetSumBitmap(vector<bool> &D, int val)
{
for (int i = D.size() - 1; i >= val; i--)
{
if (!D[i] && D[i-val])
{
D[i] = true;
}
}
}
int getSmallestNumberOfAddedElements(vector<int> &A, int N)
{
vector<bool> D(N+1);
D[0] = true;
for (int v : A)
updateSubsetSumBitmap(D, v);
int added = 0;
vector<bool>::iterator pNull = D.begin();
while ((pNull = find(pNull, D.end(), false)) != D.end())
{
int ind = pNull - D.begin();
updateSubsetSumBitmap(D, ind);
added++;
}
return added;
}
void testSmallestNumberOfAddedElements()
{
vector<int> A = { 1,3,5 };
int N = 8;
int res = getSmallestNumberOfAddedElements(A, N);
}
This is the right idea. Below is the working C++ implementation. Basically, we're adding elements and solving subset sum problem repeatedly. Complexity is O(N*(n+k)) where n is the original number of array elements and k is added
void updateSubsetSumBitmap(vector<bool> &D, int val)
{
for (int i = D.size() - 1; i >= val; i--)
{
if (!D[i] && D[i-val])
{
D[i] = true;
}
}
}
int getSmallestNumberOfAddedElements(vector<int> &A, int N)
{
vector<bool> D(N+1);
D[0] = true;
for (int v : A)
updateSubsetSumBitmap(D, v);
int added = 0;
vector<bool>::iterator pNull = D.begin();
while ((pNull = find(pNull, D.end(), false)) != D.end())
{
int ind = pNull - D.begin();
updateSubsetSumBitmap(D, ind);
added++;
}
return added;
}
void testSmallestNumberOfAddedElements()
{
vector<int> A = { 1,3,5 };
int N = 8;
int res = getSmallestNumberOfAddedElements(A, N);
}
This should work:
class Solution {
public static void main(String[] args) {
int[] arr = {1, 3, 5};
System.out.println(findN(arr, 6));
}
public static int findN(int[] arr, int n) {
int res = 0;
ArrayList<Integer> al = new ArrayList<Integer>();
for (int elem : arr)
al.add(elem);
for (int i = 1; i <= n; i++) {
if (false == findX(al, i)) {
res++;
al.add(i);
}
}
return res;
}
private static boolean findX(ArrayList<Integer> arr, int x) {
return internalFindX(arr, x, new boolean[arr.size()], 0);
}
private static boolean internalFindX(ArrayList<Integer> arr, int x, boolean[] arrBool, int currSum) {
boolean b_res = false;
if (currSum == x)
return true;
if (currSum > x)
return false;
// currSum < x
for (int i = 0; i < arr.size(); i++) {
if (arrBool[i])
continue;
currSum += arr.get(i);
arrBool[i] = true;
b_res |= internalFindX(arr, x, arrBool, currSum);
if (b_res)
return b_res;
currSum -= arr.get(i);
arrBool[i] = false;
}
return b_res;
}
}
we need to have all powers of 2 that are less than N in the array, so you need to add int(log(N))+1 minus the amount of powers of 2 already in the array
Imagine [1,3,5] and N=6. We only need to add the integer 2 to the array, even though the array has no powers of 2.
My previous below solution gives only number of elements needed without even traversing the array.
Minimum floor(Log(N))+1 elements will be needed to make all 1 to N numbers using ADD operation.
2^0 = 1 (if N<=1 then required number of elements is 0+1 = 1)
2^1 = 2 (if N>=2 & N<=3 then required number of elements is 1+1 = 2)
2^2 = 4 (if N>=4 & N<=7 then required number of elements is 2+1 = 3)
2^3 = 8 (if N>=8 & N<=15 then required number of elements is 3+1 = 4)
2^4 = 16 (if N>=16 & N<=31 then required number of elements is 3+1 = 4)
Here is solution what numbers need to be added to the array.
1. add 1 at index 0 in solutionArray
2. if 1 is already there in inputArray then just increment the index of inputArray.
3. loop while solutionArray[solutionIndex]*2 < N
4. check if next element in inputArray is less than current solutionIndex value * 2.
if(true) then copy the element from inputArray
else add solutionIndex value * 2 in the solution array.
//below is the code snippet, I am considering input array is in sorted format and taking extra array to avoid shifting the elements in existing array
int solutionIndex = 0;
int inputIndex = 0;
if (N < 1)
return;
solutionArray[solutionIndex++] = 1;
if(inputArray[inputIndex] == 1)
inputIndex++;
while( solutionArray[solutionIndex]*2 < N) {
if((solutionArray[solutionIndex]*2) > inputArray[inputIndex]) {
//No new element is need to be added, just copy the element from inputArray[].
solutionArray[++solutionIndex] = inputArray[inputIndex++];
}
else {
// add Array[index]*2 in the array as next element at index+1 position
solutionArray[solutionIndex+1] = solutionArray[solutionIndex] * 2
solutionIndex++;
}
}
returnt solutionArray;
Did you test this code? If I understood your solution correctly, you are not increasing solutionIndex correctly. Lets consider a simple case when arr[] = {1, 3, 5} and N = 7,
You enter loop with solutionIndex and inputIndex both equal to 0. In first iteration, since the solutionIndex is 0, it will enter into the if condition, you are adding 1 to solution array. But since you are not incrementing solutionIndex, you will always come in the if condition and run into an infinite loop.
Observation if you already generate/process the values until M (where M < N) the next required value is sum(values in array) + 1. Eje:
Int[] a = {5, 9};
Int n = 20;
And you already processed until 5 (M = 5) so you array currently is { 1, 2, 4, 5, 9 } the sum of those values is 12 = 1 + 2 + 4 + 5 so the next required value is 13. But you need to take in consideration that can be values between 5 and 13 in this case 9; so adding 1, 2, 4 to the original array [5, 9] you can generate until 21.
public List<int> NeededValues(int[] a, int n)
{
List<int> values = new List<int>();
if (a == null || a.Length == 0)
return values;
int sum = 0;
int index = 0;
int i = 1;
while (i <= n)
{
if (index < a.Length && i == a[index])
{
sum += a[index];
index++;
}
else if (sum < i)
{
sum += i;
values.Add(i);
}
i++;
}
return values;
}
import java.util.*;
import java.util.stream.*;
public class HelloWorld{
public static void main(String []args){
int[] arr={1, 3, 3, 3} ;
int N=11;
System.out.println(getNum(arr, N));
}
public static int getNum(int[] arr, int num){
int count=0;
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
Collections.sort(list);
LinkedList<Integer> llist = new LinkedList<>(list);
for(int i=1; i<=num; i++){
if(isNumCanBeFormed(i, llist, 0, 0)){
continue;
} else{
System.out.println("current list: "+llist+"\n"+"cannot form:: "+i);
insertAtRightIndex(i, llist);
count++;
}
}
return count;
}
private static void insertAtRightIndex(int num, List<Integer> llist){
if(llist instanceof LinkedList){
int i=0;
for(; i<llist.size(); i++){
if(num<llist.get(i)){
break;
}
}
llist.add(num, i);
} else{
llist.add(num);
Collections.sort(llist);
}
}
private static boolean isNumCanBeFormed(int num, List<Integer> list, int index, int sum){
if(index>=list.size() || list.get(index)>num){
return false;
}
boolean flag =false;
for(int i=index; i<list.size(); i++){
sum +=list.get(i);
if(num==sum){
return true;
}
flag |= isNumCanBeFormed(num, list, i+1, sum-list.get(i));
}
return flag ;
}
}
Time Complexity:- O(n*2^m), where n=N and m =arr.length
here its my faster solution in dp... :D
int dp[10000][10],n;
int main(){
cin>>n;
dp[0][0]=0;
for(int i=1;i<10;i++) dp[1][i]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<10;j++){
if(j<5){
for(int k=j+4;k<10;k++)
dp[i][j]+=dp[i-1][k];
if(j==4)
{
dp[i][j]+=dp[i-1][0];
}
}
else if(j>5){
for(int k=0;k<=j-4;k++)
dp[i][j]+=dp[i-1][k];
}
else{
dp[i][j]+=(dp[i-1][0]+dp[i-1][9]+dp[i-1][1]);
}
}
}
int ans=0;
for(int i=0;i<10;i++) ans+=dp[n][i];
cout<<ans;
return 0;
}
Solve X(X+1) = 2*N , where N is given.
Number of Required Element is = ceil(X) - n , Where n is number of element in array.
By using X(X+1) = 2*N i am trying to find sum of natural numbers.
For Ex if N is 6 then x will come as 3 so we need {1,2,3} as element. By using these 3 element you can make any number from 1 to 6...
same If N = 7 then ceil of X will comes as 4. here if is impossible to get 7 if we have only {1,2,3} as element so we add new element as 4. So now by using {1,2,3,4} we can make any element from 1 to 10.
Again if number is 11 then you need to add 5 in your set. so by using {1,2,3,4,5} you can make any number form 1 to 15....
So once we got X then total number of element in array - X will give the answer.
PS: i am considering array will have all the element lower then required N.
If array have element grater then N, then after finding X we need to check set {1 to X} present in array or NOT. if any element from this set {1 to X} not present then increase the count.
The question is to find out how many numbers are required to make a sum equal to a given integer N.
The array should contain at least first x natural numbers to make this sum.
The sum can be given by sum of first x natural numbers N = x*(x+1)/2.
So to know how many numbers are required in the array solve the equation to get X.
#include <iostream>
#include <math.h>
using namespace std;
//Get the element to be added by deducting
// the lenght of the given array from (-1+sqrt(1+8n))/2
int getMinNumElementsToAdd(int lengthOfArr, int n)
{
double TotalElemReqd = ceil((-1+sqrt(8*n+1))/2) - lengthOfArr;
return TotalElemReqd;
}
int main()
{
int a[] = { 1,2,9};
int num = 10;
int lengthOfArr = sizeof(a)/sizeof(int);
int n = getMinNumElementsToAdd(lengthOfArr, num);
cout<<"Number of elements to add = "<<n<<endl;
return 0;
}
What about n=1023 and arr[]={}. It seems that we only need to add 1, 2, 4, 8,...,512 to meet the requirement.
Here is my code for this one:
1. Sort the array: O(nlgn)
2. Search the array and check the maximum No. can be reached with 1~preVal.
(1). If the No. in array is equal to preVal, update maxreach, look at next.
(2). If the No. in array is bigger than preVal, update maxreach, put this No. into result.
Python code:
def leastNo(array, N):
if array is None:
array = []
array.sort()
maxreach, preVal, index, res = 0, 0, 0, []
while maxreach < N and index < len(array):
if array[index] <= 0:
continue
if array[index] > preVal + 1:
res.append(preVal + 1)
else:
index += 1
maxreach += preVal + 1
preVal += 1
while maxreach < N:
res.append(preVal + 1)
maxreach += preVal + 1
preVal += 1
return res
testcase:
leastNo(None, 10)
[1,2,3,4]
leastNo([], 6)
[1,2,3]
leastNo([3,2,1], 10)
[4]
leastNo([3,1,4], 7)
[2]
leastNo([3,1], 6)
[2]
leastNo([8,4,2,3,1,9], 10)
[]
I don't know how to maintain white space, sorry...
Looking for better ideas~ Thanks!
Sort the numbers and traverse from starting keeping a cumulative sum of numbers found so far(including numbers added). At any point the cumulative sum value denotes the largest number that we can get by adding numbers in the array.
- Brandy August 10, 2015