## Amazon Interview Question

Software Engineer / Developersif N is odd the (N/2 +1) non consecutive numbers are there. Else If N is even then (N/2)

Non consecutive number are there...

run selection on these non consecutive numbers using combination i.e. (N/2) C (X)

C(N-(X-1), X)

Suppose a choice is a1, a2, ..., aX.

Let a1' = a1, a2' = a2 - 1, ..., aX' = aX - (X - 1), then, a1', a2', ..., aX' is the X combination out of N - (X - 1) numbers.

On the other hand, given any choice of a1' < a2' < ... < aX' in N - (X - 1) numbers, we can get the solution a1, a2, ..., aX.

use dynamic programming

assume c(n,x) is # of ways to select x elements from the first n elements with the last element selected, then c(n,x)=sum{i=1..n-2}c(i,x-1), initial conditions are c(n,1)=1 and c(i,x)=0 for any i<2x-1. At last the total number of ways is sum{i=1..n}c(i,x)

1,2,3,4,5,6....N

1. We can pick X elements at a space of 1 ( which are odd or even numbers )

space=1, N/x times

2. We can pick X elements each spaced at 2..

space =2 N/2X times

3. We can continue to pick x lements , each element spaced at X-1. ( as long as X(X-1)<N)

space = x-1, N/2(x-1) times

so this is a summations

sum(N/px) where p varies from 1 to X-1

provided other conditions are satisfied.

if we know the value of N and X, then the solution is a geometric series

For n = 6 and x = 2,

there are 4 combinations (1, 3) (2, 4) (3, 5) (4,6), however N/x gives me only 3 combinations.

DP problem. Assume F(N,X) is number of ways to pick X from array[N] without two consecutive number.

- hyaochn September 24, 20111.We pick last one in N, F(N-2,X-1)

2.We don't pick last one in N, F(N-1,X)

add these two case we get

F(N,X)=F(N-2,X-1)+F(N-1,X)

initial condition: F(N,1)=N if N>0, F(0,X)=0, F(N,X)=0 if N<=X

Test: N=6, X=2

(1,3) (1,4) (1,5) (1,6) (2,4) (2,5) (2,6) (3,5) (3,6) (4,6) 10 combinations

F(N,X)=F(N-2,X-1)+F(N-1,X)

F(6,2)=F(4,1)+F(5,2)=4+F(3,1)+F(4,2)=7+F(2,1)+F(3,2)=9+F(1,1)+F(2,2)=10

Test: N=6, X=3

(1,3,5) (1,3,6) (1,4,6) (2,4,6) 4 combinations

F(N,X)=F(N-2,X-1)+F(N-1,X)

F(6,3)=F(4,2)+F(5,3)=F(2,1)+F(3,2)+F(3,2)+F(4,3)=2+1+1+F(2,2)+F(3,3)=4