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

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;

}

To find whether a number is in power of 2 using complement and gate (very short)

A number occurring in power of has a specialty when written in its binary representation:

1     = 0000 0001

2     = 0000 0010

4     = 0000 0100

8     = 0000 1000

16   = 0001 0000

32   = 0010 0000

64   = 0100 0000

128 = 1000 0000

What happens when I subtract one from these above numbers

1-1=0          0000 0000
2-1=1          0000 0001
4-1=3          0000 0011
8-1=7          0000 0111
16-1=15      0000 1111
32-1=31      0001 1111
64-1=63      0011 1111
128-1=127   0111 1111

Before moving further we will look at Complement Operator(~) in C.
Complement of a binary number changes all 1 bits to 0 and all zero bits to 1

~(1011 0110) = 0100 1001

It is similar to XOR toggling all bits
          1011 0110
XOR    1111 1111
------------------------
           0100 1001

Never mind!

Looking at numbers in power of two and their subtraction by 1, we can establish a pattern

For example, let us take 16
 16 =  0001 0000
 ~(16) = ~(0001 0000) = 1110 1111
16-1=15 = 0000 1111

If we AND  ~16 and (16-1), it equals (16-1)

~(16) =         1110 1111
16-1=15=      0000 1111
----------------------------------
 16-1=15=      0000 1111

Hence the method to find whether the number is power of two or not.

#include<stdio.h>
int main()
{
    int num;
    printf("\nEnter number:");
    scanf("%d",&num);
    if(((num-1)&(~num))==(num-1))
        printf("%d is in power of 2",num);
    else
        printf("%d is not in power of 2",num);

    return 0;
}

Although, this short method does not tell us which power of 2 is the number like previous methods discussed. You can verify this method for numbers that are not in power of two.

Modular Division or Remainder Division (% sign in C language)

Although I have already written many programs using modulo(modulus) division in the blog, yet i haven't explained it anywhere and relatively new programmers would be opening up some other reference pages to search what % sign means , I thought I can make life simpler for them including it here. Better late than never :)

So what a%b means in C
Say a = 35 and b = 8
35 when divided by 8 it gives quotient as 4 and remainder as 3.

In C language
35%8=3
24%4=0

We can also write it as 35=4*8+3

8%14?
8=0*14+8
Hence 8%14=8

(-5)modulo3?
possible.
 -5-(3*-1)=-2 .
make the remainder +ve by adding
-2+3=1
(-5)modulo3=1

But in gcc compiler
-5%3=-2
and
5%-3=2
and
-5%-3=-2

Pythagorean Triplets

A Pythagorean Triplet is set of three positive integers (a,b,c) such that

a²+b²=c²

^{For example (3,4,5) , (5,12,13), etc.}

^{Multiplying the triplets with a same number gives another triplets}

^{for example 2*(3,4,5)=(6,8,10)}

^{Following is the program to print Pythagorean Triplets where (a,b,c)<100 and can not be multiple of each other or factorised by each other i.e. if there is a set of (3,4,5) then (6,8,10) shoulnd be part of output.}

^{#include<stdio.h>
#include<math.h>
int check(int x,int y,int z)
{
        int i=2,r1,r2,r3,r;
        while(i<=x)
               {
                   r1=x%i;
                   r2=y%i;
                   r3=z%i;
                   r=r1+r2+r3;}

                   ^{if(r==0)
                      break;
                   else
                       i++;
                }}

           <sup>if (r==0)
                return 0;
           else
                return 1;
}



int main()
{

       float t=0;
       int a=0, u=0;
       int i, j;


       for(i=3;i<100;i++)
               {
                      for(j=i+1;j<100;j++)
                            {
                                 u=i*i+j*j;</sup>

                                 ^/*

                                  ^{sqrt() belongs to math.h header file. sqrt(4)=2, sqrt(4.5)=2.12132}

                                 ^{*/
                                  t=sqrt(u);
                                  a=t;
                                   /*} 

                                   ^{ceil() belongs to math.h header file. ceil(4.6)=5}

                                   ^{floor() belongs to math.h header file. floor(4.6)=4}

                                  ^{*/
                                   if(ceil(t)==floor(t)&& check(i,j,a))
                                              printf("(%d,%d,%d)\n",i,j,a);
                             }
                   }}

           ^{return 0;
}}

Reversing a number logic and program

Reserving a number simply involves
1)Intially taking the remainder as 0
2)Calculating and storing remainder of a number when divided by 10.
3)Multiplying the immediate remainder by 10 and adding it to previous value of remainder.
4)Dividing the number by 10
5)Repeating the above steps until number becomes 0.

For example
taking all variables as integers so that fractional part is truncated during division
number=532 (not equal to 0)
immediate remainder=number%10=532%10=2
previous remainder= (previous remainder*10)+immediate remainder=0*10+2=2
number=number/10=532/10=53

number=53 (not equal to 0)
Repeat steps
immediate remainder=number%10=53%10=3
previous remainder=(previous remainder*10)+immediate remainder=2*10+3=23
number=number/10=53/10=5

number=5 (not equal to 0)
Repeat steps
immediate remainder=number%10=5%10=5
previous remainder=(previous remainder*10)+immediate remainder=23*10+5=235
number=number/10=5/10=0

number=0
Stop loop


#include<stdio.h>
int main()
{
        int num, num_copy, rem,rev;
        printf("\nEnter the number to be reversed:");
        scanf("%d",&num);
        num_copy=num;
        rem=0;
        rev=0;

        while(num!=0)
        {
                rem=num%10;
                rev=rev*10+rem;
                num=num/10;
         }

      printf("\nReverse of %d is %d",num_copy,rev);
      return 0;
}