50 C Coding Questions & Programs
🟢 EASY
1. Even or Odd
#include <stdio.h>
int main(void) {
int n;
scanf(“%d”, &n);
printf(“%s”, n % 2 == 0 ? “Even” : “Odd”);
return 0;
}
2. Positive, Negative or Zero
#include <stdio.h>
int main(void) {
int n;
scanf(“%d”, &n);
if (n > 0)
printf(“Positive”);
else if (n < 0)
printf(“Negative”);
else
printf(“Zero”);
return 0;
}
3. Largest of Two Numbers
#include <stdio.h>
int main(void) {
int a, b;
scanf(“%d %d”, &a, &b);
printf(“%d”, a > b ? a : b);
return 0;
}
4. Largest of Three Numbers
#include <stdio.h>
int main(void) {
int a, b, c;
scanf(“%d %d %d”, &a, &b, &c);
int max = a;
if (b > max)
max = b;
if (c > max)
max = c;
printf(“%d”, max);
return 0;
}
5. Smallest of Three Numbers
#include <stdio.h>
int main(void) {
int a, b, c;
scanf(“%d %d %d”, &a, &b, &c);
int min = a;
if (b < min)
min = b;
if (c < min)
min = c;
printf(“%d”, min);
return 0;
}
6. Check Leap Year
#include <stdio.h>
int main(void) {
int year;
scanf(“%d”, &year);
if ((year % 400 == 0) ||
(year % 4 == 0 && year % 100 != 0))
printf(“Leap Year”);
else
printf(“Not a Leap Year”);
return 0;
}
7. Factorial of a Number
#include <stdio.h>
int main(void) {
int n;
unsigned long long fact = 1;
scanf(“%d”, &n);
if (n < 0) {
printf(“Invalid”);
return 0;
}
for (int i = 2; i <= n; i++)
fact *= i;
printf(“%llu”, fact);
return 0;
}
8. Fibonacci Series
#include <stdio.h>
int main(void) {
int n;
long long a = 0, b = 1;
scanf(“%d”, &n);
for (int i = 0; i < n; i++) {
printf(“%lld “, a);
long long next = a + b;
a = b;
b = next;
}
return 0;
}
9. Reverse a Number
#include <stdio.h>
int main(void) {
long long n, rev = 0;
scanf(“%lld”, &n);
long long x = n < 0 ? -n : n;
while (x) {
rev = rev * 10 + x % 10;
x /= 10;
}
printf(“%s%lld”, n < 0 ? “-” : “”, rev);
return 0;
}
10. Check Palindrome Number
#include <stdio.h>
int main(void) {
long long n, x, rev = 0;
scanf(“%lld”, &n);
if (n < 0) {
printf(“Not Palindrome”);
return 0;
}
x = n;
do {
rev = rev * 10 + x % 10;
x /= 10;
} while (x);
printf(“%s”, rev == n ? “Palindrome” : “Not Palindrome”);
return 0;
}
🟡 MEDIUM
11. Prime Number Check
#include <stdio.h>
int main(void) {
int n, prime = 1;
scanf(“%d”, &n);
if (n < 2)
prime = 0;
for (int i = 2; i <= n / i && prime; i++) {
if (n % i == 0)
prime = 0;
}
printf(“%s”, prime ? “Prime” : “Not Prime”);
return 0;
}
12. Print Prime Numbers in a Range
#include <stdio.h>
int main(void) {
int l, r;
scanf(“%d %d”, &l, &r);
for (int n = l; n <= r; n++) {
if (n < 2)
continue;
int prime = 1;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
prime = 0;
break;
}
}
if (prime)
printf(“%d “, n);
}
return 0;
}
13. Armstrong Number
#include <stdio.h>
int power(int b, int e) {
int r = 1;
while (e–)
r *= b;
return r;
}
int main(void) {
int n, x, digits = 0, sum = 0;
scanf(“%d”, &n);
if (n < 0) {
printf(“Not Armstrong”);
return 0;
}
x = n;
do {
digits++;
x /= 10;
} while (x);
x = n;
do {
sum += power(x % 10, digits);
x /= 10;
} while (x);
printf(“%s”, sum == n ? “Armstrong” : “Not Armstrong”);
return 0;
}
14. Perfect Number
#include <stdio.h>
int main(void) {
int n, sum = 1;
scanf(“%d”, &n);
if (n <= 1) {
printf(“Not Perfect”);
return 0;
}
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
sum += i;
if (i != n / i)
sum += n / i;
}
}
printf(“%s”, sum == n ? “Perfect” : “Not Perfect”);
return 0;
}
15. GCD and LCM
#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 < 0 ? -a : a;
}
int main(void) {
long long a, b;
scanf(“%lld %lld”, &a, &b);
long long g = gcd(a, b);
long long l = g ? (a / g) * b : 0;
if (l < 0)
l = -l;
printf(“GCD = %lld\n”, g);
printf(“LCM = %lld”, l);
return 0;
}
16. Count Digits in a Number
#include <stdio.h>
int main(void) {
long long n;
int count = 0;
scanf(“%lld”, &n);
if (n == 0)
count = 1;
else {
if (n < 0)
n = -n;
while (n) {
count++;
n /= 10;
}
}
printf(“%d”, count);
return 0;
}
17. Sum of Digits
#include <stdio.h>
int main(void) {
long long n;
int sum = 0;
scanf(“%lld”, &n);
if (n < 0)
n = -n;
while (n) {
sum += (int)(n % 10);
n /= 10;
}
printf(“%d”, sum);
return 0;
}
18. Reverse Words in a String
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(void) {
char s[1000];
fgets(s, sizeof(s), stdin);
int n = strlen(s);
while (n > 0 && isspace((unsigned char)s[n – 1]))
s[–n] = ‘\0’;
int end = n;
for (int i = n – 1; i >= -1; i–) {
if (i == -1 || s[i] == ‘ ‘) {
int start = i + 1;
if (start < end) {
for (int j = start; j < end; j++)
putchar(s[j]);
if (i != -1)
putchar(‘ ‘);
}
end = i;
while (end >= 0 && s[end] == ‘ ‘)
end–;
i = end;
}
}
return 0;
}
19. Check Whether Two Strings Are Anagrams
#include <stdio.h>
#include <ctype.h>
int main(void) {
char a[1000], b[1000];
int count[256] = {0};
fgets(a, sizeof(a), stdin);
fgets(b, sizeof(b), stdin);
for (int i = 0; a[i]; i++) {
if (!isspace((unsigned char)a[i]))
count[(unsigned char)tolower((unsigned char)a[i])]++;
}
for (int i = 0; b[i]; i++) {
if (!isspace((unsigned char)b[i]))
count[(unsigned char)tolower((unsigned char)b[i])]–;
}
for (int i = 0; i < 256; i++) {
if (count[i] != 0) {
printf(“Not Anagrams”);
return 0;
}
}
printf(“Anagrams”);
return 0;
}
20. Remove Duplicate Characters From a String
#include <stdio.h>
int main(void) {
char s[1000];
int seen[256] = {0};
int k = 0;
fgets(s, sizeof(s), stdin);
for (int i = 0; s[i]; i++) {
unsigned char c = (unsigned char)s[i];
if (!seen[c]) {
seen[c] = 1;
s[k++] = s[i];
}
}
s[k] = ‘\0’;
printf(“%s”, s);
return 0;
}
🟠 HARD
21. Second Largest Element Without Sorting
#include <stdio.h>
#include <limits.h>
int main(void) {
int n;
scanf(“%d”, &n);
int x;
int largest = INT_MIN;
int second = INT_MIN;
for (int i = 0; i < n; i++) {
scanf(“%d”, &x);
if (x > largest) {
second = largest;
largest = x;
}
else if (x > second && x != largest) {
second = x;
}
}
if (second == INT_MIN)
printf(“No distinct second largest”);
else
printf(“%d”, second);
return 0;
}
22. Find Missing Number in an Array
#include <stdio.h>
int main(void) {
int n;
scanf(“%d”, &n);
long long x = 0;
for (int i = 0; i < n; i++) {
int v;
scanf(“%d”, &v);
x ^= v;
}
for (int i = 0; i <= n; i++)
x ^= i;
printf(“%lld”, x);
return 0;
}
23. Find Duplicate Elements in an Array
#include <stdio.h>
int main(void) {
int n;
scanf(“%d”, &n);
int a[n];
for (int i = 0; i < n; i++)
scanf(“%d”, &a[i]);
int found = 0;
for (int i = 0; i < n; i++) {
int duplicate = 0;
for (int j = 0; j < i; j++) {
if (a[i] == a[j]) {
duplicate = 1;
break;
}
}
if (duplicate)
continue;
for (int j = i + 1; j < n; j++) {
if (a[i] == a[j]) {
printf(“%d “, a[i]);
found = 1;
break;
}
}
}
if (!found)
printf(“No duplicates”);
return 0;
}
24. Rotate an Array by K Positions
#include <stdio.h>
void reverse(int a[], int l, int r) {
while (l < r) {
int t = a[l];
a[l++] = a[r];
a[r–] = t;
}
}
int main(void) {
int n, k;
scanf(“%d”, &n);
int a[n];
for (int i = 0; i < n; i++)
scanf(“%d”, &a[i]);
scanf(“%d”, &k);
if (n == 0)
return 0;
k = ((k % n) + n) % n;
reverse(a, 0, n – k – 1);
reverse(a, n – k, n – 1);
reverse(a, 0, n – 1);
for (int i = 0; i < n; i++)
printf(“%d “, a[i]);
return 0;
}
25. Move All Zeros to the End
#include <stdio.h>
int main(void) {
int n, k = 0;
scanf(“%d”, &n);
int a[n];
for (int i = 0; i < n; i++)
scanf(“%d”, &a[i]);
for (int i = 0; i < n; i++) {
if (a[i] != 0)
a[k++] = a[i];
}
while (k < n)
a[k++] = 0;
for (int i = 0; i < n; i++)
printf(“%d “, a[i]);
return 0;
}
26. Maximum Subarray Sum
#include <stdio.h>
int main(void) {
int n;
scanf(“%d”, &n);
long long x, best, current;
scanf(“%lld”, &x);
best = current = x;
for (int i = 1; i < n; i++) {
scanf(“%lld”, &x);
current = current > 0 ? current + x : x;
if (current > best)
best = current;
}
printf(“%lld”, best);
return 0;
}
27. Find Majority Element
#include <stdio.h>
int main(void) {
int n;
scanf(“%d”, &n);
int a[n];
for (int i = 0; i < n; i++)
scanf(“%d”, &a[i]);
int candidate = 0;
int count = 0;
for (int i = 0; i < n; i++) {
if (count == 0) {
candidate = a[i];
count = 1;
}
else if (a[i] == candidate) {
count++;
}
else {
count–;
}
}
count = 0;
for (int i = 0; i < n; i++) {
if (a[i] == candidate)
count++;
}
if (count > n / 2)
printf(“%d”, candidate);
else
printf(“No majority element”);
return 0;
}
28. Find Pair With a Given Sum
#include <stdio.h>
int main(void) {
int n, target;
scanf(“%d %d”, &n, &target);
int a[n];
for (int i = 0; i < n; i++)
scanf(“%d”, &a[i]);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] + a[j] == target) {
printf(“%d %d”, a[i], a[j]);
return 0;
}
}
}
printf(“No pair”);
return 0;
}
29. Merge Two Sorted Arrays
#include <stdio.h>
int main(void) {
int n, m;
scanf(“%d %d”, &n, &m);
int a[n], b[m];
for (int i = 0; i < n; i++)
scanf(“%d”, &a[i]);
for (int i = 0; i < m; i++)
scanf(“%d”, &b[i]);
int i = 0, j = 0;
while (i < n && j < m)
printf(“%d “, a[i] < b[j] ? a[i++] : b[j++]);
while (i < n)
printf(“%d “, a[i++]);
while (j < m)
printf(“%d “, b[j++]);
return 0;
}
30. Sort an Array Containing Only 0, 1 and 2
#include <stdio.h>
int main(void) {
int n;
scanf(“%d”, &n);
int a[n];
for (int i = 0; i < n; i++)
scanf(“%d”, &a[i]);
int low = 0;
int mid = 0;
int high = n – 1;
while (mid <= high) {
if (a[mid] == 0) {
int t = a[low];
a[low++] = a[mid];
a[mid++] = t;
}
else if (a[mid] == 1) {
mid++;
}
else {
int t = a[mid];
a[mid] = a[high];
a[high–] = t;
}
}
for (int i = 0; i < n; i++)
printf(“%d “, a[i]);
return 0;
}
31. First Non-Repeating Character
#include <stdio.h>
int main(void) {
char s[1000];
int count[256] = {0};
fgets(s, sizeof(s), stdin);
for (int i = 0; s[i]; i++)
count[(unsigned char)s[i]]++;
for (int i = 0; s[i]; i++) {
if (s[i] != ‘\n’ &&
count[(unsigned char)s[i]] == 1) {
printf(“%c”, s[i]);
return 0;
}
}
printf(“No non-repeating character”);
return 0;
}
32. Longest Consecutive Sequence
#include <stdio.h>
int contains(int a[], int n, int x) {
for (int i = 0; i < n; i++)
if (a[i] == x)
return 1;
return 0;
}
int main(void) {
int n;
scanf(“%d”, &n);
int a[n];
for (int i = 0; i < n; i++)
scanf(“%d”, &a[i]);
int best = 0;
for (int i = 0; i < n; i++) {
if (!contains(a, n, a[i] – 1)) {
int len = 1;
while (contains(a, n, a[i] + len))
len++;
if (len > best)
best = len;
}
}
printf(“%d”, best);
return 0;
}
33. Implement strlen() Without Library Functions
#include <stdio.h>
int main(void) {
char s[1000];
fgets(s, sizeof(s), stdin);
int len = 0;
while (s[len] && s[len] != ‘\n’)
len++;
printf(“%d”, len);
return 0;
}
34. Implement strcpy() Without Library Functions
#include <stdio.h>
int main(void) {
char src[1000], dest[1000];
fgets(src, sizeof(src), stdin);
int i = 0;
while (src[i] && src[i] != ‘\n’) {
dest[i] = src[i];
i++;
}
dest[i] = ‘\0’;
printf(“%s”, dest);
return 0;
}
35. Implement strstr() Without Library Functions
#include <stdio.h>
#include <string.h>
int main(void) {
char text[1000], pat[1000];
fgets(text, sizeof(text), stdin);
fgets(pat, sizeof(pat), stdin);
int n = 0, m = 0;
while (text[n] && text[n] != ‘\n’)
n++;
while (pat[m] && pat[m] != ‘\n’)
m++;
for (int i = 0; i <= n – m; i++) {
int j = 0;
while (j < m && text[i + j] == pat[j])
j++;
if (j == m) {
printf(“Found at index %d”, i);
return 0;
}
}
printf(“Not Found”);
return 0;
}
🔴 EXTREME
36. Reverse a Linked List
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
int main(void) {
int n;
scanf(“%d”, &n);
struct Node *head = NULL;
for (int i = 0; i < n; i++) {
struct Node *p = malloc(sizeof(*p));
scanf(“%d”, &p->data);
p->next = head;
head = p;
}
struct Node *prev = NULL;
struct Node *cur = head;
while (cur) {
struct Node *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
while (prev) {
printf(“%d “, prev->data);
struct Node *t = prev;
prev = prev->next;
free(t);
}
return 0;
}
37. Detect a Loop in a Linked List
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
int main(void) {
int n;
scanf(“%d”, &n);
struct Node *head = NULL;
struct Node *tail = NULL;
struct Node *nodes[1000];
for (int i = 0; i < n; i++) {
nodes[i] = malloc(sizeof(struct Node));
scanf(“%d”, &nodes[i]->data);
nodes[i]->next = NULL;
if (!head)
head = nodes[i];
else
tail->next = nodes[i];
tail = nodes[i];
}
int pos;
scanf(“%d”, &pos);
if (pos >= 0 && pos < n)
tail->next = nodes[pos];
struct Node *slow = head;
struct Node *fast = head;
int loop = 0;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next
if (slow == fast) {
loop = 1;
break;
}
}
printf(“%s”, loop ? “Loop detected” : “No loop”);
return 0;
}
38. Find the Intersection of Two Linked Lists
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
int length(struct Node *p) {
int n = 0;
while (p) {
n++;
p = p->next;
}
return n;
}
struct Node *advance(struct Node *p, int k) {
while (k–)
p = p->next;
return p;
}
int main(void) {
int n, m;
scanf(“%d %d”, &n, &m);
struct Node *a = NULL;
struct Node *b = NULL;
struct Node *ta = NULL;
struct Node *tb = NULL;
struct Node *common = NULL;
for (int i = 0; i < n; i++) {
struct Node *p = malloc(sizeof(*p));
scanf(“%d”, &p->data);
p->next = NULL;
if (!a)
a = p;
else
ta->next = p;
ta = p;
}
for (int i = 0; i < m; i++) {
struct Node *p = malloc(sizeof(*p));
scanf(“%d”, &p->data);
p->next = NULL;
if (!b)
b = p;
else
tb->next = p;
tb = p;
}
int k;
scanf(“%d”, &k);
if (k >= 0 && k < n) {
common = advance(a, k);
tb->next = common;
}
int la = length(a);
int lb = length(b);
struct Node *pa = a;
struct Node *pb = b;
if (la > lb)
pa = advance(pa, la – lb);
else
pb = advance(pb, lb – la);
while (pa && pb && pa != pb) {
pa = pa->next;
pb = pb->next;
}
if (pa)
printf(“Intersection = %d”, pa->data);
else
printf(“No intersection”);
return 0;
}
39. Implement a Stack Using Arrays
#include <stdio.h>
#define MAX 1000
int main(void) {
int stack[MAX];
int top = -1;
int choice, x;
while (scanf(“%d”, &choice) == 1) {
if (choice == 1) {
scanf(“%d”, &x);
if (top < MAX – 1)
stack[++top] = x;
}
else if (choice == 2) {
if (top >= 0)
printf(“%d\n”, stack[top–]);
else
printf(“Underflow\n”);
}
else if (choice == 3) {
if (top >= 0)
printf(“%d\n”, stack[top]);
else
printf(“Empty\n”);
}
else if (choice == 4) {
break;
}
}
return 0;
}
40. Implement a Circular Queue
#include <stdio.h>
#define MAX 100
int main(void) {
int q[MAX];
int front = 0;
int rear = 0;
int count = 0;
int choice, x;
while (scanf(“%d”, &choice) == 1) {
if (choice == 1) {
scanf(“%d”, &x);
if (count < MAX) {
q[rear] = x;
rear = (rear + 1) % MAX;
count++;
}
else {
printf(“Overflow\n”);
}
}
else if (choice == 2) {
if (count) {
printf(“%d\n”, q[front]);
front = (front + 1) % MAX;
count–;
}
else {
printf(“Underflow\n”);
}
}
else if (choice == 3) {
if (count)
printf(“%d\n”, q[front]);
else
printf(“Empty\n”);
}
else if (choice == 4) {
break;
}
}
return 0;
}
41. Evaluate a Postfix Expression
#include <stdio.h>
#include <ctype.h>
int main(void) {
char s[1000];
int st[1000];
int top = -1;
fgets(s, sizeof(s), stdin);
for (int i = 0; s[i]; ) {
if (isspace((unsigned char)s[i])) {
i++;
continue;
}
if (isdigit((unsigned char)s[i])) {
int x = 0;
while (isdigit((unsigned char)s[i])) {
x = x * 10 + s[i] – ‘0’;
i++;
}
st[++top] = x;
}
else {
if (top < 1) {
printf(“Invalid”);
return 0;
}
int b = st[top–];
int a = st[top–];
switch (s[i]) {
case ‘+’:
st[++top] = a + b;
break;
case ‘-‘:
st[++top] = a – b;
break;
case ‘*’:
st[++top] = a * b;
break;
case ‘/’:
if (!b) {
printf(“Invalid”);
return 0;
}
st[++top] = a / b;
break;
default:
printf(“Invalid”);
return 0;
}
i++;
}
}
printf(“%d”, top == 0 ? st[top] : 0);
return 0;
}
42. Convert Infix Expression to Postfix
#include <stdio.h>
#include <ctype.h>
char st[1000];
int top = -1;
int prec(char c) {
if (c == ‘+’ || c == ‘-‘)
return 1;
if (c == ‘*’ || c == ‘/’)
return 2;
if (c == ‘^’)
return 3;
return 0;
}
int main(void) {
char s[1000];
fgets(s, sizeof(s), stdin);
for (int i = 0; s[i]; i++) {
char c = s[i];
if (isspace((unsigned char)c))
continue;
if (isalnum((unsigned char)c)) {
putchar(c);
}
else if (c == ‘(‘) {
st[++top] = c;
}
else if (c == ‘)’) {
while (top >= 0 && st[top] != ‘(‘)
putchar(st[top–]);
if (top >= 0)
top–;
}
else {
while (top >= 0 &&
st[top] != ‘(‘ &&
prec(st[top]) >= prec(c)) {
putchar(st[top–]);
}
st[++top] = c;
}
}
while (top >= 0)
putchar(st[top–]);
return 0;
}
43. Binary Tree Traversals Without Recursion
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *l;
struct Node *r;
};
struct Node *node(int x) {
struct Node *p = malloc(sizeof(*p));
p->data = x;
p->l = NULL;
p->r = NULL;
return p;
}
void inorder(struct Node *root) {
struct Node *st[1000];
int top = -1;
struct Node *cur = root;
while (cur || top >= 0) {
while (cur) {
st[++top] = cur;
cur = cur->l;
}
cur = st[top–];
printf(“%d “, cur->data);
cur = cur->r;
}
}
int main(void) {
int n;
scanf(“%d”, &n);
struct Node *a[n];
int l[n], r[n];
for (int i = 0; i < n; i++) {
int v;
scanf(“%d%d%d”, &v, &l[i], &r[i]);
a[i] = node(v);
}
for (int i = 0; i < n; i++) {
if (l[i] >= 0)
a[i]->l = a[l[i]];
if (r[i] >= 0)
a[i]->r = a[r[i]];
}
inorder(a[0]);
return 0;
}
44. Implement BFS and DFS
#include <stdio.h>
#define MAX 100
int g[MAX][MAX];
int n;
int vis[MAX];
void dfs(int u) {
vis[u] = 1;
printf(“%d “, u);
for (int v = 0; v < n; v++) {
if (g[u][v] && !vis[v])
dfs(v);
}
}
void bfs(int s) {
int q[MAX];
int f = 0;
int r = 0;
for (int i = 0; i < n; i++)
vis[i] = 0;
q[r++] = s;
vis[s] = 1;
while (f < r) {
int u = q[f++];
printf(“%d “, u);
for (int v = 0; v < n; v++) {
if (g[u][v] && !vis[v]) {
vis[v] = 1;
q[r++] = v;
}
}
}
}
int main(void) {
int start;
scanf(“%d”, &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf(“%d”, &g[i][j]);
scanf(“%d”, &start);
dfs(start);
printf(“\n”);
bfs(start);
return 0;
}
45. Implement Dijkstra’s Algorithm
#include <stdio.h>
#define MAX 100
#define INF 1000000000
int main(void) {
int n;
int g[MAX][MAX];
int src;
scanf(“%d”, &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf(“%d”, &g[i][j]);
scanf(“%d”, &src);
int d[MAX];
int used[MAX] = {0};
for (int i = 0; i < n; i++)
d[i] = INF;
d[src] = 0;
for (int k = 0; k < n; k++) {
int u = -1;
for (int i = 0; i < n; i++) {
if (!used[i] &&
(u == -1 || d[i] < d[u]))
u = i;
}
if (u == -1 || d[u] == INF)
break;
used[u] = 1;
for (int v = 0; v < n; v++) {
if (g[u][v] > 0 &&
d[u] + g[u][v] < d[v]) {
d[v] = d[u] + g[u][v];
}
}
}
for (int i = 0; i < n; i++)
printf(“%d: %d\n”, i, d[i]);
return 0;
}
46. Generate All Permutations of a String
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) {
char t = *a;
*a = *b;
*b = t;
}
void perm(char *s, int l, int r) {
if (l == r) {
printf(“%s\n”, s);
return;
}
for (int i = l; i <= r; i++) {
swap(&s[l], &s[i]);
perm(s, l + 1, r);
swap(&s[l], &s[i]);
}
}
int main(void) {
char s[100];
scanf(“%99s”, s);
perm(s, 0, (int)strlen(s) – 1);
return 0;
}
47. Solve Tower of Hanoi
#include <stdio.h>
void hanoi(int n, char from, char aux, char to) {
if (n == 0)
return;
hanoi(n – 1, from, to, aux);
printf(“Move disk %d from %c to %c\n”,
n, from, to);
hanoi(n – 1, aux, from, to);
}
int main(void) {
int n;
scanf(“%d”, &n);
hanoi(n, ‘A’, ‘B’, ‘C’);
return 0;
}
48. Solve the N-Queens Problem
#include <stdio.h>
#define MAX 20
int n;
int pos[MAX];
int usedCol[MAX];
int diag1[2 * MAX];
int diag2[2 * MAX];
int solutions = 0;
void solve(int r) {
if (r == n) {
solutions++;
for (int i = 0; i < n; i++)
printf(“%d%c”,
pos[i] + 1,
i == n – 1 ? ‘\n’ : ‘ ‘);
return;
}
for (int c = 0; c < n; c++) {
if (!usedCol[c] &&
!diag1[r – c + n] &&
!diag2[r + c])
pos[r] = c;
usedCol[c] = 1;
diag1[r – c + n] = 1;
diag2[r + c] = 1;
solve(r + 1);
usedCol[c] = 0;
diag1[r – c + n] = 0;
diag2[r + c] = 0;
}
}
}
int main(void) {
scanf(“%d”, &n);
solve(0);
printf(“Solutions = %d”, solutions);
return 0;
}
49. Build a Sudoku Solver
#include <stdio.h>
int a[9][9];
int valid(int r, int c, int x) {
for (int i = 0; i < 9; i++) {
if (a[r][i] == x ||
a[i][c] == x)
return 0;
}
int R = r / 3 * 3;
int C = c / 3 * 3;
for (int i = R; i < R + 3; i++)
for (int j = C; j < C + 3; j++)
if (a[i][j] == x)
return 0;
return 1;
}
int solve(void) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (a[r][c] == 0) {
for (int x = 1; x <= 9; x++) {
if (valid(r, c, x)) {
a[r][c] = x;
if (solve())
return 1;
a[r][c] = 0;
}
}
return 0;
}
}
}
return 1;
}
int main(void) {
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
scanf(“%d”, &a[r][c]);
if (solve()) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++)
printf(“%d “, a[r][c]);
printf(“\n”);
}
}
else {
printf(“No solution”);
}
return 0;
}
50. Implement KMP String Matching Algorithm
#include <stdio.h>
#include <string.h>
void prefix(const char *p, int m, int *lps) {
lps[0] = 0;
for (int i = 1, len = 0; i < m; ) {
if (p[i] == p[len]) {
lps[i++] = ++len;
}
else if (len) {
len = lps[len – 1];
}
else {
lps[i++] = 0;
}
}
}
int main(void) {
char text[2000];
char pat[1000];
fgets(text, sizeof(text), stdin);
fgets(pat, sizeof(pat), stdin);
int n = strlen(text);
int m = strlen(pat);
while (n && text[n – 1] == ‘\n’)
text[–n] = ‘\0’;
while (m && pat[m – 1] == ‘\n’)
pat[–m] = ‘\0’;
if (m == 0) {
printf(“Found at index 0”);
return 0;
}
int lps[m];
prefix(pat, m, lps);
for (int i = 0, j = 0; i < n; ) {
if (text[i] == pat[j]) {
i++;
j++;
if (j == m) {
printf(“Found at index %d”, i – m);
return 0;
}
}
else if (j) {
j = lps[j – 1];
}
else {
i++;
}
}
printf(“Not Found”);
return 0;
}
Free Resources