Given an array of red, green and blue balls arrange them in groups of all red together, greens together and blue together. Do in a single scan of the array.

You have an array containing only '0's, '1's and '2's. Club same items together in single scan.

let's try to understand problem:



algorithm:
i)  initialize i and j to 0 and  k to n-1 Where n is  number of balls
ii) while j <= k  do
            if pointer  j point to red ball than
                     swap a[i] and a[j];
and  perform i++; j++

           if pointer  j point to white ball than
just perform j++

           if pointer  j point to blue ball than
swap a[j] and a[k];
         and  perform  k--;

This problem is also known as Dutch National Flag Problem. Check out how Dutch flag looks like:

code:

#include <stdio.h>

//here red->0, white->1, blue->2
int arr[] = { 0,1,0,2,2,0,1,1,0 };      
int arr_size = sizeof(arr)/sizeof(arr[0]);

void swap(int *a, int *b);
void dutchflag( ); 

int main()
{
  int c; 
  dutchflag();  
  printf("\ndutch flag Order: ");
  for (c = 0; c < arr_size; c++)
    printf("%d ", arr[c]);
   
  return 0;
}
/* test function to to Sort the balls in dutch flag order*/
void dutchflag( )
{
 int i = 0,j=0 , k = arr_size - 1;
 
   while(j <= k)
   {
      switch(arr[j])
      {
         case 0:
            swap(&arr[i++], &arr[j++]);
           break;
         case 1:
          j++;
           break;
         case 2:
          swap(&arr[j], &arr[k--]);
           break;
      }
   }
}

/* Function to swap *a and *b */ 
void swap(int *a, int *b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}

output:-

dutch flag Order: 0 0 0 0 1 1 1 2 2

Time Complexity:  O(n)

Given n stairs, how many number of ways can you climb if u use either 1 or 2 at a time?

variant of question:-

A person can take m steps at a time to reach a particular floor( say in a building). How many different ways can a person reach the nth floor?

let's try to understand problem:




but we have to make some modification in Fibonacci sequence to get correct answer.
why?
In Fibonacci first element is 0 & second is 1
i.e for step no 0  we have 0 ways & for step no 1 we have 1 way
for step no 2=no of ways(0)+ no of ways(1)=0+1=1
but  answer is 2 which is no of ways(2)+ no of ways(1)=1+1=2
look at table

Here our first element is 1 not 0
therefore to find no of ways for step no n ,we have to find  no of ways for step no n+1

code:

#include <stdio.h> 
int Fibonacci(int);
main()
{
   int n;
   printf("total no of steps:");
   scanf("%d",&n);
   printf("no of ways to climb is %d\n", Fibonacci(n+1));
   return 0;
}
 
int Fibonacci(int n)
{
   if ( n == 0 )
      return 0;
   else if ( n == 1 )
      return 1;
   else
      return ( Fibonacci(n-1) + Fibonacci(n-2) );
} 

output:-

total no of steps:4
no of ways to climb is 5

but what if person can take m steps at a time ?
if person take up-to 2 steps at time(i.e either 1-step or 2-step) then to get no of steps we add
(n-1) +(last result)=(new result)

if person take up-to 3 steps at time(i.e either 3-step or 2-step or 1-step) then to get no of steps we add
(n-2)+(n-1) +(last result)=(new result)

similarly, 
if person take up-to m steps at time then to get no of steps we add
(n-(m-1))+(n-(m-1)-1) ..............+(last result)=(new result)

Generalize code:

#include <stdio.h> 
int n, m;
int Fibonacci(int n);
int main ()
{
 printf("total no of steps:");
 scanf("%d",&n);
 printf("max no of steps can climb:");
 scanf("%d",&m);
 printf("no of ways to climb is %d\n", Fibonacci(n+1));
   return 0;
}
int Fibonacci(int n)
{ int total=0,i;
  if ( n == 0 )
      return 0;
  if ( n == 1 )
      return 1;
    for ( i = 1; i<=m && i<=n; i++) //for m steps
        total += Fibonacci(n-i);
    return total;
}

output:-

total no of steps:4
max no of steps can climb:3
no of ways to climb is 7