Problem:-
A simple problem on sorted array: Design an O(n)-time algorithm
that, given a real number x and a sorted array S of n numbers,
determines whether or not there exist two elements in S whose sum is
exactly x .In this problem the we can apply count sort for sorting the array and then implement the problem in c programming language. At first understand the count sort algorithm. Count sort is non-comparison type sorting algorithm that is the in this sorting algorithm no comparison is takes place. In count sort the input element x is less then to total number of elements. By this information we put the element x to its appropriate position in the array.
Count sort is integer sorting algorithm.
Complexity of counting sort is O(n).So the in over problem we can apply the count sort algorithm for sort the array.
Code for given problem:-
/* by www.computersciencearticle.in */ #include<conio.h> #include<stdio.h> void main() { int a[100],b[100],c[100],k,i,j,n=0,ele,flag=0,sum,count=0; clrscr(); printf("enter the array size"); scanf("%d",&n); printf("enter the array element"); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } k=9; for(i=0;i<=k;i++) { c[i]=0; } for(j=1;j<=n;j++) { c[a[j]]=c[a[j]]+1; } for(i=1;i<=k;i++) { c[i]=c[i]+c[i-1]; } for(j=n;j>=0;j--) { b[c[a[j]]]=a[j]; c[a[j]]=c[a[j]]-1; } printf("the sorted array is"); for(i=1;i<=n;i++) { printf(" %d",b[i]); } printf("enter element which two element sum not exactly entered elemt"); scanf("%d",&ele); for(i=n;i>=1;i--) { if(b[i]>ele) flag=i-1; } printf("the pair of sum not exactly is: "); for(i=1;i<=flag;i++) { sum=b[i-1]+b[i]; if(sum<ele) { count++; printf("pair no %d is: %d %d",count,b[i-1],b[i]); } } getch(); }
Source Code: COUNT
Output:-
Lets the array is A=<6, 0, 2, 0, 1, 3, 4, 6 >
and sum not exactly is 2.
Output of Count sort algorithm in c programming language |