Repeated Digits

Given a number with n digits.
Find whether there are repeated digits in that number.

If n > 10, return true //there are repeated digits
if n <= 10, we can create an array of size 10 and record number of entries...this wont need many resources...

Hex Format

PRINT A NO IN HEX FORMAT

int main()
{
int num,i=0,index;
char buff[17]="0123456789ABCDEF";
printf("Enter Num: ");
scanf(" %d",&num);

printf("0x");
for(i=7;i greaterThanEqualTo 0;i--)
{
index = ((num rightShift i*4)&15);
printf("%c",buff[index]);
}
printf("\n");
}

Sorting a Stack

/****
Given a stack S, write a C program to sort the stack (in the ascending
order).

We are not allowed to make any assumptions about how the stack is implemented.
The only functions to be used are:
Push
Pop
Top
IsEmpty
IsFull
****/
void recursive(Stack s)
{
if(s.isEmpty == true)
return ;
elem temp = s.pop();
recursive(s);
recur_push(temp, s);
return;
}
recur_push(elem t, stack s)
{
if(s.isEmpty == null || s.top() > t)
{
s.push(t);
return;
}
temp1= s.pop()
recur_push(t,s);
s.push(temp1);
}

Pass code Problem

/*
Problem Description
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.The main input, contains fifty successful login attempts.Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

Sample Input
Assuming 2 successful attempts (NOTE: Input would have 50)123142

Sample Output
1423
*/
int INPUT_ROW_SIZE;
int INPUT_COL_SIZE;
typedef enum
{
FALSE = -1,
TRUE = 1
}BOOLEAN;
typedef enum
{
OFF = 0,
ON = 1
}STATUS;
char **inputArray;
int **relationshipMatrix;
char *passCode;
char *uniqueArray;
unsigned int uniqueArrayIndex;
unsigned int rowSize,colSize;
unsigned int passCodeIndex;
void printInputArray(void)
{
int i,j;
printf("\n");
for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
for(j=0;j lessThan INPUT_COL_SIZE;j++)
{
printf("%2c",inputArray[i][j]);
}
printf("\n");
}
}
void printUniqueArray()
{
int i =0;
printf("Unique Array:\n");
for(i=0;i lessThan uniqueArrayIndex;i++)
{
printf("%2c",uniqueArray[i]);
}
printf("\n");
}
void printRelationshipArray()
{
int i,j;
printf("RelationshipArray\n");
for(i=0;i lessThan rowSize;i++)
{
for(j=0;j lessThan colSize;j++)
{
printf("%2d",relationshipMatrix[i][j]);
}
printf("\n");
}
}

void setUniqueArray()
{
BOOLEAN foundMatch = FALSE;
int i=0,j=0,k=0;
for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
for(j=0;j lessThan INPUT_COL_SIZE;j++)
{
foundMatch = FALSE;
for(k=0;k lessThan uniqueArrayIndex;k++)
{
if(inputArray[i][j] == uniqueArray[k])
{
foundMatch = TRUE;
}
}
if(foundMatch == TRUE)
{
continue;
}
else
{
uniqueArray[uniqueArrayIndex] = inputArray[i][j];
uniqueArrayIndex++;
}
}
}
}
void setRelationshipArray()
{
int i=0,j=0,k=0;
int rowIndex,colIndex;
relationshipMatrix = (int **)malloc(uniqueArrayIndex*sizeof(int *));
for(i=0;i lessThan uniqueArrayIndex;i++)
{
relationshipMatrix[i]= (int *)malloc(uniqueArrayIndex*sizeof(int));
}
for(i=0;i lessThan uniqueArrayIndex;i++)
{
for(j=0;j lessThan uniqueArrayIndex;j++)
relationshipMatrix[i][j]= OFF;
}

for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
for(j=0;j lessThan INPUT_COL_SIZE - 1;j++)
{
/*locate inputArray[i][j] in the uniqueArray*/
for(k=0;k lessThan uniqueArrayIndex;k++)
{
if(inputArray[i][j] == uniqueArray[k])
{
break;
}
}
if(k == uniqueArrayIndex )
{
printf("Match not found in unique Array\n");
return;
}
rowIndex = k;
/*locate inputArray[i][j+1] in the uniqueArray*/
for(k=0;k lessThan uniqueArrayIndex;k++)
{
if(inputArray[i][j+1] == uniqueArray[k])
{
break;
}
}
if(k == uniqueArrayIndex )
{
printf("Match not found in unique Array\n");
return;
}
colIndex = k;
relationshipMatrix[rowIndex][colIndex] = ON;
}
}
}
BOOLEAN matrixCorrectnessCheck()
{
int i , j=0;
for(i=0;i lessThan rowSize; i++)
{
for(j=0;j lessThan colSize;j++)
{
if((i != j )&& relationshipMatrix[i][j] == ON && relationshipMatrix[j][i] == ON)
{
printf("Invalid relation between %c and %c",uniqueArray[i],uniqueArray[j]);
return FALSE;
}
}
}
return TRUE;
}
int whichColHasAllZeros()
{
int i,j=0;
int sum = 0;
if(colSize == 0 || rowSize == 0)
{
printf("Reached the end of the input with row=%d col=%d\n",rowSize,colSize);
return FALSE;
}
for(j=0;j lessThan colSize;j++)
{
sum = 0;
for(i=0;i lessThan rowSize;i++)
{
sum= sum+relationshipMatrix[i][j];
}
if(sum == 0)
{
return j;
}
}
return FALSE;
}
void exchangeRowCol(int index)
{
char temp1=0;
int temp = 0;
int i,j;
/*exhange row of relationship matrix*/
for(i=0;i lessThan colSize;i++)
{
temp = relationshipMatrix[index][i];
relationshipMatrix[index][i] = relationshipMatrix[rowSize-1][i];
relationshipMatrix[rowSize-1][i] = temp;
}
rowSize--;
/*exhange col of relationship matrix*/
for(i=0;i lessThan colSize;i++)
{
temp = relationshipMatrix[i][index];
relationshipMatrix[i][index] = relationshipMatrix[i][colSize -1];
relationshipMatrix[i][colSize -1] = temp;
}
colSize--;
/*exhange elem for uniqueArray*/
temp1 = uniqueArray[index];
uniqueArray[index] = uniqueArray[uniqueArrayIndex - 1];
uniqueArray[uniqueArrayIndex - 1] = temp1;
uniqueArrayIndex--;
}
void setPasscodeArray(void)
{
int colIndex = 0;
passCode = (char *)malloc(sizeof(char)*uniqueArrayIndex);

while(colIndex != FALSE)
{
colIndex = whichColHasAllZeros();
if(colIndex != FALSE)
{
passCode[passCodeIndex] = uniqueArray[colIndex];
passCodeIndex++;
exchangeRowCol(colIndex);
}
}

}
void printPasscodeArray(void)
{
int i=0;
printf("Passcode Array\n");
for(i=0;i lessThan passCodeIndex;i++)
{
printf("%2c",passCode[i]);
}
printf("\n");
return;
}

void makeSmallestPasscode(void)
{
int i , j=0;
BOOLEAN retVal = FALSE;

setUniqueArray();
printUniqueArray();

rowSize = uniqueArrayIndex;
colSize = uniqueArrayIndex;

setRelationshipArray();
printRelationshipArray();
retVal = matrixCorrectnessCheck();

setPasscodeArray();
printPasscodeArray();
}
main()
{
int i = 0,j=0;
printf("Enter Row size of INPUT: ");
scanf(" %d",&INPUT_ROW_SIZE);
printf("Enter Col size of INPUT:");
scanf(" %d",&INPUT_COL_SIZE);
printf("Enter Input:\n");
inputArray = (char **)malloc(INPUT_ROW_SIZE*sizeof(char*));
uniqueArray = (char *)malloc(INPUT_ROW_SIZE*INPUT_COL_SIZE*sizeof(char));
for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
inputArray[i] = (char *)malloc(INPUT_COL_SIZE*sizeof(char));
for(j=0;j lessThan INPUT_COL_SIZE;j++)
{
printf("Enterarr[%d][%d]\n",i,j);
scanf(" %c",&inputArray[i][j]);
}
}
printInputArray();
makeSmallestPasscode();
}

Probability

You are provided with a function f() which returns either 0 or 1 with probability 1/2. Using this to construct a function f1() which returns 0 with probability 1/3 and 1 with probability 2/3.


int f1(){
while( true ){
if( f()==1 ) return 1;
if( f()==1 ) return 0;
}
}

int f1()
{
while( true)
{
int x = f();
int y = f();
if(x==1) return 1;
if(y==1) return 0;
}

}

int f1()
{
int x = 2;
while(x ==2)
{
x=f() + f();
}
return x;
}

Original array

/*
You are given an array of n numbers and each element is equal to the value of numbers less than that number in right hand side of the original array we have to find the original array
for ex. if the original array is 4,1,3,2
then we would we given the array 3,0,1,0
and we have to find the original array ,it is given that the numbers in the original array is from 1 to n.
ex no 2. original array 2,3,1,4
given array 1,1,0,0
ex no. 3 original array 5,2,1,3,4
given array 4,1,0,0,0
*/
Solution1:
main()
{
int *array;
int *value;
int *input;
int *orig;
unsigned int origIndex = 0;
unsigned int size = 0;
unsigned int sizeValue = 0;
unsigned int sizeArray = 0;
int i,j,k;
printf("Enter the size of input Array: ");
scanf(" %d",&size);
input = (int *)malloc(sizeof(int)*size);
array = (int *)malloc(sizeof(int)*size);
value = (int *)malloc(sizeof(int)*size);
orig = (int *)malloc(sizeof(int)*size);
for(i=0;i lessThan size;i++)
{
printf("Enter arr[%d]=",i);
scanf(" %d",&input[i]);
array[i] = i+1;
value[i] = i;
orig[i] = 0;
}
sizeValue = size;
for(i=0;i lessThan size;i++)
{
for(j=0;j lessThan sizeValue;j++)
{
if(input[i] == value[j])
{
orig[origIndex] = array[j];
origIndex++;
/*Shift the array and its value*/
for(k=j+1;k lessThan sizeValue;k++)
{
value[k] = (value[k] == 0)? 0: (value[k]-1);
}
for(k=j;k lessThan sizeValue-1;k++)
{
array[k] = array[k+1];
value[k] = value[k+1];
}
sizeValue--;
break;
}
}
}
printf("\n");
for(i=0;i lessThan size;i++)
printf("%2d",orig[i]);
printf("\n");
}



Solution2:
Let us assume that output has n elements.
We init an array say helperArray[i] = i; for i from 1 till n
Also have an outputArr[] which is init to 0.

Now take the input array inputArr[].
Step1. Check what is inputArr[i] let it be k.
Step2. Then we ask this qn what is the number which has exactly k lesser elements than itself. For this we check the helperArray[] and find the element from there. Let that element be helperArray[j]. Now strike of this element and do the above step again. But we dont take the striked off elements into considerations.

We take a simple example
let input 4 1 0 0 0
output 0 0 0 0 0
helper 1 2 3 4 5

Iteration1: k = 4 then output[0] = 5 as number which has 4 less numbers is 5
strike of 5 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 0 0 0 0
helper 1 2 3 4

Iteration2: k = 1 then output[1] = 2 as number which has 1 less numbers is 2
strike of 2 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 0 0 0
helper 1 3 4

Iteration3: k = 0 then output[2] = 1 as number which has 0 less numbers is 1
strike of 2 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 0 0
helper 3 4

Iteration4: k = 0 then output[3] = 3 as number which has 0 less numbers is 3
strike of 3 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 3 0
helper 3 4

Iteration5: k = 0 then output[4] = 4 as number which has 0 less numbers is 4
strike of 4 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 3 4
helper

Next Power of 2

Given a number N, find out the nearest power of 2 which is greater than or equal to N..

int Closest(int x)
{
int higher = 1;
int orig = x;
while( x greaterThan 0 )
{
x = x rightShift 1;
higher = higher leftShift 1;
}
if(orig * 2 == higher)
return orig;
else
return higher;
}

Open Nth File

I have a program that has to output some data to
different files each having a unique filename like :

file01.dat , file02.dat, file03.dat ,.......

my question is how can you use fopen to do this job?

FILE *fopenNth(int n) /* 0 lessThanEqualTo n lessThan 100 ! */
{
char * name = "file00.dat";
name[4]+=n / 10;
name[5]+=n % 10;

return fopen (name, "w");
}

Row with Maximum 0s

/***
There is a 2D nxn array of 0's and 1's. Each and every row is sorted.
Now you have to report the row with max no. of zeros in O(n) time.
***/
void rowWithMaxNumberOfZeros(int **arr,int r,int c)
{
int i=0,j=0;
int optRow=0,optCol=c-1;
int found = 0;
for(j=0;j lessThan c;j++)
{
if(arr[0][j] == ONE)
{
optCol = j-1;
found = 1;
break;
}
}
if(found == 0 && j ==c)
{
optCol=c-1;
}
i++;

while(i lessThan r && (optCol+1) lessThan c)
{
if(arr[i][optCol+1] == ZERO )
{
found = 0;
for(j=optCol+1;j lessThan c;j++)
{
if(arr[i][j] == ONE)
{
found = 1;
optCol = j-1;
optRow = i;
break;
}
}
if(found == 0 && j ==c)
{
optCol=c-1;
optRow = i;
}
}
i++;
}
printf("Row containg max number of zeros is %d till this column %d\n",optRow,optCol);
}

Longest Palindrome

Write a program which finds the longest palindrome in a given string of characters.
/******
Assumption1.
===========
So if it were of even length then the centre would be i and i+1 for example
KaaK
0123
so centers are 1,2
but for a odd length palindrome the centers are one and the same as in
KapaK
01234
so centers are 2,2

Assumption2:
============
If two strings have the same center and smaller one is not a palindrome then bigger can't be a palindrome

for example:abcddeba
index willb:01234567
since str[3,4] is a palindrome then [2,5] may be a palindrome
but since str[2,5] is not a palindrome [1,6] can't become palindrome.

Logic:
======
Here i take every index in the array as the center of the palindrome.
Now first loop searches for odd lenght palindromes in the string.
Taking the first 0,0 as the centers we try to expand our palindrome till we
encounter the boundaries or a mismatch. In such a way we can eliminate all
the strings with the same base which are not palindromes.

******/

void longestPalindrome(char *input)
{
int len;
int i=0,j=0,k=0,l=0;
int lower=0,upper=0;
len = strlen(input);

/*Odd length Palindromes*/
while(i lessThan len && j lessThan len)
{
k=i;
l=j;
while(( k greaterThan =0 && l lessThan len) && (input[k] == input[l]))
{
if((upper - lower) lessThan = (l-k))
{
lower=k;
upper=l;
}
k--;
l++;
}
i++;
j++;
}

/*Even length Palindromes*/
i = 0;
j = 1;
while(i lessThan len && j lessThan len)
{
k=i;
l=j;
while(( k greaterThan =0 && l lessThan len) && (input[k] == input[l]))
{
if((upper - lower) lessThan = (l-k))
{
lower=k;
upper=l;
}
k--;
l++;
}
i++;
j++;
}

for(i=lower;i lessThan =upper;i++)
{
printf("%c",input[i]);
}
printf("\n");
}

How many possible Brackets?

/******
Given a number n, print all possible combinations of n pairs of braces that are balanced
I/P:1
O/P:
()

I/P:2
(())
()()

I/P:3
O/P:
((()))
(()())
(())()
()(())
()()()

I/P:4
O/P:
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

******/
int lbCount;
int rbCount;
void printLeftBrace(int index);
void printRightBrace(int index);
void printLeftBrace(int index)
{
int i = 0;
int lbLoc ,rbLoc ;
lbCount--;
temp[index] = ')';
if( lbCount == 0 && rbCount == 0)
{
printf("%s\n",temp);
return;
}
for(i=0;i lessThan 2;i++)
{
if(i==0)
{
if(rbCount greaterThan 0)
{
lbLoc = lbCount;
rbLoc = rbCount;
printRightBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;

}
}
else
{
if(rbCount lessThan lbCount)
{
lbLoc = lbCount;
rbLoc = rbCount;
printLeftBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;
}
}
}
}
void printRightBrace(int index)
{
int i = 0;
int lbLoc ,rbLoc ;
if(rbCount greaterThan 0)
{
temp[index] = '(';
rbCount--;
}
for(i=0;i lessThan 2;i++)
{
if(i==0)
{
if(rbCount greaterThan 0)
{
lbLoc = lbCount;
rbLoc = rbCount;
printRightBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;
}
}
else
{
lbLoc = lbCount;
rbLoc = rbCount;
printLeftBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;
}
}
}
main()
{
lbCount = 0;
rbCount = 0;

printf("Enter the Number of Braces: ");
scanf(" %d",&rbCount);
lbCount = rbCount;
temp = (char *) malloc((rbCount+lbCount+1)*sizeof(char));
memset(temp,0,sizeof(temp));
printRightBrace(0);
}

N Sorted Arrays

Given n streams of sorted data (each of which can be infinite in length). Give an efficient way to merge them to give a single sorted stream..

Best method would be to store all the streams in a heap. With each node in the heap having the head value of the stream. So when we pop out one element from the heap. We push back the stream with the head removed and pushing the next element as the head. This way we can merge the streams quickly.

Majority element

/********
A majority element in an array A, of size N is an element that appears more than N/2 times (and hence there is atmost
one such element)

Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:

I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE

Answer:

As we sweep through the sequence, we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0. When we move the pointer forward over an element e:
If the counter is 0, we set the current candidate to e and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate. When we are done, the current candidate is the majority element, if there is a majority.
If you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it.
******/
int find_majority(int *a, int n)
{
int count = 1;
currentIndex = 0;
for (i = 1 ; i lessThan n; i ++)
{
if (a[i] == a[currentIndex])
count++;
else
count--;
if (count == 0)
{
currentIndex = i;
count = 1;
}

}
return a[currentIndex];
}

Multiple of 8

using bit manipulation, find next multiple of 8 for a given number

int nextMultipleOfEight(int num)
{
i = i rightShift 3;
i++;
i=i leftShift 3;
printf("%d\n",i);
}

Maximum Sub Array Sum

/***
Input Array has both +ve and -ve ints.
Find the sub array with maximum sum.

Solution:
Run Time : O(n)
Assumes that whenever thisSum is less than 0 then we can get a better sum from the index following the current one.
***/
int maxSubSum3( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
int i=0;
int j=0;

while (j lessThan a.length)
{
if(a[j] lessThan 0)
{
thisSum = 0;
j++;
continue;
}
thisSum =thisSum + a[ j ];

if( thisSum greaterThan maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if( thisSum lessThan 0 )
{
i = j + 1;
thisSum = 0;
}
j=j+1;
}

return maxSum;
}

Other Solution

Reverse Stack

/****
Reverse a stack with recursion...u have only pop, push, size,isEmpty functions
****/
void recursive(Stack s)
{
if(s.isEmpty == true)
return ;
elem temp = s.pop();
recursive(s);
recur_push(temp, s);
return;
}
recur_push(elem t, stack s)
{
if(s.isEmpty == null)
{
s.push(t);
return;
}
temp1= s.pop()
recur_push(t,s);
s.push(temp1);
}

Merge with a twist!!

/***
Given a array of size M+N in which first M numbers are sorted and last N spaces are vacant. Another array of size N which is sorted. Now merge these two arrays without using any extra space so that the array of M+N size is sorted. Optimize it to hav complexity M+N.
***/

#include
#define M 10
#define N 5
void printArr(int *arr1,int *arr2)
{
int i,j;
printf("\n");
printf("Arr1 Elements\n");
for(i=0;i lessThan M+N;i++)
{
printf("%3d",arr1[i]);
}
printf("\n");
printf("Arr2 Elements\n");
for(i=0;i lessThan N;i++)
{
printf("%3d",arr2[i]);
}
printf("\n");
}
main()
{
int arr1[M+N] = {0};
int arr2[N] = {0};
int i = 0, j =0,temp=0,k=0;
printf("Arr1 Elements\n");

for(i=0;i lessThan M;i++)
{
printf("arr1[%d] = ",i);
scanf(" %d",&arr1[i+N]);
}
printf("Arr2 Elements\n");
for(i=0;i lessThan N;i++)
{
printf("arr2[%d] = ",i);
scanf(" %d",&arr2[i]);
}
printArr(arr1,arr2);
j = 0;
i = N;
k = 0;
while(i lessThan M+N && j lessThan N)
{
if(arr1[i] lessThan arr2[j])
{
arr1[k]=arr1[i];
k++;
i++;
}
else if(arr1[i] greaterThan arr2[j])
{
arr1[k] = arr2[j];
k++;
j++;
}
else
{
arr1[k] = arr2[j];
k++;
j++;
arr1[k] = arr1[i];
k++;
i++;
}
}
while(i lessThan M+N && k lessThan M+N)
{
arr1[k]=arr1[i];
k++;
i++;
}
while(j lessThan N && k lessThan M+N)
{
arr1[k]=arr2[j];
k++;
j++;
}
printArr(arr1,arr2);
}

Little / Big Endian

/***
A program to find if a machine is big or little endian.
***/
#include
main()
{
int i = 1;
char *p= (char *)&i;

if(*p == 1)
printf("Little");
else
printf("Big");
printf(" Endian\n");
}

Rotate Array

/***
Rotate the array about an index k.
So if the input was 0 1 2 3 4 5 6
rotating the array about index = 2the o/p would be
3 4 5 6 0 1 2
***/
First, reverse the order of the elements in the whole list:
{xn, xn-1, ..., x1}

Then reverse the sublist containing the last k-1 elements, and then also the sublist containing the other n-k+1 elements:

{xk, xk+1, ..., xn, x1, ..., xk-1}

To illustrate rotating a list of n=5 elements so that k=4 is first:

1 2 3 4 5
reverse list:
5 4 3 2 1
break into sublists and reverse:
5 4 3 2 1
4 5 1 2 3

Each reversal is clearly O(n) and the swapping requires some small constant amount of storage.

Array flip

Write a function that will flip the n*n array about its non major diagonal.
Example 3 5 7 makes the non major diagonal in the following manner.
1 2 3 --- 9 6 3
4 5 6 --- 8 5 2
7 8 9 --- 7 4 1

#define N 10
main()
{
int arr[N][N] = {0};
int i=0,j=0,k=1,temp=0;
printf("\n");
initializeArray(arr,N);
for(i = 0; i lessThan N ; i++)
{
for(j = 0 ; j lessThan N-i-1; j++)
{
temp = arr[i][j];
arr[i][j] = arr[N-1-j][N-1-i];
arr[N-1-j][N-1-i] = temp;
}
}
printf("\n");
printArray(arr,N);
}

Tree sum

/***
Given a tree and a sum, write an algorithm to return TRUE if there is a path from the root node down to a leaf such that adding all values of the nodes along the path equals the given sum.
***/

BOOLEAN rootToLeafSumEqualsInput(NODE *root,int sum)
{
if(root.left == NULL && root.right == NULL)
{
if(root.value == sum)
{
printf root.value;
return TRUE;
}
else
return FALSE;
}
if(root.left != NULL)
{
if(rootToLeafSumEqualsInput(root.left,(sum - root.value)) == TRUE)
{
printf root.value;
return TRUE;
}
}
if(root.right != NULL)
{
if(rootToLeafSumEqualsInput(root.left,(sum - root.value)) == TRUE)
{
printf root.value;
return TRUE;
}
}
}

Arrays Extra Element

/***
Given two arrays A and B. Array 'A' contains all the elements of 'B' but
one more element extra.
Find out the extra element......
Restrictions: Dont use any relational ops ( > or > or == etc....), array
elements are not in order ...,
***/
main()
{
int A[]={1,4,2,4,5};
int B[]={1,4,2,4};
int sa=5,sb=4;
int sumA=0;
int sumB=0;
int i=0;

for(i=0;i lessThan sa;i++)
{
sumA+=A[i];
}
for(i=0;i lessThan sb;i++)
{
sumB+=B[i];
}

printf("%d\n",sumA-sumB);
}

0s to Left 1s to the Right

Given an array with random 0,1 ,sort 0's to left and 1's to right???
in time complexity O(n)..

main()
{
int i = 0;
int arr[]={1,1,0,1,0,1,0,0,1};
int size = 9;
int oneP=0;
int zeroP=0;
while(oneP lessThan size && zeroP lessThan size)
{
if(arr[zeroP] == 0 )
{
zeroP++;
oneP++;
continue;
}
if(arr[oneP] == 0)
{
arr[zeroP] = 0;
arr[oneP] = 1;
zeroP++;
}
oneP++;
}
for(i=0;i lessThan size;i++)
printf("arr[%d]= %d\n",i,arr[i]);
}

ZigZag

Problem Statement
A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

import java.util.Random;
class ZigZag
{
static void print(int[] arr)
{
System.out.println();
for(int i=0;i lessThan arr.length;i++)
{
System.out.print(" "+arr[i]);
}
System.out.println();
}
public static void main(String[] args)
{

int[] arr ={ 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5,1000,32,32};
int n=arr.length;
int[] numb = new int[n];
int sign=0;
int i=0;
Random r=new Random();
numb[0]=1;
numb[1]=1;
if(arr[0]!=arr[1])
numb[1]=2;
print(arr);
for(i=2;i lessThan n;i++)
{
sign=arr[i-1]-arr[i-2];
print(numb);
if(sign==0 || arr[i]==arr[i-1])
{
numb[i]=numb[i-1];
continue;
}
if(sign lessThan 0 && arr[i]-arr[i-1] greaterThan 0)
{
numb[i]=numb[i-1]+1;
continue;
}
if(sign greaterThan 0 && arr[i]-arr[i-1] lessThan 0)
{
numb[i]=numb[i-1]+1;
continue;
}
if(sign lessThan 0 && arr[i]-arr[i-1] greaterThan 0)
{
numb[i]=numb[i-1];
continue;
}
if(sign lessThan 0 && arr[i]-arr[i-1] lessThan 0)
{
numb[i]=numb[i-1];
continue;
}

}
print(numb);
}
}

Group Characters Together in Order

/**
Input will be a string. We need to o/p a string with the order of characters same as the input but with same characters grouped together.
I/P: abcdacde
O/P: aabccdde

I/P: kapilrajadurga
O/P: kaaaapilrrjdug

I/P: 1232
O/P: 1223
**/
I have found out two methods:
Method 1:
/**
Running Time: O(n*n*n)
Here we take one char see if there are any characters which equal it. If any two characters are equal we shift the array by 1 to the right(from the character till the first match) . and keep the matching element in that blank.
For example:
I/P: abcdead
Iteration 1: a bcded
Iteration 2: aabcded
Iteration 3: aabcded
Iteration 4: aabcded
Iteration 5: aabcd e
Iteration 6: aabcdde
Here Blank places mean that we shifted the array from that point till the first match from that point.

**/
main(int argc,char **argv)
{
int i = 0,j=0,k = 0;
int length = 0;
char *inputPtr;
char input[MAX_ALPHABET_LENGTH]={0};
int temp[MAX_ALPHABET_LENGTH]={0};
if(argc lessThan 2)
{
printf("Enter the input String as command line argument\n");
return;
}
strcpy(input,argv[1]);

inputPtr = input;
length = strlen(argv[1]);
printf("Method 1:\n");
printf("I/P: %s\n",inputPtr);

for(i=0;i lessThan length;i++)
{
for(j = i+1;j lessThan length; j++)
{
if(inputPtr[i] == inputPtr[j])
{
for(k = j; k greaterThan i; k-- )
{
inputPtr[k] = inputPtr[k-1];
}
inputPtr[i+1]=inputPtr[i];
}
}
}
printf("O/P: %s\n",inputPtr);

}
Method 2:
/**
Running Time: O(n) with O(1) constant space.
Here i am making the following assumption
1. The character set is limited to 256 characters.

Here we deploy hashing for this:
We have a bucket for 256 characters.
Step 1: We init the bucket to 0.
Step 2: We traverse through the input String and increment the corresponding bucket.
Step 3: We then traverse through the whole input array and check the order of the characters. So once we have printed the input character bucket[character] times then we make the bucket entry for that character to 0.

Though the last for loop seems to be O(n*n) actually it is O(n) only.
**/
main(int argc,char **argv)
{
int i = 0,j=0,k = 0;
int length = 0;
char *inputPtr;
char input[MAX_ALPHABET_LENGTH]={0};
int temp[MAX_ALPHABET_LENGTH]={0};
if(argc < 2)
{
printf("Enter the input String as command line argument\n");
return;
}

printf("Method 2:\n");
strcpy(input,argv[1]);
inputPtr = input;
length = strlen(argv[1]);
printf("I/P: %s %d\n",inputPtr,length);
for(i = 0; i lessThan length; i++)
{
temp[inputPtr[i]]++;
}
printf("O/P: ");
for( i = 0; i lessThan length ; i++ )
{
for(k=0; k lessThan temp[inputPtr[i]]; k++)
{
printf("%c",inputPtr[i]);
}
temp[inputPtr[i]]=0;
}
printf("\n");
}

First repeating element

/*
How will u find the first repeating letter in a string?... Remember solution should be efficient in both time and space...

Example:
abcdabccccaab
Reapeating letters are: a, b, c
take an auxilary array of 256 ...O(n) complixity in time also
*/

#define MAX 500
int main()
{
char arr[MAX],aux[256];
int i,j;
for(i=0;i lessThan 256;i++)
aux=0;
scanf("%s",arr);

for(i=0;i lessThan j;i++)
if(aux[arr[i]])
{
printf("The repeting character is %c",arr);
break;
}
else
aux[arr[ i]]++;
return ;
}

Index Same As Element

Suppose that you are given a sorted sequence of distinct integers{a1,a2,...an} . Give an O(log(n)) algorithm to determine whether there exists an index i such at ai = i . For example, in arr[]={-1,0,3,6,7} since arr[3] == 3 the solution should be three.

Solution
We do a binary search for the array. Compare the index of the curr element(ind) and the current elements(arr[ind]). If the ind is less than arr[ind] then match can be found only in the lower half(since all elements are distict). Similarly if ind is greater than arr[ind] then match can be found in the upper half. If Equal then match is found.

pseudo code

int matchIndToElem(int arr[], int size)
{
low = 0;
upper = size - 1;
mid = (low+upper)/2;
while(low < upper)
{
if( mid == arr[mid])
{
printf("Match Found at index %d",mid);
return mid;
}
else if( mid < arr[mid])
{
low = low;
upper = mid;
mid = (upper + low)/2;
}
else
{
low = mid;
upper = upper;
mid = (upper +low)/2;
}
}
if(arr[low] == low)
{
printf("Match Found at index %d",low);
return low;
}
return -1;
}

Median

/*********************************************
X[1...n] and Y[1....n] are 2 sorted arrays....
give O(log n) algo to find median of the array
formed by merging the 2 arrays
*********************************************/

/***
Take the middle of Arr X call it midX and middle element of
Arr Y call it midY..
***/
int findMedian(Array arrX[])
{
lowX=0
lowY=0
highX=arrX.size - 1
highY=arrY.size - 1

midX = (highX - lowX)/2
midY = (highY - lowY)/2
while(lowX != highX || lowY !=highY)
{
if(midX < midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowX=midX
highY=midY
midX = midX + (highX - lowX)/2;
midY = (highY - lowY)/2;
**/
}
else if (midX > midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowY =midY
highX=midX
midY = midY + (highY - lowY)/2;
midX = (highX - lowX)/2;
**/
}
else
{
printf("median %d",arrX[midX]);
return arrX[midX];
}
}
return arrX[midX];/*or return arrY[midY]*/
}

Rotate one to get Another

/****************************************
Given a string s1 and a string s2,
write a snippet to say whether s2 is a
rotation of s1?

Solution:
concatenate s1 with s1 and do a search
for s2 in that. If found then s2 is a
rotation of s1.
****************************************/
int isRotation(char *s1,char *s2)
{
strcat(s1,s1);
if((temp = strstr(s1,s2))!= NULL)
{
if(strcmp(s1,temp)!= 0)
{
printf("s2 is a rotation of s1 and vice versa\n");
return 1;
}
}
return 0;
}

Distance[2]

/***
You are given 2 pointers to two nodes (p1, p2) in a binary tree. Devise an algorithm to find the distance between p1 and p2 (i.e. the length of the shortest path between them).
***/

Trace back to the top of the tree from each node, recording the left and right subtrees as 0 and 1 in a binary string. Compare the binary strings. The sum of the lengths of the two minus twice the length of the common parts at the end gives the distance.

Distance[1]

/***
You are given 2 pointers to two nodes (p1, p2) in a binary search tree. Devise an algorithm to find the distance between p1 and p2 (i.e. the length of the shortest path between them).
***/
take ln as the lowest value node, and hn as the high value node,cn has the current node

Node cn=ln;
int c=0;
while (cn != root && cn.parent < hn)
cn = cn.parent
c++;
endwhile
while (cn != hn)
cn = cn > hn ? cn.left : cn.right;
c++;
endwhile

Nth Element from end SLL

/*
How to find nth element from end of a single linked list.
*/
list_ptr *p1, *p2;

p1 = p2 = list.head

for( i = 0; i < n; ++i )
p2 = p2->next;

while( p2 )
{
p1 = p1->next;
p2 = p2->next;
}

C or C++

Write a program that will print "C" if compiled as an (ANSI) C program, and "C++" if compiled as a C++ program.

$cat a.c
#include

int
main ()
{
char ch[][5]={"C++","C"};
printf ("%s \n",ch[( 2 //*
/ 2) -1] // */ 1) -1]
);
return 0;
}

$cc a.c ; ./a.out ????
$cc -ansi a.c ; ./a.out ????
Contributed by -KC

Permutations!!

/**********************************************************************************
A program to find out all possible Permutations.
If I/P is 3 then o/p is
Permute[ 0] 1 2 3
Permute[ 1] 1 3 2
Permute[ 2] 2 1 3
Permute[ 3] 2 3 1
Permute[ 4] 3 2 1
Permute[ 5] 3 1 2
**********************************************************************************/

void permute(int i)
{
int j=0,k=0,temp=0;
if(i == size)
{
return;
}
for(j = i; j < size; j++)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
permute(i+1);
if(i == size - 1)
{
printf("Permute[%3d]",count++);
for(k = 0;k< size;k++)
printf(" %3d ",arr[k]);
printf("\n");
}
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
main()
{
int i = 0;
size = 3;
count = 0;
arr = (int *)malloc(size*sizeof(int));
for(i=0;i arr[i] = i+1;
permute(0);
}

8 Queens Problem

/**********************************************************************************
A program to generate all possible positions of keeping maximum queens on a n*n chess board with neither of them attacking each other.
***********************************************************************************/
void generateCases(int row)
{
int col = 0;
BOOLEAN retVal = FALSE;
if(row greaterThanEqualTo SIZE)
{
return;
}
for(col = 0 ; col lessThan SIZE; col++)
{
/**************************************
This function will check if the new
queen(row,col) can be placed in the
board. Returns true if we can.
***************************************/
retVal = validatePosition(row,col,QUEEN);
if(retVal == TRUE)
{
piecePositions[size_g].row = row;
piecePositions[size_g].col = col;
size_g++;
if(row == SIZE-1)
{
printBoard();/*Prints the board*/
count_g++;
}
generateCases(row+1);
size_g--;
}
}
}

main()
{
int r = 0;
INIT_GLOBALS();
size_g=0;
memset(piecePositions,0,sizeof(piecePositions));
generateCases(0);
}

Map of India

/*how this works? I dont know..*/
#include
main()
{
int a,b,c;
for (c=b=10;a=
"VAMSI PERI,TFy!QJu ROo TNn(ROo)SLq SLq ULo+ UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^ NBELPeHBFHT}TnALVlBLOFAkHFOuFETp HCStHAUFAgcEAelclcn^r^r\\tZvYxXy T|S~Pn SPm SOn TNn ULo0ULo#ULo-W Hq!WFs XDt!" [b++];)

for(; a-- > 64 ; )
putchar ( ++c==90 ? c=10:33^b&1);

}

Decimal to Roman

Write a function to convert a number to its equivalent roman numeral value. You have to convert only numbers < 1000. Analyze the runtime. (This was really hard, and I fluffed my way through it.)


char* u2roman(unsigned n)
{
static char* roman_digits[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
static char* roman_tenths[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
static char* roman_hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
static char buf[13]; // Max length is 12 symbols
int cnt;

if (n >= 1000) return 0;

cnt = sprintf(buf, "%s", roman_hundreds[ n / 100 ]);
cnt += sprintf(buf + cnt, "%s", roman_tenths[ n / 10 ]);
sprintf(buf + cnt, "%s", roman_digits[ n % 10 ]);

return buf;
}

Array[3][3]

Sort a 2d array(m*n). Such that if we print the array in zigzag manner you get the sorted array(first row than second row and so on..). The array being such that each of its rows and its cols are in increasing order
e.g
I/P:
2 4 5
3 6 8
5 7 9

O/P:
2 3 4
5 5 6
7 8 9

Solution :
O(m*n*log(n))
Since the rows are sorted we can do this...
Take Row[0] and Row[1] merge them, Row [2] Row[3] merge them.....
so the tree looks like this.... Row[i,j] implies that Row[i] through Row[j] are sorted(i.e if we go from Row[i][0] till Row[j][n-1] it will be in sorted manner)...
___________________________Row[0,n-1]
___________________________/______.
.
.
___________/______________\___________
______Row[0,1]___________Row[2,3]_________________Row[n-2,n-1]
_____/________\________/_________\________________/__________Row[0]____Row[1]___Row[2]___Row[3]_____________Row[n-2]___Row[n-1]

This is similar to To merge sort of m*n elements only differernce is that we already have sorted arrays and thus we reduce the height of our merge tree....

Set Operations

Set Operations on Array
U - Universal Set
A - Subset
B - Subset

1. Union - All elements in A or B.
2. Intersection - All elements in A and B.
3. Minus - All elements in A but not in B.
4. Complement - All elements in U - A.

If the A, B, U are sorted
1. Union
Do a merge of A and B. If we get two elements with same value then take one of them and proceed.
i=0;
k=0;
j=0;
while(i lessThan n && j lessThan n)
{
_____if(A[i] lessThan B[j])
_____{
__________C[k] = A[i];
__________i++;
__________k++;
_____}
_____else if(A[i] greaterThan B[j])
_____{
__________C[k] = B[i];
__________j++;
__________k++;
_____}
_____else
_____{
__________C[k] = A[i];
__________j++;
__________k++;
__________i++;
_____}
}
while(i lessThan n)
{
__________C[k] = A[i];
__________i++;
__________k++;
}
while(j lessThan n)
{
__________C[k] = B[j];
__________j++;
__________k++;
}

2. Intersection
Normal Merge of A and B.
A[0,n-1] B[0,n-1]
Assuming that since these arrays represent sets we dont have any repeating elements
i=0;
k=0;
j=0;
while(k lessThan n && i lessThan n && j lessThan n)
{
_____if(A[i] == B[j])
_____{
__________print A[i];
__________i++;
__________j++;
__________k++;
_____}
_____else if(A[i] lessThan B[j])
_____{
__________i++;
_____}
_____else
_____{
___________j++;
_____}
}

3. Minus
C = A - B

while(k lessThan n && i lessThan n && j lessThan n)
{
_____if(A[i] == B[j])
_____{
__________i++;
__________j++;
_____}
_____else if(A[i] lessThan B[j])
_____{
__________C[k] = A[i];
__________k++;
__________i++;
_____}
_____else
_____{
___________j++;
_____}
}
if(j greaterThanEqualTo n)
{
_____while(k lessThan n && i lessThan n)
_____{
__________C[k]=A[i];
__________i++;
__________k++;
_____}
}

3. Complement
Same as Minus. complement(A) = U - A

Array[1]

Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's say they are decreasingly sorted), we define a set S = {(a,b) | a \in A and b \in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n) algorithm.

Logic:
Take the two arrays and Take a maximal heap...
Now add into heap the first element (A[0]+B[0])...
Now Remove the maximum from the heap...And Print i...
Now if the removed element was (A[i]+B[j]) then push (A[i+1]+B[j]) and (A[i]+B[j+1])...
Do this until you get n elements...
Answer Contributed by f2001840

Array[0]

There is an array of size n storing numbers between 0 to n-3 and 2 of the nums repeated. Find both of them.

Example:
I/P: 0 1 2 1 2 3
O/P: 1 2

This solution is generic for finding if there are any repeats in the array.

Solution:
for(i=0;i lessThan n; i++)
{
swap(arr[i], arr[arr[i]]);
if(i != arr[i] && arr[arr[i]] EQ arr[i])
print "found %d", arr[i]

}
Question And Answer Contributed by f2001389

Xor linked list

How to Maintain a double linked list using a single linked list?

Xor linked lists are a curious use of the bitwise exclusive disjunction (XOR) operation to decrease storage requirements for doubly-linked lists. An ordinary doubly-linked list stores addresses of the previous and next list items in each list node, requiring two address fields:

... A-1 A B C C+1 ...
<– prev <– prev <– prev <–
–> next –> next –> next –>
An Xor linked list compresses the same information into one address field by storing the bitwise XOR of the address for previous and the address for next in one field:

... A-1 A B C C+1 ...
–> A-1 XOR B <–> A XOR C <–> B XOR C+1 <–
When you traverse the list from left to right: supposing you are at B, you can take the address of the previous item, A, and XOR it with the value in the XOR field. You will then have the address for C and you can continue traversing the list. The same pattern applies in the other direction.

To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one. If the addresses of the two consecutive items are reversed, you will end up traversing the list in the opposite direction.

This particular trick is generally discouraged for several reasons:

general-purpose debugging tools cannot follow the XOR chain, making debugging more difficult;
the price for the decrease in memory usage is an increase in code complexity, making maintenance more expensive; and
conservative garbage collection schemes do not work with data structures that do not contain literal pointers.
Also, modern computer systems usually have cheap and plentiful memory, so storage overhead is not normally an issue outside specialised embedded systems. Where it is still desirable to reduce the overhead of a linked list, unrolling provides a more practical approach (as well as other advantages, such as increasing cache performance and speeding random accesses).

Infinite Bit Stream Problems

All such Problems we cannot store the input strings. For all such questions which require computation on infinite Bit Streams we use a FSM(Finite State Machine). Let us discuss some such problems.

1. Find out remainder when the given bit stream is divided by 2.
Input : 010
Output: 0

Input : 0101
Output : 1

Solution:
Design an FSM in which u have states as remainder. So for 2 we can have only two possible remainders 0 or 1.

Now start with a state 0. Be in this state till u get a 1. If in 1 you get a zero then move to state 0 this looks something like this. The end state will give us the remainder.





Similarly we can apply the same logic to find the remainder when the number is divided by 3...(Remainder can be 0,1,2)


In General:

If you are finding the remainder of a bit stream when divided by N then...
if you are in state A. then

CASE 1: Input is 0
nextState = (A * 2 + 0) % N

CASE 2: Input is 1
nextState = (A * 2 + 1) % N

When u reach the end of the i/p you state is the remainder....

Code
/*************************************************************
arr contains the input. arr will contain 0/1....
**************************************************************/
unsigned int findRemainder(int arr[],int len, int divisor)
{
int i=0;
int currState = 0;
while(i lessThan len)
{
currState = (currState * 2 + arr[i]) % divisor;
i++;
}
return currState;
}
/************************************************************************
-numberSystem if 2 then input string contains 0/1...
-numberSystem if 10 then input string contains 0/1/2/3/4/5/6/7/8/9
-arr contains the input. arr will contain [0,9]
*************************************************************************/
unsigned int findRemainder(int arr[],unsigned int numberSystem,int len, int divisor)
{
int i=0;
int currState = 0;
while(i lessThan len)
{
currState = (currState * numberSystem + arr[i]) % divisor;
i++;
}
return currState;
}

Bubble Sort/Insertion Sort

Methods of Sorting
1. Bubble Sort
Compare the adjacent elements and set the higher index element to the highest among the two. a[i+1] = max(a[i],a[i+1]). So each pass you are actually putting the highest element at the end of the array.
Sample Code:

for (int i = 0; i < data.Length; i++)
for (int j = 0; j < data.Length - 1; j++)
if (data[j] > data[j + 1])
{
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}


2. Insertion Sort
In Insertion Sort we try to insert one element by element into the already sorted array. So every time we insert a new element we actually shift the whole array.

for (int i = 0; i <= data.Length; i++) {
int j = i;
while (j > 0 && data[i] < data[j - 1])
j--;
int tmp = data[i];
for (int k = i; k > j; k--)
data[k] = data[k - 1];
data[j] = tmp;
}

About Sorting:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=sorting

Dynamic Programming

Dynamic Programming:
A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub-solution of the problem is constructed from previously found ones. DP solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc.

Refer these links for more info:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
http://en.wikipedia.org/wiki/Dynamic_programming



Example Problem:
Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.

For a better understanding let's take this example:
Given coins with values 1, 3, and 5.
And the sum S is set to be 11.

First of all we mark that for state 0 (sum 0) we have found a solution with a minimum number of 0 coins. We then go to sum 1. First, we mark that we haven't yet found a solution for this one (a value of Infinity would be fine). Then we see that only coin 1 is less than or equal to the current sum. Analyzing it, we see that for sum 1-V1= 0 we have a solution with 0 coins. Because we add one coin to this solution, we'll have a solution with 1 coin for sum 1. It's the only solution yet found for this sum. We write (save) it. Then we proceed to the next state - sum 2. We again see that the only coin which is less or equal to this sum is the first coin, having a value of 1. The optimal solution found for sum (2-1) = 1 is coin 1. This coin 1 plus the first coin will sum up to 2, and thus make a sum of 2 with the help of only 2 coins. This is the best and only solution for sum 2. Now we proceed to sum 3. We now have 2 coins which are to be analyzed - first and second one, having values of 1 and 3. Let's see the first one. There exists a solution for sum 2 (3 - 1) and therefore we can construct from it a solution for sum 3 by adding the first coin to it. Because the best solution for sum 2 that we found has 2 coins, the new solution for sum 3 will have 3 coins. Now let's take the second coin with value equal to 3. The sum for which this coin needs to be added to make 3 , is 0. We know that sum 0 is made up of 0 coins. Thus we can make a sum of 3 with only one coin - 3. We see that it's better than the previous found solution for sum 3 , which was composed of 3 coins. We update it and mark it as having only 1 coin. The same we do for sum 4, and get a solution of 2 coins - 1+3. And so on.