Category Archives: C Array

C Code of arrays.

Find the occurence of each number from array in O(n) ?

December 9, 2013 admin

Find the the occurrence of each number from given array of size n , where elements ranges from 0 to n-1 ?
Complexity : O(n)
Space complexity : O(1)
e.g.
Input:
5 3 3 2 1 3 8 7 3
Output:
3 occurs 4 times

Solution :

#include<stdio.h>
#include<math.h>
void No_of_Occurrence(int A[],int length){
int i=0,temp;
while(i<=length-1){
if(A[i]>=0){
    if(A[A[i]]>=0){temp=A[i];A[i]=A[A[i]];A[temp]=-1;}
    else{A[A[i]]--;A[i]=-length;i++;}

          }
else i++;
}
for(i=0;i<=length-1;i++){
if(A[i]>-length){printf("%d occurred %d times\n",i,abs(A[i]));}
}
}
int main(){
int i=0,temp;int A[]={2,5,0,5,2,2,5,5,0};
int length=9;
No_of_Occurrence(A,length);

return 0;
}

#include<stdio.h>

#include<math.h>

void No_of_Occurrence(int A[],int length){

int i=0,temp;

while(i<=length-1){

if(A[i]>=0){

if(A[A[i]]>=0){temp=A[i];A[i]=A[A[i]];A[temp]=-1;}

else{A[A[i]]--;A[i]=-length;i++;}

}

else i++;

}

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

if(A[i]>-length){printf("%d occurred %d times\n",i,abs(A[i]));}

}

int main(){

int i=0,temp;int A[]={2,5,0,5,2,2,5,5,0};

int length=9;

No_of_Occurrence(A,length);

return 0;

}

Code provided by : Arpit Agrawal

C Array, play with numbers

Print given square matrix in spiral order

August 26, 2013 admin

Print givensquare matrix in spiral order :

Complexity : O(n^2)

Approach :

Step1 : write a 4 for loop for printing boundry

step 2: Apply the step1 for inner martrix by modifying starting point and ending point of matrix

step 3: Aplly step2 untill the matrix size becomes 1 or 0

end

Input :

—————-

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

—————-

Output :

——————————————————-

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

——————————————————-

C code to print given square matrix in spiral order :

#include<stdio.h>
void print_array_spiral(int A[][4],int i,int j,int l,int m,int n)
{
    if(n<=0) return;
    if(n==1)
    {
        printf(" %d ",A[i][j]);
	return;
    }
    int ii=i,jj=j,ll=l,mm=m;
    // Loop 1 to print top Row
    for(jj=j;jj<=m;jj++)
        printf(" %d ",A[ii][jj]);
    jj=m;
    // Loop 2 to print Right most column array
    for(ii=i+1;ii<=l;ii++)
	printf(" %d ",A[ii][jj]);
    ii=l;
    // Loop 3 to print bottom Row
    for(jj=m-1;jj>=i;jj--)
        printf(" %d ",A[ii][jj]);
    jj=i;
    // Loop 4 to print Left most column
    for(ii=l-1;ii>=i+1;ii--)
	printf(" %d ",A[ii][jj]);
print_array_spiral(A,i+1,j+1,l-1,m-1,n-2);
}
int main(){

int Arr[][4]={{1,2,3,4},{12,13,14,5},{11,16,15,6},{10,9,8,7}};

print_array_spiral(Arr,0,0,3,3,4);

return 0;
}

#include<stdio.h>

void print_array_spiral(int A[][4],int i,int j,int l,int m,int n)

{

if(n<=0) return;

if(n==1)

{

printf(" %d ",A[i][j]);

return;

}

int ii=i,jj=j,ll=l,mm=m;

// Loop 1 to print top Row

for(jj=j;jj<=m;jj++)

printf(" %d ",A[ii][jj]);

jj=m;

// Loop 2 to print Right most column array

for(ii=i+1;ii<=l;ii++)

printf(" %d ",A[ii][jj]);

ii=l;

// Loop 3 to print bottom Row

for(jj=m-1;jj>=i;jj--)

printf(" %d ",A[ii][jj]);

jj=i;

// Loop 4 to print Left most column

for(ii=l-1;ii>=i+1;ii--)

printf(" %d ",A[ii][jj]);

print_array_spiral(A,i+1,j+1,l-1,m-1,n-2);

}

int main(){

int Arr[][4]={{1,2,3,4},{12,13,14,5},{11,16,15,6},{10,9,8,7}};

print_array_spiral(Arr,0,0,3,3,4);

return 0;

}

C Array, play with numbers

find pair of numbers in array that add to given sum

August 26, 2013 admin

Find pair of numbers in array that add to given sum :

Complexity: O(n logn)

Approach :

step 1: Sort an array using efficient sorting method

step 2: use two variable i & j , initialize i as starting position of array (i=0) and j as last position of array (j=n-1). Where n is number of element in array.

step 3: if(A[i]+A[j]<x) i++

else if(A[i]+A[j]>x) j–

else (A[i]+A[j]==x) print A[i] , A[j] and i++

step 4: Repeat step 3 untill i<j

Code to Find pair of numbers in array that add to given sum :

#include<stdio.h>
void swap(int *p,int *q){
int t;
t=*q;
*q=*p;
*p=t;
}
int partition(int [],int ,int);
void quicksort(int A[],int p,int r){
    int q;
    if(p<r){
        q=partition(A,p,r);
        quicksort(A,p,q-1);
        quicksort(A,q+1,r);
    }
}
int partition(int A[],int p,int r){
int x,i,j;
x=A[r];
i=p-1;
for(j=p;j<r;j++){
    if(A[j]<=x){
        i=i+1;
        swap(&A[i],&A[j]);
        }
}
swap(&A[i+1],&A[r]);
return i+1;
}

void sum_of_pair_as_x(int A[],int n,int x){
   int i=0,j=n-1;
    while(j>i){
        if(A[i]+A[j]<x) i++;
        else if(A[i]+A[j]>x) j--;
        else {printf(" [ %d ,%d ] ",A[i],A[j]); i++;}
    }
}

void print_array(int A[],int n){
    int i=0;
    for(i=0;i<n;i++)
        printf(" %d ",A[i]);
printf("\n");
}
int main()
{
    int Arr[]={7,8,3,1,2,4,6,5};
    int x=9;
    int n=sizeof(Arr)/sizeof(Arr[0]);
    quicksort(Arr,0,n-1);
    printf("\n Pair of sum %d are : \n",x);
    sum_of_pair_as_x(Arr,n,x);
    printf("\n");
 return 0;
}

#include<stdio.h>

void swap(int *p,int *q){

int t;

t=*q;

*q=*p;

*p=t;

}

int partition(int [],int ,int);

void quicksort(int A[],int p,int r){

int q;

if(p<r){

q=partition(A,p,r);

quicksort(A,p,q-1);

quicksort(A,q+1,r);

}

int partition(int A[],int p,int r){

int x,i,j;

x=A[r];

i=p-1;

for(j=p;j<r;j++){

if(A[j]<=x){

i=i+1;

swap(&A[i],&A[j]);

}

swap(&A[i+1],&A[r]);

return i+1;

}

void sum_of_pair_as_x(int A[],int n,int x){

int i=0,j=n-1;

while(j>i){

if(A[i]+A[j]<x) i++;

else if(A[i]+A[j]>x) j--;

else {printf(" [ %d ,%d ] ",A[i],A[j]); i++;}

}

void print_array(int A[],int n){

int i=0;

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

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

printf("\n");

}

int main()

{

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

int x=9;

int n=sizeof(Arr)/sizeof(Arr[0]);

quicksort(Arr,0,n-1);

printf("\n Pair of sum %d are : \n",x);

sum_of_pair_as_x(Arr,n,x);

printf("\n");

return 0;

}

C Array, Sorting

Counting sort

August 24, 2013 admin

Counting Sort :

n is number of values in array , k is the range of values (max – min )

Compexity : O(n+k)

Counting sort is a sorting technique to sort an array in linear time. It uses an extra space for counting occurrence of each object in array. This technique is efficient when range of data is not much larger than number of inputs to be sorted.

/* Counting Sort Code by codingstreet.com
Complexity: O(n+k);
n is number of object in the array
k is range of input
*/
#include<stdio.h>
#include<stdlib.h>

void printarray(int A[],int size){
    int i;
    printf("\n ");
    for(i=0;i<size;i++)
        printf("%d ",A[i]);
}

void counting_sort(int A[],int size){
int min,max,i,range,*p,j;
min=A[0],max=A[0];
    for(i=0;i<size;i++){
            if(A[i]<min) min=A[i];
            if(A[i]>max) max=A[i];
    }
range=max-min+1;
p=malloc(sizeof(int)*range);
    for(i=0;i<range;i++) p[i]=0;

    for(i=0;i<size;i++){
        p[A[i]-min]+=1;
    }
    int k=0;
    /* First Fore loop is executed 'range' times and second while loop wil be executed only 'size' */ 
    for(i=0;i<range;i++){
	j=p[i];    	
	while(p[i]!=0 && j!=0){
	A[k]=i+min;
	k++;
	j--;      
	}
    }
}
int main(){

int A[]={5,9,8,6,15,11,7,5,8};

int n=sizeof(A)/sizeof(A[0]);
// Array Before Sorting
printarray(A,n);
counting_sort(A,n);
// Array After counting Sort
printarray(A,n);

return 0;
}

/* Counting Sort Code by codingstreet.com

Complexity: O(n+k);

n is number of object in the array

k is range of input

#include<stdio.h>

#include<stdlib.h>

void printarray(int A[],int size){

int i;

printf("\n ");

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

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

}

void counting_sort(int A[],int size){

int min,max,i,range,*p,j;

min=A[0],max=A[0];

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

if(A[i]<min) min=A[i];

if(A[i]>max) max=A[i];

}

range=max-min+1;

p=malloc(sizeof(int)*range);

for(i=0;i<range;i++) p[i]=0;

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

p[A[i]-min]+=1;

}

int k=0;

/* First Fore loop is executed 'range' times and second while loop wil be executed only 'size' */

for(i=0;i<range;i++){

j=p[i];

while(p[i]!=0 && j!=0){

A[k]=i+min;

k++;

j--;

}

int main(){

int A[]={5,9,8,6,15,11,7,5,8};

int n=sizeof(A)/sizeof(A[0]);

// Array Before Sorting

printarray(A,n);

counting_sort(A,n);

// Array After counting Sort

printarray(A,n);

return 0;

}

C Array, Sorting

Kth smallest element in Array

August 22, 2013 admin

C code to find out Kth smallest element in array .

Approach 1:

Sort the array using any sorting method and return the value of kth index.

Approach 2:

Using partition function of quick sort which return the index of the pivot value.

comparing the returning value from partition function with k.

/* C code to find Kth smallest element in array */
#include<stdio.h>
int partition(int A[],int,int );
void  swap(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}

/* n is total no of element in array , k is for kth smallest element */
int kthsmallest(int  A[],int n, int k){
int i=0,flag=0;
int p,q,r;
p=0;
r=n-1;
k--;
while(!flag){
    q=partition(A,p,r);
    if(q==k) flag=1;
    else if(k<q){ r=q-1;}
    else {p=q+1;}
}
return A[k];
}
int partition(int A[],int p,int r){
int i,j,pivot;
i=p-1;
pivot=A[r];
for(j=p;j<r;j++){
   if(A[j]<pivot){
        i++;
        swap(&A[j],&A[i]);
   }
}
swap(&A[i+1],&A[r]);
return i+1;
}
int main(){

int Arr[]={5,-4,3,-2,1};
int result;
result=kthsmallest(Arr,5,2);

printf(" %d ",result);

return 0;
}

/* C code to find Kth smallest element in array */

#include<stdio.h>

int partition(int A[],int,int );

void swap(int *a,int *b){

int t=*a;

*a=*b;

*b=t;

}

/* n is total no of element in array , k is for kth smallest element */

int kthsmallest(int A[],int n, int k){

int i=0,flag=0;

int p,q,r;

p=0;

r=n-1;

k--;

while(!flag){

q=partition(A,p,r);

if(q==k) flag=1;

else if(k<q){ r=q-1;}

else {p=q+1;}

}

return A[k];

}

int partition(int A[],int p,int r){

int i,j,pivot;

i=p-1;

pivot=A[r];

for(j=p;j<r;j++){

if(A[j]<pivot){

i++;

swap(&A[j],&A[i]);

}

swap(&A[i+1],&A[r]);

return i+1;

}

int main(){

int Arr[]={5,-4,3,-2,1};

int result;

result=kthsmallest(Arr,5,2);

printf(" %d ",result);

return 0;

}

C Array, C Code, Hash

Hash implementation in Array (Direct Addressing)

June 28, 2013 admin

C code to implement hash using array.

Description :

Hash can store only integer value. One slot can store only one value. Hash function is mod ( value % slots) .

/* int hash code using array by Codingstreet.com */
/* hash function (key % hashize) */
#include<stdio.h>
int *create_hash(int hashsize){
int p;
p=(int *)malloc(sizeof(int)* hashsize);
return p;
}
int main (){
int *h1,h1size,i=0,key,val,slot;
printf("\n Enter the hash size : ");
scanf("%d",&h1size);
h1=create_hash(h1size);
printf("\n Please not that we are using array so value which you are going to enter may override the older value because of getting same hash value. ");
do{
    printf("\n Hash Menu by Codingstreet.com ");
    printf("\n 1. Insert value");
    printf("\n 2. Find Value ");
    printf("\n 3. Exit");
    printf("\n Enter the key : ");
    scanf("%d",&key);
    switch(key){
    case 1:
    printf("\n Enter the value :");
    scanf("%d",&val);
    slot=val%h1size;//computed hash key using mod function
    h1[slot]=val;
    printf("\n Slot for value  %d is %d",val,slot);
    break;
    case 2:
    printf("\n Enter the value to be searched :");
    scanf("%d",&val);
    slot=val%h1size;
    if(h1[slot]==val) printf("\n %d is found at slot %d ",val,slot);
    else printf("\n %d is not found ",val);
    break;
    case 3:
        printf(" \n Good Bye .. ");
    break;
    }
    }while(key!=3);
    printf("\n Thank you for using codingstreet.com 's DataStructure Solutions\n");
return 0;;
}

/* int hash code using array by Codingstreet.com */

/* hash function (key % hashize) */

#include<stdio.h>

int *create_hash(int hashsize){

int p;

p=(int *)malloc(sizeof(int)* hashsize);

return p;

}

int main (){

int *h1,h1size,i=0,key,val,slot;

printf("\n Enter the hash size : ");

scanf("%d",&h1size);

h1=create_hash(h1size);

printf("\n Please not that we are using array so value which you are going to enter may override the older value because of getting same hash value. ");

do{

printf("\n Hash Menu by Codingstreet.com ");

printf("\n 1. Insert value");

printf("\n 2. Find Value ");

printf("\n 3. Exit");

printf("\n Enter the key : ");

scanf("%d",&key);

switch(key){

case 1:

printf("\n Enter the value :");

scanf("%d",&val);

slot=val%h1size;//computed hash key using mod function

h1[slot]=val;

printf("\n Slot for value %d is %d",val,slot);

break;

case 2:

printf("\n Enter the value to be searched :");

scanf("%d",&val);

slot=val%h1size;

if(h1[slot]==val) printf("\n %d is found at slot %d ",val,slot);

else printf("\n %d is not found ",val);

break;

case 3:

printf(" \n Good Bye .. ");

break;

}

}while(key!=3);

printf("\n Thank you for using codingstreet.com 's DataStructure Solutions\n");

return 0;;

}

C Array, C Code, stack

Stack implementation using array in C

June 19, 2013 admin

Stack implementation using array in C

Stack has following operations :

push // To add value at top of stack

pop // To remove value from top of stack

isstack_empty // To check whether stack is empty or not

isstack_full // To check whether stack is full or not

/* Integer Stack implementation using array , Code by codingstreet.com */
#include<stdio.h>
int push(int *stack,int val,int *top,int *size);
int pop(int *stack,int *top);
int isstack_empty(int *top);
int isstack_full(int *top,int *size);
int isstack_empty(int *top){
    if((*top)==0) return 1;
    return 0;
}
int isstack_full(int *top,int *size){
    if((*top)==(*size)-1) return 1;
    return 0;
}
int push(int *stack,int val,int *top,int *size){
    if(isstack_full(top,size)){
        return 0;
    }
    stack[(*top)++]=val;
    return 1;
}
int pop(int *stack,int *top){
    if(isstack_empty(top)){
        return -1;
    }
    else return stack[--(*top)];
}
int main(){
int sstack[10],ssize=10,stop=0;
push(sstack,10,&stop,&ssize);
push(sstack,101,&stop,&ssize);
printf(" %d ",pop(sstack,&stop));
printf(" %d ",pop(sstack,&stop));
printf("\n Thank you for using codingstreet.com 's Datastructure Solutions ");
return 0;
}

/* Integer Stack implementation using array , Code by codingstreet.com */

#include<stdio.h>

int push(int *stack,int val,int *top,int *size);

int pop(int *stack,int *top);

int isstack_empty(int *top);

int isstack_full(int *top,int *size);

int isstack_empty(int *top){

if((*top)==0) return 1;

return 0;

}

int isstack_full(int *top,int *size){

if((*top)==(*size)-1) return 1;

return 0;

}

int push(int *stack,int val,int *top,int *size){

if(isstack_full(top,size)){

return 0;

}

stack[(*top)++]=val;

return 1;

}

int pop(int *stack,int *top){

if(isstack_empty(top)){

return -1;

}

else return stack[--(*top)];

}

int main(){

int sstack[10],ssize=10,stop=0;

push(sstack,10,&stop,&ssize);

push(sstack,101,&stop,&ssize);

printf(" %d ",pop(sstack,&stop));

printf("\n Thank you for using codingstreet.com 's Datastructure Solutions ");

return 0;

}

Stack implementation using array in C

C Array, C Code, play with numbers

count perfect numbers c program

June 18, 2013 admin

Counting perfect numbers c program in array :

A perfect number is a positive integer that is equal to the sum of its integer positive divisors(excluding itself).

To know list of perfect nos click here

/*Counting perfect nos Code by Codingstreet.com */
#include<stdio.h>
int getsumoffactors(int n){
    int i=1,sum=0;
    while(i<n){
        if(n%i==0) sum+=i;
    i++;
    }
return sum;
}
int countPerfectNumbers(int num[],int size){
int i,count=0,rv;
    for(i=0;i<size;i++){
    rv=getsumoffactors(num[i]);
    if(rv==num[i]) count++;
    }
return count;
}
int main(){
int A[]={6,5,28,496,8128,55};
printf("%d",countPerfectNumbers(A,6));
printf("\n Thankyou for using Codingstreet.com 's solution ");
return 0;
}

/*Counting perfect nos Code by Codingstreet.com */

#include<stdio.h>

int getsumoffactors(int n){

int i=1,sum=0;

while(i<n){

if(n%i==0) sum+=i;

i++;

}

return sum;

}

int countPerfectNumbers(int num[],int size){

int i,count=0,rv;

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

rv=getsumoffactors(num[i]);

if(rv==num[i]) count++;

}

return count;

}

int main(){

int A[]={6,5,28,496,8128,55};

printf("%d",countPerfectNumbers(A,6));

printf("\n Thankyou for using Codingstreet.com 's solution ");

return 0;

}

C Array, C Code, Sorting

Bubble sort on array

June 7, 2013 admin

Algorithm: Bubble Sort

Code:

/*bubble sort on array by codingstreet.com */
#include<stdio.h>
void swap(int *p,int *q){
int t;
t=*p;
*p=*q;
*q=t;
}
void bubblesort(int A[],int size){
	int i,j;
	for(i=0;i<size;i++){
		for(j=size-1;j>=i+1;j--){
			if(A[j]<A[j-1])
				swap(&A[j],&A[j-1]);
			}
		}
}
int main(){
	int A[]={9,8,7,6,5,4},i;
	bubblesort(A,6);
	for(i=0;i<6;i++)
		printf(" %d ",A[i]);
return 0;
}

/*bubble sort on array by codingstreet.com */

#include<stdio.h>

void swap(int *p,int *q){

int t;

t=*p;

*p=*q;

*q=t;

}

void bubblesort(int A[],int size){

int i,j;

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

for(j=size-1;j>=i+1;j--){

if(A[j]<A[j-1])

swap(&A[j],&A[j-1]);

}

int main(){

int A[]={9,8,7,6,5,4},i;

bubblesort(A,6);

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

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

return 0;

}

A place to brush your coding skills