## Amazon Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

I'm going to try to prove it... bare with me... I think the least sequence is the position of the MSB of the represented number. The reason for this is there are only two ways of incrementing the number.

1) adding the number to itself

2) adding all the numbers previous.

The quickest way to reach i is to double i with each step. Sounds like binary. The MSB of the binary representation is the corresponding number of sequences.

Take 42 for instance: MSB 101010 LSB

that means 32, 8, and 2 are asserted. So we need to create numbers add up to 32, 8 and 2 that still abide by the rules...

well we are given 1 to begin the sequence so we only need to create numbers up to 31 and 7 (32 - num's we have) ... what's 31's binary? 11111... which 7 is contained in... so we need 1, 2, 4, 8, 16, 32, 42 as the smallest subset.

I don't know how to better explain it but it's impossible to reach the target number faster than doubling each step until you have the MSB of the binary representation.

so a very simple representation

```
vector<int> findSequence (int a)
{
vector<int> ans;
for(int i = 1; i < a;)
{
ans.push_back(i);
i *= 2;
}
return (ans.push_back(i));
}
```

all of you are wrong

23= 1 2 3 5 6 11 12 23 using 1

23= 1 2 4 8 16 17 19 23 using 2

Correct Solution is

1 2 3 5 10 20 23

all of you are wrong

23= 1 2 3 5 6 11 12 23 using 1

23= 1 2 4 8 16 17 19 23 using 2

Correct Solution is

1 2 3 5 10 20 23

What are you talking about?

My solution would yield 1 2 4 8 16 23...

My solution is right.

You are wrong.

sorry my return statement should be

return ans.push_back(a);

not return ans.push_back(i);

My Approach for this problem is as bellow:

Let given Number is 'N'

Step 1: Put N in the sequence.

Step 2: If 'N' is even, put N/2 in sequence.

Step 3: if 'N' is odd then put N-1 in sequence because our sequence will contain 1 and ((N-1)+1) < (N-1), So it will stratify both the conditions.

Step 4: Repeat the Step 2 and 3 until we get 1 in the sequence.

Example:

42 => 21 => 20 => 10 => 5 => 4 => 2 => 1

My Approach is as bellow :

Step 1: Put the 'N' in the sequence.

Step 2: If 'N' is even, put N/2 in the sequence.

Step 3: If 'N' is odd, put N/2+1 and N/2 in the sequence

Step 4: take the last element in the sequence and repeat the Step 2 and 3, until we get 1 in the sequence.

Example :

42 => 21 => 11 => 10 => 5 => 3 => 2 => 1

15 => 8 => 7 => 4 => 3 => 2 => 1

15=>10=>5=>3=>2=>1

Your solution is like everyone else's, i think we need to do a recursive approach and think from the ground up

Oh for Odd number we have to take care special action.

In the previous approach if number is odd, then we are taking N/2+1 and N/2. which means our next will be N/2.

But if our odd number is divisible by 3 ( 3N => 2N + N ) then we can put 2*(N/3) and (N/3). which means, our next number will be N/3 which is less then N/2.

So the modify approach is :

if N is even then put N/2 in the list

else if N is divisible by 3 then put 2*(N/3) and (N/3)

else put N/2+1 and N/2

example :

15 => 10 => 5 => 3 => 2 => 1

27 => 18 => 9 => 6 => 3 =>2 => 1

42 => 28 => 14 => 7 => 4 => 3 => 2 => 1

This is apparently NP-Hard: Lookup addition chains on the web.

Also see wwwhomes uni-bielefeld de / achim / addition_chain.html

This is correct answer.

Some LOSER has downvoted many answers... perhaps one the other answerers.

```
#include <cstdlib>
#include <iostream>
using namespace std;
void fun(int n)
{
if(n==1)
return;
if(n%2==0)
{
fun(n/2);
cout<<" "<<n/2;
}
else
{
fun(n/2);
cout<<" "<<(n/2)+1<<" "<<n/2;
}
}
int main(int argc, char *argv[])
{
int n=2355;
fun(n);
cout<<" "<<n;
system("PAUSE");
return EXIT_SUCCESS;
}
```

I think we sould be able to solve it using BFS.

1. Consider each number i, from 1 to n, a vertex such that it has directed edges to all numbers from {i+1, ..., k} (k = 2i if 2i is less than n, else n). Weight of all these edges is 1.

2. Now run BFS starting with vertex 1, until you discover vertex n.

not all of i + 1 to 2i could be in the solution Set. And it doesnt seem to be n Square too. -1

not all of i + 1 to 2i could be in the solution Set. And it doesnt seem to be n Square too. -1

Step 1 is creating a graph for given problem. i+1 to 2i edges point to possible numbers that we can be created from number at current vertex.

For time complexity, i think i can you give a much tighter bound, i.e., O(n(n + 2)/4) => O(n^2)

Here i have tried to give you a matrix re-presentation of the graph for which we need to run BFS. If we use adjacency list representation, we get a tighter bound of O(n(n+1)/2) for BFS on this graph.

1 2 3 4 5 6 7 8 9 10

------------------------------------------

1 | 0 1 0 0 0 0 0 0 0 0

2 | 0 0 1 1 0 0 0 0 0 0

3 | 0 0 0 1 1 1 0 0 0 0

4 | 0 0 0 0 1 1 1 1 0 0

5 | 0 0 0 0 0 1 1 1 1 1

6 | 0 0 0 0 0 0 1 1 1 1

7 | 0 0 0 0 0 0 0 1 1 1

8 | 0 0 0 0 0 0 0 0 1 1

9 | 0 0 0 0 0 0 0 0 0 1

10| 0 0 0 0 0 0 0 0 0 0

```
Matrix re-loaded:
1 2 3 4 5 6 7 8 9 10
------------------------------------------
1 | 0 1 0 0 0 0 0 0 0 0
2 | 0 0 1 1 0 0 0 0 0 0
3 | 0 0 0 1 1 1 0 0 0 0
4 | 0 0 0 0 1 1 1 1 0 0
5 | 0 0 0 0 0 1 1 1 1 1
6 | 0 0 0 0 0 0 1 1 1 1
7 | 0 0 0 0 0 0 0 1 1 1
8 | 0 0 0 0 0 0 0 0 1 1
9 | 0 0 0 0 0 0 0 0 0 1
10| 0 0 0 0 0 0 0 0 0 0
```

import java.util.ArrayList;

import java.util.List;

public class Test {

public static void main(String args[])

{

Integer positivenum = new Integer(15);

Integer curr = positivenum;

List list = new ArrayList<Integer>(20);

System.out.println("Hello Java \n\n");

list.add(curr);

while(curr != 1)

// for(int k = 0 ;k<9;k++)

{

if(curr%2 == 0)

{

curr = curr/2;

list.add(curr);

}else

{

curr = curr/2 + 1;

list.add(curr);

--curr;

list.add(curr);

}

}

System.out.println("list : "+ list);

System.out.println("list : "+ list.size());

}

}

int _tmain(int argc, _TCHAR* argv[])

{

int curr = 15;

vector<int> list;

list.push_back(curr);

while(curr != 1)

{

if(curr%2 == 0)

{

curr /= 2;

list.push_back(curr);

}else

{

curr = curr/2 + 1;

list.push_back(curr);

--curr;

list.push_back(curr);

}

}

return 0;

}

public static void doList(int targetNumber, int[] list, int lim,ArrayList<Integer> ans) {

if(list[lim-1] == targetNumber) {

if(ans.size() > lim-1 || ans.size() == 0) {

System.out.print("\nAdded "+ lim);

ans.clear();

for(int i =0; i < lim ;i++) ans.add(list[i]);

}

return;

}

//Generate new lim elements from 0 to lim-1

for(int i = 0; i < lim; i++) {

list[lim] = list[lim-1] + list[i];

if(list[lim] > targetNumber) continue;

doList(targetNumber, list, lim + 1,ans);

}

}

Takes a billion years to run though. I am not sure what optimizations are possible.

```
void getSequence (int finalSum)
{
if (finalSum < 1) cout << "Invalid input, this is not allowed";
stack <int> collector;
vector <stack <int > > result;
collector.push(1);
collector.push(2);
int currentSum = 0;
//populate all the possible sequences
populateSequence (finalSum, currentSum, collector, result);
//check at least one sequence found
if (result.size() == 0) {
cout << "No valid sequence can be generated";
}
//check the smallest sequence among all and dump from the vector (result)
return;
}
void populateSequence (int finalSum, int currentSum, stack <int> &collector, vector <stack <int > > &result)
{
if (finalSum == currentSum) {
result.push_back(collector);
return;
}
if (finalSum < currentSum) {
return;
}
int first_pre = collector.top();
collector.pop();
int second_pre = collector.top();
collector.pop();
int temp_sum = first_pre + second_pre;
collector.push(second_pre);
collector.push(first_pre);
collector.push(temp_sum);
populateSequence(finalSum, temp_sum, collector, result);
collector.pop();
temp_sum = first_pre + first_pre;
collector.push(temp_sum);
populateSequence(finalSum, temp_sum, collector, result);
collector.pop();
return;
}
```

I agree the code can be optimized further .

Time Complexity (n^2)

Space Complexity (number of possible sequence * log n)

There are too many answers to read one by one. Here's my solution.

Suppose the length of the shortest solution for integer n is f(n), so:

f(n) = f(n/2) + 1 + n%2.

This is good enough to find one shortest solution. Of course there would be other ways to make it right. Please let me know if I'm wrong.

This is incorrect.

If n =15, the output is [ 1,2,3,4,7,8]

However the shortest sequence should be [1,2,4,8];

Basically we can write the number n=a +b such that a>=b

Now for all a,b combinations we have to create the sequence and keep track the minimum.

We can break it into finding the minimum sequence of a(Recusrion) and then checking if b i subset of that a. Before going ahead and checking the minimum.

Way to optimise:- Since we may create a sequence for 'a' multiple times it is better to store it in memory[ Dynamic programming].

To illustrate lets take n=7

min(7)=min(min(6) +1, min (5)+2, min(4)+3)...= 1,2,4,6,7 || 1,2 ,3,3,7|| 1,2,3,5,7|| 1,2,3,4,7

min(6)=min(min(5)+1, min(4)+2, min(3))... = min[(1,2,4,5,6) , (1,2,4,6), (1,2,3,6)]= (1,2,4,6) && (1,2,3,6)

min(5)=min(min(4)+1, min(3)+2)....= (1, 2,4,5) || (1,2,3,5)

min(4)= 1 2 4

min(3)= 1 2 3

min(2)=1 2

for shotest you have take the sum of two largest whose sum<=desire value.so every tim keep on adding last element with itself.if it exceed the last value then chek the sum of the last no with the remaining no..

- Anonymous May 02, 2012