CareerCup

DP problem. Assume F(N,X) is number of ways to pick X from array[N] without two consecutive number.
1.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

if 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)

0 if N < 2x-1
(x+1)^(N-2x+1) if N >= 2x-1

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

is the number of ways one can do..

correct if i am wrong

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

Combination minus consequtive combinations which to me sounds like (N /X) - (N-X+1)