Frog Problem

There are stones numbered from A-K and A frog which can make a jump of one stone at a time or two stones at a time but no more than that. For example, at any point say A, the frog can jump from A-B or from A-C but not from A-D or otherwise, when it reaches J, it can only make a hop of 1 as there are no more stones after that. Frog can not jump backwards.

Now, question is how many ways can frog reach from A-K and Print all possible paths that the Frog can choose while moving from A-K?

Sol: I think, everyone knows Fibonacci's series.
Mathematically..To reach K
No. Of ways to reach K
F(K) = F(K-1)+F(K-2)
= F(J) + F(I)
= No. Of ways to reach J + No. Of ways to reach I (if K > 2)
= 1 , if K = 2 or K = 1
= 0 , if K = 0.

Lucky Number

Prob: All the numbers from 1 to infinity are written in sequence:
1,2,3,4,5,6,7,8,9,10,11,12,13,14.....
in the first iteration, every second number is removed, leaving:
1,3,5,7,9,11,13....
in the second iteration, every third number in the above sequence is
removed, thus leaving: 1,3,7,9,13....
in the third iteration, every fourth number is removed, leaving:
1,3,7,13....
like this the process goes on indefinitely.
the numbers which are, thus, left are called lucky numbers.

Write an algorithm to verify whether given a number n(can be as big as 18
digits)lucky number or not.

Sol: First n will be the nth number in the sequence. After each iteration
(intially i=2) the new position of n is calculated as n=n- (n/i) and if
n%i then u stop. this goes on until n less than i.
if n becomes less than i then n is lucky.

C-Version:

void luckyOrNot(long int n){
long int n2 = n;
int i= 2;
while(n2>=i){
if(n2%i == 0){
printf("%ld got unlucky when i was %d\n", n, i);
break;
}
n2 = n2 - (n2/i);
i++;
}
if(n2<i){
printf("%ld is lucky\n", n);
}
}

Sub Array with Large Sum in Array

Prob: Given an array int[] x of n elements , how can we find the sub-sequence that yields the maximum sum. Note that negative numbers are also present in the array.

Sol: mini = -1, minv = 0, maxi1 = 0, maxi2 = 0, maxv = -999999999;

for i=0 to length of x
{
if (i>0)
x[i] += x[i-1];

if (x[i]-minv>=maxv) {
maxv = x[i]-minv;
maxi1 = mini+1;
maxi2 = i;
}
if (x[i] minv = x[i];
mini = i;
}
}

Values of indexes will be maxi1 and maxi2