Binary Search using recursion

Given an sorted array: {1,5,6,10,19,31,72}

Solution:
Binary search only works on sorted array.
Calculate middle location of array and check the element which element to be searched.
Since array is sorted, if mid element is less then search item, then element is bound to be in the second half of list. In next steps, search within the respective part of the list
Start marker of array become middle +1 location, end remains same.
start= mid+1

Otherwise if the mid element is greater than search item, then element will be in the first half of list.
End marker of array become middle -1 location, start remains same.

Complexity: O(N/2)

#include <stdio.h>

int binarySearch(int array[],int start,int end,int search) {
if( start > end) {
                // A base condition
                // Happens when list does not contain value
return -1;
}

int mid = (int) ((start + end)/2);

if(  array[mid] > search) {
binarySearch(array, start, mid-1, search);
}
else if ( array[mid] < search) {
binarySearch(array, mid+1, end, search);
}

else {
               // A Base condition
              // Element found, return its position
return mid+1;
}
}

int main() {
    int arr[] = {1,5,6,10,19,31,72};
    int size = sizeof(arr)/sizeof(arr[0]);

    int pos = -1;
    int searchItem = 1;
 
    pos = binarySearch(arr, 0, 5,searchItem);
    if(pos == -1) {
        printf("%d not found in list",searchItem);
    }
    else {
        printf("%d found at location %d",searchItem,pos);
    }
    return 0;
}

Output:
1 found at location 1

Factorial Using recursion

Factorial of number n (n!) is 1* 2 * ... (n-1) *  n
5! = 5*4*3*2*1 = 120

Checkout: Factorial without recursion

Solution: 
Recursion is the process in which functions calls itself until some base condition is met. Recursion helps in writing shorter functions by dividing a problem into small parts and then solving that problem using a same function again.

We know that n! = 1 for n = 0, n! = n * (n-1)!  for n > 0
For writing a recursive method we can use base condition when n become 1 and call the recursive method with (n-1) at each call.

#include<stdio.h>

int factorial(int n) {
     if(n>0) {
           return n * factorial(n-1);
     }
     else {
           return 1;
     }
}

int main()
{
    int num =5;
    printf("Factorial of %d : %d", num, factorial(num));
}

Output:

Factorial of 5 : 120                                                                                                          

                    

Finding whether a number exists as sum of two array elements in a sorted array

Given the array{-5,-2,7,8,9,10,12}

Find whether sum 8 is possible

As element no.2 (-2) and element no.7(10) are present the sum of the two is 8

Solution:  As the array is sorted, we can leverage this property and come up with an approach which is similar to binary searching

Start with two markers at start and end of the array

Sum the two numbers at start and end marker

if sum is greater than given number, decrease the end marker 

if sum is less than given number, advance the start marker

Break if desired sum is found or start becomes greater than or equal to end

Complexity: O(n)

#include <stdio.h>
int main()
{
    int a[] = {-5,-2,7,8,9,10,12};
    
    int sum =8;
    
    int found_flag = 0;
    int size = sizeof a / sizeof a[0];
    printf("\nSize of array %d", size);
    int start = 0;
    int end = size-1;
    
    while(start<=end) {
        if((a[start]+a[end])<sum) {
            start++;
        }
        else if ((a[start]+a[end]>sum)) {
            end--;
        }
        else {
            found_flag++;
            break;
        }
    }
    
    if(found_flag) {
     printf("\nElement at location(%d):%d and location(%d):%d has sum:%d", start+1,a[start],end+1,a[end],sum);
    }
    else {
        printf("\nNot found !!");
    }
    return 0;
}

Output:

Size of array 7                                                                                                               

Element at location(2):-2 and location(6):10 has sum:8 

Finding whether a number exists as sum of two array elements in an unsorted array

Given the array{2, 10,9,7,8 ,-2}

Find whether sum 8 is possible

As element no.2 (10) and element no.6(-2) are present the sum of the two is 8

Solution: Taking an Sum minus the fixed element, we scan through rest of the array to find another element matching

Complexity: O(n^2)

#include <stdio.h>

int main()

{

    int a[6] = {2, 10,9,7,8 ,-2};

    

    int sum = 8;

    

    int flag = 0;

    int size = sizeof a / sizeof a[0];

    printf("\nSize of array %d", size);

    int i=0;

    int j =0;

    for (i= 0; i<size-1; i++) {

        for(j=i+1; j <size;j++) {

            if(sum-a[i] == a[j]) {

                flag++;

                break;

            }

        }

        if(flag==1) {

            break;

        }

    }

    

    if(flag) {

     printf("\n Element at location(%d):%d and location(%d):%d has sum:%d", i+1,a[i],j+1,a[j],sum);

    }

    else {

        printf("Not found !!");

    }

    return 0;

}

Output:

Size of array 6                                                                                                               

 Element at location(2):10 and location(6):-2 has sum:8

Frequency of number in an array

Program to find number of times a given integer value has occurred in an array of integers.

let array a[]= {6,1,6,3,5,6,2,2,1,3,6,2}
output:
1 -- 2
2 -- 3
3 -- 2
5 -- 1
6 -- 4

The simple solution to the problem is to increment array value at a particular index where index value is equal to the number.

Program

#include<stdio.h>
int main()
{
       int a[]={6,1,2,5,6,3,2,2,2,1,4,2,8,4,3}; // size of a =15
       int b[10]; // size 10 is sufficient because maximum number in above array is 9
       int i;

       //assigning all elements of array b to 0    
       for(i=0;i<10;i++)
            b[i]=0;

       for(i=0;i<15;i++)
            b[a[i]]++;

       for(i=0;i<10;i++)
       {
           if(b[i]!=0)
              printf("%d -- %d\n",i,b[i]);
        }
       return 0;
}

     

histogram printing

Program to print a histogram pattern for a given array.

For example 

Array   =     4 5 3 2

pattern 

4 5 3 2

   *

* *

* * *

* * * *

* * * *

Outer loop: depends on the maximum element in the array.

The very basic technique to find the maximum element is to assign first element of array as maximum and then subsequently checking it with other array elements and changing the maximum element appropriately.

Inner loop: controls the printing and also depends on maximum element. Find the maximum element and compare it with elements. If the given element is greater than the max element than print "*" otherwise print a space. Decrement the maximum element for a full completion of inner loop. 

                      

Program:

#include<stdio.h>

int main()

{

int a[]={5,7,3,6,4,8,2};

int size=7;

int max=a[0];

int i,j,temp;

for(i=1;i<size;i++)

{

if(max<a[i])

max=a[i];

}

for(i=0;i<size;i++)

     printf("%d ",a[i]);

printf("\n");

temp=max;

for(i=0;i<max;i++)

{

for(j=0;j<size;j++)

{

if(a[j]>=temp)

printf("* ");

else

printf("  ");

        }

temp--;

printf("\n");

}

return 0;

}

Printing Pattern 10

      1
    121
  12321
1234321
------------- for n values

The above pattern can be divided into two parts

        1             
       12             1
     123      +     21
   1234             321

outer loop i should run n times.
inner loop comprises of 2 loop variable for printing 1st and 2nd half of the pattern.
Number of spaces printed depends on number of values in that line
Maximum value in a line is the line number.



Outer loop
for(i=1;i<=n;i++)
{ ... }



Inner loop for spaces
Number of spaces = max lines in pattern - Values printed in that line

for(j=1;j<=n-i;j++)
printf(" ");

here 'n' number of lines in pattern which user enters and also the maximum value that appears in the pattern.

'i' is the line number of that line or number of values printed in that line.



Inner loop for 1st pattern
starts with 1 and goes till line number value for that line or max value of that line.

for(k=1;k<=i;k++)
printf("%d",k);






Inner loop for 2nd pattern

start with maximum value of that line -1 and decrements down to 1.

for(t=i-1;t>=1;t--)
printf("%d",t);




Program

#include<stdio.h>

int main()
{
int i,j,k,t,n;

//ask user to enter number of lines
printf("\nEnter the number of lines in the pattern:");
scanf("%d",&n);

//outer loop
for(i=1;i<=n;i++)
{

//loop for spaces 
        for(j=1;j<=n-i;j++)
              printf(" ");

//loop for 1st part of pattern
        for(k=1;k<=i;k++)
              printf("%d",k);

//loop for 2nd part of pattern
        for(t=i-1;t>=1;t--)
              printf("%d",l);

//move to next line
         printf("\n");
}

return 0;
}

Printing Pattern 9

1
01
101
0101
10101

Alternating between 1 and 0. Hmm! We can use number%2 that will always be 1 or 0. % means remainder division(or modular division) and gives remainder when number is divided by another number. When a number is divided by number 'n', remainder is always between 0 and n-1. So in case of division with 2, remainder is between 0 to 1 (n-1).
0 and 1 keeps on alternating in each line as well as for the next line. How about making it dependent on line both i and j say sum of i and j

line 1 element 1 -- i=1,j=1, i+j=2, 2%2=0 but we want a 1 instead. So add 1 to i+j and then mod it will 2.
Then i (outer loop variable) loops 5 times and j (inner loop variable) loops from 1 till i for each line and then goes to the next line.

i     j    i+j+1     i+j+1%2
1    1      3              1
next line
2    1      4              0
2    2      5              1
next line
3    1      5              1
3    2      6              0
3    3      7              1
next line
and so on.

#include<stdio.h>
int main()
{
     int i,j;

    for(i=1;i<=5;i++)
    {
          for(j=1;j<=i;j++)
                 printf("%d",(i+j+1)%2);

          printf("\n");
    }

    return 0;
}

 

Printing pattern 8

1
2   7
3   8 12
4   9 13 16
5 10 14 17 19
6 11 15 18 20 21

Seeing the pattern we can figure our that 1st element of each line is the value of line no. that is dependent on i (outer loop variable)

Some further look into the pattern reveals the following
1
2 7(2+5)
3 8(3+5) 12(8+4)
4 9(4+5) 13(9+4) 16(13+3)
5 10(5+5) 14 (10+4) 17(14+3) 19(17+2)
and so on.

#include<stdio.h>
int main()
{
    int i,j,fix,curval=0;

    for(i=1;i<=6;i++)
    {      
        fix=5;
        curval=i+fix;
        for(j=1;j<=i;j++)
        {
            if(j==1)
                printf("%2d ",i);

            if(j>1)
            {
                printf("%2d ",curval);
                fix--;
                curval=curval+fix;
            }
        }
        printf("\n");
    }
    return 0;
}

Printing pattern 7

1
1*2
1*2*3
1*2*3*4

i used as outer loop variable for printing no. of lines=4
j used to control printing * and nos. in each line.
In this pattern, we can figure out that star does not get printed when value of i equals value of j.

#include<stdio.h>
int main()
{
         int i,j;

         for(i=1;i<=4;i++)
         {
                 for(j=1;j<=i;j++)
                 {
                           printf("%d",j);

                           if(i!=j)
                                 printf("*");
                 }

                  printf("\n");
            }

            return 0;
}