C_Programs_60_Prograsbjssbsbsjsbwbshms.pptx

Whiswbwbsisb

1. C Programming — Full Deck — 60 Programs DESCRIPTION A curated set of C programs from basics to advanced data structures & algorithms. Each slide has AIM, CODE, and sample INPUT/OUTPUT with a large code-themed image on the right.

2. 1) Hello World AIM Print 'Hello, World!' to the console. CODE # include < stdio . h > int main ( ) { printf ( "Hello, World!\n" ) ; return ; } INPUT / OUTPUT Input: (none)
Output:
Hello, World!

3. 2) Sum of Two Numbers AIM Read two integers and print their sum. CODE # include < stdio . h > int main ( ) { int a , b ; scanf ( "%d %d" , & a , & b ) ; printf ( "%d\n" , a + b ) ; return ; } INPUT / OUTPUT Input:
3 7
Output:
10

4. 3) Even or Odd AIM Check whether a number is even or odd. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; if ( n % 2 = = ) printf ( "Even\n" ) ; else printf ( "Odd\n" ) ; return ; } INPUT / OUTPUT Input:
5
Output:
Odd

5. 4) Factorial (Iterative) AIM Compute factorial of a non-negative integer using iteration. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; long long f = 1 ; for ( int i = 2 ; i < = n ; i + + ) f * = i ; printf ( "%lld\n" , f ) ; return ; } INPUT / OUTPUT Input:
5
Output:
120

6. 5) Fibonacci (N terms) AIM Print first N Fibonacci numbers. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; long long a = , b = 1 ; for ( int i = ; i < n ; i + + ) { printf ( "%lld " , a ) ; long long c = a + b ; a = b ; b = c ; } printf ( "\n" ) ; return ; } INPUT / OUTPUT Input:
7
Output:
0 1 1 2 3 5 8

7. 6) Prime Check AIM Determine if a number is prime. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; if ( n < 2 ) { printf ( "Not Prime\n" ) ; return ; } for ( int i = 2 ; i * i < = n ; i + + ) if ( n % i = = ) { printf ( "Not Prime\n" ) ; return ; } printf ( "Prime\n" ) ; return ; } INPUT / OUTPUT Input:
13
Output:
Prime

8. 7) Reverse an Integer AIM Reverse the digits of an integer. CODE # include < stdio . h > int main ( ) { long long n ; scanf ( "%lld" , & n ) ; long long r = ; while ( n ) { r = r * 10 + n % 10 ; n / = 10 ; } printf ( "%lld\n" , r ) ; return ; } INPUT / OUTPUT Input:
1205
Output:
5021

9. 8) Palindrome Number AIM Check if an integer is a palindrome. CODE # include < stdio . h > int main ( ) { int n , x , r = ; scanf ( "%d" , & n ) ; x = n ; while ( x ) { r = r * 10 + x % 10 ; x / = 10 ; } if ( r = = n ) printf ( "Palindrome\n" ) ; else printf ( "Not Palindrome\n" ) ; return ; } INPUT / OUTPUT Input:
121
Output:
Palindrome

10. 9) GCD (Euclid) AIM Compute GCD of two integers using Euclid's algorithm. CODE # include < stdio . h > int gcd ( int a , int b ) { while ( b ) { int t = a % b ; a = b ; b = t ; } return a ; } int main ( ) { int a , b ; scanf ( "%d%d" , & a , & b ) ; printf ( "%d\n" , gcd ( a , b ) ) ; } INPUT / OUTPUT Input:
54 24
Output:
6

11. 10) LCM using GCD AIM Compute LCM of two integers via GCD. CODE # include < stdio . h > long long gcd ( long long a , long long b ) { while ( b ) { long long t = a % b ; a = b ; b = t ; } return a ; } int main ( ) { long long a , b ; scanf ( "%lld%lld" , & a , & b ) ; printf ( "%lld\n" , a / gcd ( a , b ) * b ) ; } INPUT / OUTPUT Input:
12 18
Output:
36

12. 11) Swap Without Temp AIM Swap two integers without using a third variable. CODE # include < stdio . h > int main ( ) { int a , b ; scanf ( "%d%d" , & a , & b ) ; a ^ = b ; b ^ = a ; a ^ = b ; printf ( "%d %d\n" , a , b ) ; } INPUT / OUTPUT Input:
2 5
Output:
5 2

13. 12) Array Sum AIM Sum of N integers in an array. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; long long s = ; for ( int i = , x ; i < n ; i + + ) { scanf ( "%d" , & x ) ; s + = x ; } printf ( "%lld\n" , s ) ; } INPUT / OUTPUT Input:
5
1 2 3 4 5
Output:
15

14. 13) Max Element in Array AIM Find maximum element in an array. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; int mx = - 2147483648 , x ; for ( int i = ; i < n ; i + + ) { scanf ( "%d" , & x ) ; if ( x > mx ) mx = x ; } printf ( "%d\n" , mx ) ; } INPUT / OUTPUT Input:
5
-5 2 9 1 0
Output:
9

15. 14) Linear Search AIM Find index of a key in array using linear search. CODE # include < stdio . h > int main ( ) { int n , key ; scanf ( "%d" , & n ) ; int a [ n ] ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & a [ i ] ) ; scanf ( "%d" , & key ) ; for ( int i = ; i < n ; i + + ) if ( a [ i ] = = key ) { printf ( "%d\n" , i ) ; return ; } printf ( "-1\n" ) ; } INPUT / OUTPUT Input:
5
4 1 7 9 2
7
Output:
2

16. 15) Binary Search AIM Binary search on a sorted array. CODE # include < stdio . h > int main ( ) { int n , key ; scanf ( "%d" , & n ) ; int a [ n ] ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & a [ i ] ) ; scanf ( "%d" , & key ) ; int l = , r = n - 1 ; while ( l < = r ) { int m = ( l + r ) / 2 ; if ( a [ m ] = = key ) { printf ( "%d\n" , m ) ; return ; } else if ( a [ m ] < key ) l = m + 1 ; else r = m - 1 ; } printf ( "-1\n" ) ; } INPUT / OUTPUT Input:
5
1 3 5 7 9
7
Output:
3

17. 16) Bubble Sort AIM Sort an array using Bubble Sort. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; int a [ n ] ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & a [ i ] ) ; for ( int i = ; i < n - 1 ; i + + ) for ( int j = ; j < n - 1 - i ; j + + ) if ( a [ j ] > a [ j + 1 ] ) { int t = a [ j ] ; a [ j ] = a [ j + 1 ] ; a [ j + 1 ] = t ; } for ( int i = ; i < n ; i + + ) printf ( "%d " , a [ i ] ) ; printf ( "\n" ) ; } INPUT / OUTPUT Input:
5
5 1 4 2 8
Output:
1 2 4 5 8

18. 17) Selection Sort AIM Sort an array using Selection Sort. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; int a [ n ] ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & a [ i ] ) ; for ( int i = ; i < n - 1 ; i + + ) { int m = i ; for ( int j = i + 1 ; j < n ; j + + ) if ( a [ j ] < a [ m ] ) m = j ; int t = a [ i ] ; a [ i ] = a [ m ] ; a [ m ] = t ; } for ( int i = ; i < n ; i + + ) printf ( "%d " , a [ i ] ) ; printf ( "\n" ) ; } INPUT / OUTPUT Input:
5
64 25 12 22 11
Output:
11 12 22 25 64

19. 18) Insertion Sort AIM Sort an array using Insertion Sort. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; int a [ n ] ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & a [ i ] ) ; for ( int i = 1 ; i < n ; i + + ) { int key = a [ i ] , j = i - 1 ; while ( j > = & & a [ j ] > key ) { a [ j + 1 ] = a [ j ] ; j - - ; } a [ j + 1 ] = key ; } for ( int i = ; i < n ; i + + ) printf ( "%d " , a [ i ] ) ; printf ( "\n" ) ; } INPUT / OUTPUT Input:
5
12 11 13 5 6
Output:
5 6 11 12 13

20. 19) String Length AIM Find length of a string (without strlen). CODE # include < stdio . h > int main ( ) { char s [ 1000 ] ; fgets ( s , 1000 , stdin ) ; int len = ; while ( s [ len ] & & s [ len ] ! = '\n' ) len + + ; printf ( "%d\n" , len ) ; } INPUT / OUTPUT Input:
hello
Output:
5

21. 20) String Reverse AIM Reverse a string in place. CODE # include < stdio . h > # include < string . h > int main ( ) { char s [ 1000 ] ; fgets ( s , 1000 , stdin ) ; int n = strlen ( s ) ; if ( n & & s [ n - 1 ] = = '\n' ) s [ - - n ] = ; for ( int i = ; i < n / 2 ; i + + ) { char t = s [ i ] ; s [ i ] = s [ n - 1 - i ] ; s [ n - 1 - i ] = t ; } printf ( "%s\n" , s ) ; } INPUT / OUTPUT Input:
abcde
Output:
edcba

22. 21) Count Vowels AIM Count vowels in a string. CODE # include < stdio . h > # include < ctype . h > int main ( ) { char s [ 1000 ] ; fgets ( s , 1000 , stdin ) ; int c = ; for ( int i = ; s [ i ] ; i + + ) { char ch = tolower ( s [ i ] ) ; if ( ch = = 'a' | | ch = = 'e' | | ch = = 'i' | | ch = = 'o' | | ch = = 'u' ) c + + ; } printf ( "%d\n" , c ) ; } INPUT / OUTPUT Input:
Hello World
Output:
3

23. 22) Matrix Addition AIM Add two matrices of size r x c. CODE # include < stdio . h > int main ( ) { int r , c ; scanf ( "%d%d" , & r , & c ) ; int A [ r ] [ c ] , B [ r ] [ c ] ; for ( int i = ; i < r ; i + + ) for ( int j = ; j < c ; j + + ) scanf ( "%d" , & A [ i ] [ j ] ) ; for ( int i = ; i < r ; i + + ) for ( int j = ; j < c ; j + + ) scanf ( "%d" , & B [ i ] [ j ] ) ; for ( int i = ; i < r ; i + + ) { for ( int j = ; j < c ; j + + ) { printf ( "%d " , A [ i ] [ j ] + B [ i ] [ j ] ) ; } printf ( "\n" ) ; } } INPUT / OUTPUT Input:
2 2
1 2
3 4
5 6
7 8
Output:
6 8
10 12

24. 23) Matrix Multiplication AIM Multiply matrices A (r1 x c1) and B (r2 x c2) when c1==r2. CODE # include < stdio . h > int main ( ) { int r1 , c1 , r2 , c2 ; scanf ( "%d%d%d%d" , & r1 , & c1 , & r2 , & c2 ) ; if ( c1 ! = r2 ) { printf ( "Invalid\n" ) ; return ; } int A [ r1 ] [ c1 ] , B [ r2 ] [ c2 ] , C [ r1 ] [ c2 ] ; for ( int i = ; i < r1 ; i + + ) for ( int j = ; j < c1 ; j + + ) scanf ( "%d" , & A [ i ] [ j ] ) ; for ( int i = ; i < r2 ; i + + ) for ( int j = ; j < c2 ; j + + ) scanf ( "%d" , & B [ i ] [ j ] ) ; for ( int i = ; i < r1 ; i + + ) for ( int j = ; j < c2 ; j + + ) { C [ i ] [ j ] = ; for ( int k = ; k < c1 ; k + + ) C [ i ] [ j ] + = A [ i ] [ k ] * B [ k ] [ j ] ; } for ( int i = ; i < r1 ; i + + ) { for ( int j = ; j < c2 ; j + + ) printf ( "%d " , C [ i ] [ j ] ) ; printf ( "\n" ) ; } } INPUT / OUTPUT Input:
2 3 3 2
1 2 3
4 5 6
1 2
3 4
5 6
Output:
22 28
49 64

25. 24) Recursive Factorial AIM Compute factorial using recursion. CODE # include < stdio . h > long long fact ( int n ) { return n < 2 ? 1 : n * fact ( n - 1 ) ; } int main ( ) { int n ; scanf ( "%d" , & n ) ; printf ( "%lld\n" , fact ( n ) ) ; } INPUT / OUTPUT Input:
6
Output:
720

26. 25) Recursive Fibonacci AIM Compute n-th Fibonacci using recursion. CODE # include < stdio . h > long long fib ( int n ) { return n < 2 ? n : fib ( n - 1 ) + fib ( n - 2 ) ; } int main ( ) { int n ; scanf ( "%d" , & n ) ; printf ( "%lld\n" , fib ( n ) ) ; } INPUT / OUTPUT Input:
7
Output:
13

27. 26) Pointer Basics AIM Demonstrate pointer usage by swapping two integers via function. CODE # include < stdio . h > void swap ( int * a , int * b ) { int t = * a ; * a = * b ; * b = t ; } int main ( ) { int x , y ; scanf ( "%d%d" , & x , & y ) ; swap ( & x , & y ) ; printf ( "%d %d\n" , x , y ) ; } INPUT / OUTPUT Input:
10 20
Output:
20 10

28. 27) File Write AIM Write lines to a file named out.txt. CODE # include < stdio . h > int main ( ) { FILE * f = fopen ( "out.txt" , "w" ) ; if ( ! f ) { printf ( "Error\n" ) ; return ; } fprintf ( f , "Hello File\n" ) ; fclose ( f ) ; printf ( "Done\n" ) ; } INPUT / OUTPUT Input:
(none)
Output:
Done (creates out.txt)

29. 28) File Read AIM Read a file input.txt and print contents. CODE # include < stdio . h > int main ( ) { FILE * f = fopen ( "input.txt" , "r" ) ; if ( ! f ) { printf ( "Error\n" ) ; return ; } int ch ; while ( ( ch = fgetc ( f ) ) ! = EOF ) putchar ( ch ) ; fclose ( f ) ; } INPUT / OUTPUT Input:
(input.txt exists)
Output:
(contents printed)

30. 29) Count Words in File AIM Count words in a text file. CODE # include < stdio . h > # include < ctype . h > int main ( ) { FILE * f = fopen ( "input.txt" , "r" ) ; if ( ! f ) { printf ( "Error\n" ) ; return ; } int c , inw = , cnt = ; while ( ( c = fgetc ( f ) ) ! = EOF ) { if ( isspace ( c ) ) inw = ; else if ( ! inw ) { inw = 1 ; cnt + + ; } } printf ( "%d\n" , cnt ) ; fclose ( f ) ; } INPUT / OUTPUT Input:
(input.txt)
Output:
<number of words>

31. 30) Structure (Student) AIM Use struct to store and print student details. CODE # include < stdio . h > struct Student { char name [ 50 ] ; int age ; float cgpa ; } ; int main ( ) { struct Student s = { "Amit" , 20 , 8 . 5 } ; printf ( "%s %d %.1f\n" , s . name , s . age , s . cgpa ) ; } INPUT / OUTPUT Input:
(none)
Output:
Amit 20 8.5

32. 31) Dynamic Memory (malloc) AIM Allocate array dynamically and compute average. CODE # include < stdio . h > # include < stdlib . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; int * a = malloc ( n * sizeof ( int ) ) ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & a [ i ] ) ; long long s = ; for ( int i = ; i < n ; i + + ) s + = a [ i ] ; printf ( "%.2f\n" , ( double ) s / n ) ; free ( a ) ; } INPUT / OUTPUT Input:
4
1 2 3 6
Output:
3.00

33. 32) Command-line Args AIM Print all command-line arguments. CODE # include < stdio . h > int main ( int argc , char * argv [ ] ) { for ( int i = ; i < argc ; i + + ) printf ( "%s\n" , argv [ i ] ) ; } INPUT / OUTPUT Run:
./a.out one two
Output:
./a.out
one
two

34. 33) Bit Count (Brian Kernighan) AIM Count set bits in an integer. CODE # include < stdio . h > int main ( ) { unsigned int x ; scanf ( "%u" , & x ) ; int c = ; while ( x ) { x & = x - 1 ; c + + ; } printf ( "%d\n" , c ) ; } INPUT / OUTPUT Input:
13
Output:
3

35. 34) Endianness Check AIM Detect system endianness. CODE # include < stdio . h > int main ( ) { unsigned int x = 1 ; char * c = ( char * ) & x ; printf ( * c ? "Little\n" : "Big\n" ) ; } INPUT / OUTPUT Input:
(none)
Output:
Little (usually)

36. 35) Pointer to Function AIM Use a function pointer to call add. CODE # include < stdio . h > int add ( int a , int b ) { return a + b ; } int main ( ) { int ( * fp ) ( int , int ) = add ; printf ( "%d\n" , fp ( 2 , 3 ) ) ; } INPUT / OUTPUT Input:
(none)
Output:
5

37. 36) Singly Linked List (Insert & Print) AIM Create a singly linked list and print it. CODE # include < stdio . h > # include < stdlib . h > typedef struct Node { int data ; struct Node * next ; } Node ; Node * push ( Node * head , int x ) { Node * n = malloc ( sizeof ( Node ) ) ; n - > data = x ; n - > next = head ; return n ; } void print ( Node * h ) { for ( ; h ; h = h - > next ) printf ( "%d " , h - > data ) ; printf ( "\n" ) ; } int main ( ) { Node * head = NULL ; head = push ( head , 3 ) ; head = push ( head , 2 ) ; head = push ( head , 1 ) ; print ( head ) ; } INPUT / OUTPUT Input:
(none)
Output:
1 2 3

38. 37) Stack (Array) AIM Implement stack using array (push/pop/top). CODE # include < stdio . h > # define N 100 int a [ N ] , top = - 1 ; void push ( int x ) { a [ + + top ] = x ; } int pop ( ) { return a [ top - - ] ; } int main ( ) { push ( 1 ) ; push ( 2 ) ; printf ( "%d\n" , pop ( ) ) ; } INPUT / OUTPUT Input:
(none)
Output:
2

39. 38) Queue (Array) AIM Implement circular queue using array. CODE # include < stdio . h > # define N 5 int q [ N ] , f = , r = , sz = ; void enq ( int x ) { if ( sz < N ) { q [ r ] = x ; r = ( r + 1 ) % N ; sz + + ; } } int deq ( ) { int v = q [ f ] ; f = ( f + 1 ) % N ; sz - - ; return v ; } int main ( ) { enq ( 10 ) ; enq ( 20 ) ; printf ( "%d\n" , deq ( ) ) ; } INPUT / OUTPUT Input:
(none)
Output:
10

40. 39) Stack (Linked List) AIM Stack using linked list (push/pop). CODE # include < stdio . h > # include < stdlib . h > typedef struct Node { int d ; struct Node * n ; } Node ; Node * top = NULL ; void push ( int x ) { Node * t = malloc ( sizeof ( Node ) ) ; t - > d = x ; t - > n = top ; top = t ; } int pop ( ) { int v = top - > d ; Node * t = top ; top = top - > n ; free ( t ) ; return v ; } int main ( ) { push ( 5 ) ; push ( 7 ) ; printf ( "%d\n" , pop ( ) ) ; } INPUT / OUTPUT Input:
(none)
Output:
7

41. 40) Queue (Linked List) AIM Queue using linked list (enqueue/dequeue). CODE # include < stdio . h > # include < stdlib . h > typedef struct Node { int d ; struct Node * n ; } Node ; Node * f = NULL ; Node * r = NULL ; void enq ( int x ) { Node * t = malloc ( sizeof ( Node ) ) ; t - > d = x ; t - > n = NULL ; if ( ! r ) f = r = t ; else { r - > n = t ; r = t ; } } int deq ( ) { int v = f - > d ; Node * t = f ; f = f - > n ; if ( ! f ) r = NULL ; free ( t ) ; return v ; } int main ( ) { enq ( 1 ) ; enq ( 2 ) ; printf ( "%d\n" , deq ( ) ) ; } INPUT / OUTPUT Input:
(none)
Output:
1

42. 41) Binary Search Tree (Insert & Inorder) AIM Insert into BST and print inorder traversal. CODE # include < stdio . h > # include < stdlib . h > typedef struct Node { int k ; struct Node * l ; struct Node * r ; } Node ; Node * newN ( int k ) { Node * n = malloc ( sizeof ( Node ) ) ; n - > k = k ; n - > l = n - > r = NULL ; return n ; } Node * ins ( Node * root , int k ) { if ( ! root ) return newN ( k ) ; if ( k < root - > k ) root - > l = ins ( root - > l , k ) ; else root - > r = ins ( root - > r , k ) ; return root ; } void inorder ( Node * r ) { if ( ! r ) return ; inorder ( r - > l ) ; printf ( "%d " , r - > k ) ; inorder ( r - > r ) ; } int main ( ) { Node * r = NULL ; r = ins ( r , 5 ) ; r = ins ( r , 3 ) ; r = ins ( r , 7 ) ; inorder ( r ) ; } INPUT / OUTPUT Input:
(none)
Output:
3 5 7

43. 42) BST Search AIM Search a key in a BST. CODE # include < stdio . h > # include < stdlib . h > typedef struct Node { int k ; struct Node * l ; struct Node * r ; } Node ; Node * newN ( int k ) { Node * n = malloc ( sizeof ( Node ) ) ; n - > k = k ; n - > l = n - > r = NULL ; return n ; } Node * ins ( Node * root , int k ) { if ( ! root ) return newN ( k ) ; if ( k < root - > k ) root - > l = ins ( root - > l , k ) ; else root - > r = ins ( root - > r , k ) ; return root ; } int find ( Node * r , int k ) { if ( ! r ) return ; if ( k = = r - > k ) return 1 ; return k < r - > k ? find ( r - > l , k ) : find ( r - > r , k ) ; } int main ( ) { Node * r = NULL ; int a [ ] = { 5 , 2 , 8 , 1 , 3 } ; for ( int i = ; i < 5 ; i + + ) r = ins ( r , a [ i ] ) ; printf ( find ( r , 3 ) ? "Found\n" : "Not Found\n" ) ; } INPUT / OUTPUT Input:
(none)
Output:
Found

44. 43) Heap (Min-Heap) AIM Build a min-heap and extract minimum. CODE # include < stdio . h > # define N 100 int h [ N ] , sz = ; void up ( int i ) { while ( i > 1 & & h [ i ] < h [ i / 2 ] ) { int t = h [ i ] ; h [ i ] = h [ i / 2 ] ; h [ i / 2 ] = t ; i / = 2 ; } } void down ( int i ) { while ( 2 * i < = sz ) { int j = 2 * i ; if ( j + 1 < = sz & & h [ j + 1 ] < h [ j ] ) j + + ; if ( h [ i ] < = h [ j ] ) break ; int t = h [ i ] ; h [ i ] = h [ j ] ; h [ j ] = t ; i = j ; } } void push ( int x ) { h [ + + sz ] = x ; up ( sz ) ; } int pop ( ) { int v = h [ 1 ] ; h [ 1 ] = h [ sz - - ] ; down ( 1 ) ; return v ; } int main ( ) { push ( 5 ) ; push ( 2 ) ; push ( 8 ) ; printf ( "%d\n" , pop ( ) ) ; } INPUT / OUTPUT Input:
(none)
Output:
2

45. 44) Quick Sort AIM Sort an array using Quick Sort (Lomuto). CODE # include < stdio . h > void qs ( int a [ ] , int l , int r ) { if ( l > = r ) return ; int p = a [ r ] , i = l ; for ( int j = l ; j < r ; j + + ) if ( a [ j ] < p ) { int t = a [ i ] ; a [ i ] = a [ j ] ; a [ j ] = t ; i + + ; } int t = a [ i ] ; a [ i ] = a [ r ] ; a [ r ] = t ; qs ( a , l , i - 1 ) ; qs ( a , i + 1 , r ) ; } int main ( ) { int n ; scanf ( "%d" , & n ) ; int a [ n ] ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & a [ i ] ) ; qs ( a , , n - 1 ) ; for ( int i = ; i < n ; i + + ) printf ( "%d " , a [ i ] ) ; } INPUT / OUTPUT Input:
5
3 5 1 4 2
Output:
1 2 3 4 5

46. 45) Merge Sort AIM Sort an array using Merge Sort. CODE # include < stdio . h > void merge ( int a [ ] , int l , int m , int r ) { int n1 = m - l + 1 , n2 = r - m ; int L [ n1 ] , R [ n2 ] ; for ( int i = ; i < n1 ; i + + ) L [ i ] = a [ l + i ] ; for ( int j = ; j < n2 ; j + + ) R [ j ] = a [ m + 1 + j ] ; int i = , j = , k = l ; while ( i < n1 & & j < n2 ) a [ k + + ] = ( L [ i ] < = R [ j ] ) ? L [ i + + ] : R [ j + + ] ; while ( i < n1 ) a [ k + + ] = L [ i + + ] ; while ( j < n2 ) a [ k + + ] = R [ j + + ] ; } void ms ( int a [ ] , int l , int r ) { if ( l < r ) { int m = ( l + r ) / 2 ; ms ( a , l , m ) ; ms ( a , m + 1 , r ) ; merge ( a , l , m , r ) ; } } int main ( ) { int n ; scanf ( "%d" , & n ) ; int a [ n ] ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & a [ i ] ) ; ms ( a , , n - 1 ) ; for ( int i = ; i < n ; i + + ) printf ( "%d " , a [ i ] ) ; } INPUT / OUTPUT Input:
6
6 5 3 1 8 7
Output:
1 3 5 6 7 8

47. 46) DFS (Graph Adjacency Matrix) AIM Depth-first search traversal from node 0. CODE # include < stdio . h > int vis [ 100 ] ; int g [ 100 ] [ 100 ] ; int n ; void dfs ( int u ) { vis [ u ] = 1 ; printf ( "%d " , u ) ; for ( int v = ; v < n ; v + + ) if ( g [ u ] [ v ] & & ! vis [ v ] ) dfs ( v ) ; } int main ( ) { scanf ( "%d" , & n ) ; for ( int i = ; i < n ; i + + ) for ( int j = ; j < n ; j + + ) scanf ( "%d" , & g [ i ] [ j ] ) ; dfs ( ) ; } INPUT / OUTPUT Input:
4
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
Output:
0 1 2 3

48. 47) BFS (Graph Adjacency Matrix) AIM Breadth-first search traversal from node 0. CODE # include < stdio . h > int vis [ 100 ] ; int g [ 100 ] [ 100 ] ; int n ; int q [ 1000 ] , f = , r = ; void bfs ( int s ) { vis [ s ] = 1 ; q [ r + + ] = s ; while ( f < r ) { int u = q [ f + + ] ; printf ( "%d " , u ) ; for ( int v = ; v < n ; v + + ) if ( g [ u ] [ v ] & & ! vis [ v ] ) { vis [ v ] = 1 ; q [ r + + ] = v ; } } } int main ( ) { scanf ( "%d" , & n ) ; for ( int i = ; i < n ; i + + ) for ( int j = ; j < n ; j + + ) scanf ( "%d" , & g [ i ] [ j ] ) ; bfs ( ) ; } INPUT / OUTPUT Input:
4
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
Output:
0 1 2 3

49. 48) Dijkstra (Adjacency Matrix) AIM Single-source shortest paths using Dijkstra. CODE # include < stdio . h > # define INF 1000000000 int g [ 100 ] [ 100 ] , n ; int main ( ) { scanf ( "%d" , & n ) ; for ( int i = ; i < n ; i + + ) for ( int j = ; j < n ; j + + ) scanf ( "%d" , & g [ i ] [ j ] ) ; int s = ; int d [ 100 ] , vis [ 100 ] = { } ; for ( int i = ; i < n ; i + + ) d [ i ] = INF ; d [ s ] = ; for ( int i = ; i < n ; i + + ) { int u = - 1 ; for ( int v = ; v < n ; v + + ) if ( ! vis [ v ] & & ( u = = - 1 | | d [ v ] < d [ u ] ) ) u = v ; vis [ u ] = 1 ; for ( int v = ; v < n ; v + + ) if ( g [ u ] [ v ] > & & d [ u ] + g [ u ] [ v ] < d [ v ] ) d [ v ] = d [ u ] + g [ u ] [ v ] ; } for ( int i = ; i < n ; i + + ) printf ( "%d " , d [ i ] ) ; } INPUT / OUTPUT Input:
3
0 1 4
1 0 2
4 2 0
Output:
0 1 3

50. 49) Topological Sort (DFS) AIM Topological ordering of DAG using DFS. CODE # include < stdio . h > int n ; int g [ 100 ] [ 100 ] ; int vis [ 100 ] ; int st [ 100 ] , top = ; void dfs ( int u ) { vis [ u ] = 1 ; for ( int v = ; v < n ; v + + ) if ( g [ u ] [ v ] & & ! vis [ v ] ) dfs ( v ) ; st [ top + + ] = u ; } int main ( ) { scanf ( "%d" , & n ) ; for ( int i = ; i < n ; i + + ) for ( int j = ; j < n ; j + + ) scanf ( "%d" , & g [ i ] [ j ] ) ; for ( int i = ; i < n ; i + + ) if ( ! vis [ i ] ) dfs ( i ) ; while ( top ) printf ( "%d " , st [ - - top ] ) ; } INPUT / OUTPUT Input:
4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
Output:
0 1 2 3

51. 50) KMP String Search AIM Find pattern occurrences using KMP. CODE # include < stdio . h > # include < string . h > int lps [ 1000 ] ; void build ( char * p ) { int m = strlen ( p ) , len = ; lps [ ] = ; for ( int i = 1 ; i < m ; ) { if ( p [ i ] = = p [ len ] ) lps [ i + + ] = + + len ; else if ( len ) len = lps [ len - 1 ] ; else lps [ i + + ] = ; } } void kmp ( char * t , char * p ) { int n = strlen ( t ) , m = strlen ( p ) ; build ( p ) ; int i = , j = ; while ( i < n ) { if ( t [ i ] = = p [ j ] ) { i + + ; j + + ; if ( j = = m ) { printf ( "%d " , i - m ) ; j = lps [ j - 1 ] ; } } else if ( j ) j = lps [ j - 1 ] ; else i + + ; } } int main ( ) { char t [ 1000 ] , p [ 1000 ] ; gets ( t ) ; gets ( p ) ; kmp ( t , p ) ; } INPUT / OUTPUT Input:
ABABDABACDABABCABAB
ABABCABAB
Output:
10

52. 51) Longest Common Subsequence (DP) AIM Length of LCS using DP. CODE # include < stdio . h > # include < string . h > int dp [ 1001 ] [ 1001 ] ; int max ( int a , int b ) { return a > b ? a : b ; } int main ( ) { char a [ 1001 ] , b [ 1001 ] ; gets ( a ) ; gets ( b ) ; int n = strlen ( a ) , m = strlen ( b ) ; for ( int i = 1 ; i < = n ; i + + ) for ( int j = 1 ; j < = m ; j + + ) dp [ i ] [ j ] = ( a [ i - 1 ] = = b [ j - 1 ] ) ? dp [ i - 1 ] [ j - 1 ] + 1 : max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ; printf ( "%d\n" , dp [ n ] [ m ] ) ; } INPUT / OUTPUT Input:
AGGTAB
GXTXAYB
Output:
4

53. 52) 0/1 Knapsack (DP) AIM Compute max value for knapsack capacity W. CODE # include < stdio . h > int max ( int a , int b ) { return a > b ? a : b ; } int dp [ 201 ] [ 2001 ] ; int main ( ) { int n , W ; scanf ( "%d%d" , & n , & W ) ; int wt [ n ] , val [ n ] ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & wt [ i ] ) ; for ( int i = ; i < n ; i + + ) scanf ( "%d" , & val [ i ] ) ; for ( int i = 1 ; i < = n ; i + + ) for ( int w = ; w < = W ; w + + ) { dp [ i ] [ w ] = dp [ i - 1 ] [ w ] ; if ( wt [ i - 1 ] < = w ) dp [ i ] [ w ] = max ( dp [ i ] [ w ] , val [ i - 1 ] + dp [ i - 1 ] [ w - wt [ i - 1 ] ] ) ; } printf ( "%d\n" , dp [ n ] [ W ] ) ; } INPUT / OUTPUT Input:
3 50
10 20 30
60 100 120
Output:
220

54. 53) Union-Find (DSU) AIM Disjoint Set Union with path compression. CODE # include < stdio . h > int p [ 1000 ] , rnk [ 1000 ] ; int f ( int x ) { return p [ x ] = = x ? x : ( p [ x ] = f ( p [ x ] ) ) ; } void u ( int a , int b ) { a = f ( a ) ; b = f ( b ) ; if ( a = = b ) return ; if ( rnk [ a ] < rnk [ b ] ) p [ a ] = b ; else if ( rnk [ b ] < rnk [ a ] ) p [ b ] = a ; else { p [ b ] = a ; rnk [ a ] + + ; } } int main ( ) { int n = 5 ; for ( int i = ; i < n ; i + + ) { p [ i ] = i ; rnk [ i ] = ; } u ( , 1 ) ; u ( 3 , 4 ) ; printf ( "%d\n" , f ( 1 ) = = f ( ) ) ; } INPUT / OUTPUT Input:
(none)
Output:
1

55. 54) Trie (Lowercase) AIM Insert and search words in a Trie. CODE # include < stdio . h > # include < stdlib . h > typedef struct Node { int end ; struct Node * ch [ 26 ] ; } Node ; Node * newN ( ) { Node * n = calloc ( 1 , sizeof ( Node ) ) ; return n ; } void ins ( Node * r , char * s ) { for ( int i = ; s [ i ] ; i + + ) { int c = s [ i ] - 'a' ; if ( ! r - > ch [ c ] ) r - > ch [ c ] = newN ( ) ; r = r - > ch [ c ] ; } r - > end = 1 ; } int find ( Node * r , char * s ) { for ( int i = ; s [ i ] ; i + + ) { int c = s [ i ] - 'a' ; if ( ! r - > ch [ c ] ) return ; r = r - > ch [ c ] ; } return r - > end ; } int main ( ) { Node * r = newN ( ) ; ins ( r , "cat" ) ; ins ( r , "car" ) ; printf ( "%d %d\n" , find ( r , "cat" ) , find ( r , "can" ) ) ; } INPUT / OUTPUT Input:
(none)
Output:
1 0

56. 55) Producer-Consumer (Basics) AIM Circular buffer demonstration (no threads). CODE # include < stdio . h > # define N 4 int b [ N ] , h = , t = , cnt = ; void put ( int x ) { if ( cnt < N ) { b [ h ] = x ; h = ( h + 1 ) % N ; cnt + + ; } } int get ( ) { int v = b [ t ] ; t = ( t + 1 ) % N ; cnt - - ; return v ; } int main ( ) { put ( 1 ) ; put ( 2 ) ; printf ( "%d\n" , get ( ) ) ; } INPUT / OUTPUT Input:
(none)
Output:
1

57. 56) Rotate Matrix 90° AIM Rotate an N x N matrix by 90 degrees clockwise. CODE # include < stdio . h > int main ( ) { int n ; scanf ( "%d" , & n ) ; int a [ n ] [ n ] ; for ( int i = ; i < n ; i + + ) for ( int j = ; j < n ; j + + ) scanf ( "%d" , & a [ i ] [ j ] ) ; for ( int i = ; i < n ; i + + ) for ( int j = i + 1 ; j < n ; j + + ) { int t = a [ i ] [ j ] ; a [ i ] [ j ] = a [ j ] [ i ] ; a [ j ] [ i ] = t ; } for ( int i = ; i < n ; i + + ) for ( int j = ; j < n / 2 ; j + + ) { int t = a [ i ] [ j ] ; a [ i ] [ j ] = a [ i ] [ n - 1 - j ] ; a [ i ] [ n - 1 - j ] = t ; } for ( int i = ; i < n ; i + + ) { for ( int j = ; j < n ; j + + ) printf ( "%d " , a [ i ] [ j ] ) ; printf ( "\n" ) ; } } INPUT / OUTPUT Input:
3
1 2 3
4 5 6
7 8 9
Output:
7 4 1
8 5 2
9 6 3

58. 57) Spiral Matrix Print AIM Print matrix elements in spiral order. CODE # include < stdio . h > int main ( ) { int r , c ; scanf ( "%d%d" , & r , & c ) ; int a [ r ] [ c ] ; for ( int i = ; i < r ; i + + ) for ( int j = ; j < c ; j + + ) scanf ( "%d" , & a [ i ] [ j ] ) ; int top = , bot = r - 1 , left = , right = c - 1 ; while ( top < = bot & & left < = right ) { for ( int j = left ; j < = right ; j + + ) printf ( "%d " , a [ top ] [ j ] ) ; top + + ; for ( int i = top ; i < = bot ; i + + ) printf ( "%d " , a [ i ] [ right ] ) ; right - - ; if ( top < = bot ) { for ( int j = right ; j > = left ; j - - ) printf ( "%d " , a [ bot ] [ j ] ) ; bot - - ; } if ( left < = right ) { for ( int i = bot ; i > = top ; i - - ) printf ( "%d " , a [ i ] [ left ] ) ; left + + ; } } } INPUT / OUTPUT Input:
3 3
1 2 3
4 5 6
7 8 9
Output:
1 2 3 6 9 8 7 4 5

59. 58) N-Queens (Backtracking, N=4) AIM Solve N-Queens for N=4 and print one solution. CODE # include < stdio . h > int n = 4 , col [ 10 ] , d1 [ 20 ] , d2 [ 20 ] , a [ 10 ] ; int solve ( int r ) { if ( r = = n ) { for ( int i = ; i < n ; i + + ) { for ( int j = ; j < n ; j + + ) printf ( a [ i ] = = j ? "Q " : ". " ) ; printf ( "\n" ) ; } return 1 ; } for ( int c = ; c < n ; c + + ) if ( ! col [ c ] & & ! d1 [ r - c + n ] & & ! d2 [ r + c ] ) { col [ c ] = d1 [ r - c + n ] = d2 [ r + c ] = 1 ; a [ r ] = c ; if ( solve ( r + 1 ) ) return 1 ; col [ c ] = d1 [ r - c + n ] = d2 [ r + c ] = ; } return ; } int main ( ) { solve ( ) ; } INPUT / OUTPUT Input:
(none)
Output:
. Q . .
. . . Q
Q . . .
. . Q .

60. 59) Sudoku Validity Check AIM Check if a 9x9 Sudoku grid is valid (rows/cols/boxes). CODE # include < stdio . h > int row [ 9 ] [ 10 ] , col [ 9 ] [ 10 ] , box [ 9 ] [ 10 ] ; int main ( ) { int a [ 9 ] [ 9 ] ; for ( int i = ; i < 9 ; i + + ) for ( int j = ; j < 9 ; j + + ) scanf ( "%d" , & a [ i ] [ j ] ) ; for ( int i = ; i < 9 ; i + + ) for ( int j = ; j < 9 ; j + + ) { int v = a [ i ] [ j ] ; if ( v < 1 | | v > 9 ) { printf ( "Invalid\n" ) ; return ; } int b = ( i / 3 ) * 3 + j / 3 ; if ( row [ i ] [ v ] | | col [ j ] [ v ] | | box [ b ] [ v ] ) { printf ( "Invalid\n" ) ; return ; } row [ i ] [ v ] = col [ j ] [ v ] = box [ b ] [ v ] = 1 ; } printf ( "Valid\n" ) ; } INPUT / OUTPUT Input:
(9x9 grid)
Output:
Valid/Invalid

61. 60) Big Integer Addition (as String) AIM Add two non-negative big integers given as strings. CODE # include < stdio . h > # include < string . h > int main ( ) { char a [ 1001 ] , b [ 1001 ] , r [ 1005 ] ; gets ( a ) ; gets ( b ) ; int i = strlen ( a ) - 1 , j = strlen ( b ) - 1 , k = , carry = ; while ( i > = | | j > = | | carry ) { int x = i > = ? a [ i - - ] - '0' : ; int y = j > = ? b [ j - - ] - '0' : ; int s = x + y + carry ; r [ k + + ] = ( s % 10 ) + '0' ; carry = s / 10 ; } for ( int t = k - 1 ; t > = ; t - - ) putchar ( r [ t ] ) ; } INPUT / OUTPUT Input:
999
1
Output:
1000