C Interview Questions with Answers

// First C Program
#include <stdio.h>

int main() {
    printf("Hello, World!\n");
    return 0;
}

// Data Types in C
#include <stdio.h>

int main() {
    int age = 25;
    float salary = 50000.50;
    double pi = 3.14159265358979;
    char grade = 'A';
    
    printf("Age: %d\n", age);
    printf("Salary: %.2f\n", salary);
    printf("Pi: %.10lf\n", pi);
    printf("Grade: %c\n", grade);
    
    return 0;
}

// Variables and Constants
#include <stdio.h>

#define PI 3.14159    // macro constant
#define MAX 100

int main() {
    int x = 10;       // variable
    const int y = 20; // constant variable
    
    printf("x = %d\n", x);
    printf("y = %d\n", y);
    printf("PI = %.5f\n", PI);
    printf("MAX = %d\n", MAX);
    
    x = 30;   // allowed
    // y = 40; // ERROR: cannot modify const
    
    return 0;
}

// Operators in C
#include <stdio.h>

int main() {
    int a = 10, b = 3;
    
    // Arithmetic
    printf("%d + %d = %d\n", a, b, a + b);
    printf("%d - %d = %d\n", a, b, a - b);
    printf("%d * %d = %d\n", a, b, a * b);
    printf("%d / %d = %d\n", a, b, a / b);
    printf("%d %% %d = %d\n", a, b, a % b);
    
    // Relational
    printf("a > b: %d\n", a > b);
    printf("a == b: %d\n", a == b);
    
    // Logical
    printf("a>5 && b<5: %d\n", a > 5 && b < 5);
    
    // Bitwise
    printf("a & b = %d\n", a & b);
    printf("a | b = %d\n", a | b);
    printf("a ^ b = %d\n", a ^ b);
    
    return 0;
}

// if-else and switch
#include <stdio.h>

int main() {
    int num = 15;
    
    // if-else
    if (num > 0) {
        printf("%d is positive\n", num);
    } else if (num < 0) {
        printf("%d is negative\n", num);
    } else {
        printf("Zero\n");
    }
    
    // switch
    int day = 3;
    switch (day) {
        case 1: printf("Monday\n"); break;
        case 2: printf("Tuesday\n"); break;
        case 3: printf("Wednesday\n"); break;
        default: printf("Other day\n");
    }
    
    return 0;
}

// Loops in C
#include <stdio.h>

int main() {
    // for loop
    printf("For loop: ");
    for (int i = 1; i <= 5; i++) {
        printf("%d ", i);
    }
    printf("\n");
    
    // while loop
    printf("While loop: ");
    int i = 1;
    while (i <= 5) {
        printf("%d ", i);
        i++;
    }
    printf("\n");
    
    // do-while loop
    printf("Do-While loop: ");
    int j = 1;
    do {
        printf("%d ", j);
        j++;
    } while (j <= 5);
    printf("\n");
    
    return 0;
}

// Functions in C
#include <stdio.h>

// Function declaration (prototype)
int add(int a, int b);
float area(float radius);
void greet(char name[]);

int main() {
    printf("Sum: %d\n", add(5, 3));
    printf("Area: %.2f\n", area(7.0));
    greet("Alice");
    return 0;
}

int add(int a, int b) {
    return a + b;
}

float area(float radius) {
    return 3.14159 * radius * radius;
}

void greet(char name[]) {
    printf("Hello, %s!\n", name);
}

// Arrays in C
#include <stdio.h>

int main() {
    // 1D Array
    int nums[5] = {10, 20, 30, 40, 50};
    
    printf("1D Array: ");
    for (int i = 0; i < 5; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");
    
    // 2D Array
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    printf("2D Array:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

// Pointers in C
#include <stdio.h>

int main() {
    int x = 42;
    int *ptr = &x;   // ptr stores address of x
    
    printf("Value of x: %d\n", x);
    printf("Address of x: %p\n", &x);
    printf("ptr holds: %p\n", ptr);
    printf("Value via ptr: %d\n", *ptr);  // dereferencing
    
    // Modify via pointer
    *ptr = 100;
    printf("x after modification: %d\n", x);
    
    // Pointer arithmetic
    int arr[] = {10, 20, 30};
    int *p = arr;
    printf("arr[0]=%d, arr[1]=%d, arr[2]=%d\n",
           *p, *(p+1), *(p+2));
    
    return 0;
}

// Strings in C
#include <stdio.h>
#include <string.h>

int main() {
    char str1[] = "Hello";
    char str2[] = "World";
    char result[50];
    
    printf("str1: %s\n", str1);
    printf("Length: %lu\n", strlen(str1));
    
    // Copy
    strcpy(result, str1);
    printf("Copied: %s\n", result);
    
    // Concatenate
    strcat(result, " ");
    strcat(result, str2);
    printf("Concatenated: %s\n", result);
    
    // Compare
    printf("strcmp: %d\n", strcmp(str1, str2));
    
    // Convert
    char numStr[] = "12345";
    int num = atoi(numStr);
    printf("atoi: %d\n", num);
    
    return 0;
}

// Structures in C
#include <stdio.h>
#include <string.h>

struct Student {
    int id;
    char name[50];
    float gpa;
};

void printStudent(struct Student s) {
    printf("ID: %d\n", s.id);
    printf("Name: %s\n", s.name);
    printf("GPA: %.2f\n", s.gpa);
}

int main() {
    struct Student s1;
    s1.id = 101;
    strcpy(s1.name, "Alice");
    s1.gpa = 3.85;
    
    printStudent(s1);
    
    // Initialize directly
    struct Student s2 = {102, "Bob", 3.70};
    printStudent(s2);
    
    return 0;
}

// Typedef and Unions
#include <stdio.h>

// typedef for struct
typedef struct {
    int x;
    int y;
} Point;

// Union - shares memory
union Data {
    int i;
    float f;
    char str[20];
};

int main() {
    Point p = {3, 4};
    printf("Point: (%d, %d)\n", p.x, p.y);
    
    union Data d;
    d.i = 10;
    printf("d.i = %d\n", d.i);
    
    d.f = 3.14;
    printf("d.f = %.2f\n", d.f);
    // Note: d.i is now garbage since union shares memory
    
    printf("Size of union: %lu\n", sizeof(d));
    
    return 0;
}

// Recursion in C
#include <stdio.h>

// Factorial
int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    return n * factorial(n - 1);
}

// Fibonacci
int fibonacci(int n) {
    if (n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Power
int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

int main() {
    printf("5! = %d\n", factorial(5));
    printf("fib(7) = %d\n", fibonacci(7));
    printf("2^10 = %d\n", power(2, 10));
    return 0;
}

// Dynamic Memory Allocation
#include <stdio.h>
#include <stdlib.h>

int main() {
    int n = 5;
    
    // malloc
    int *arr = (int*)malloc(n * sizeof(int));
    if (arr == NULL) {
        printf("Memory allocation failed\n");
        return 1;
    }
    
    for (int i = 0; i < n; i++) arr[i] = (i + 1) * 10;
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    
    // realloc - resize
    arr = (int*)realloc(arr, 8 * sizeof(int));
    for (int i = 5; i < 8; i++) arr[i] = (i + 1) * 10;
    for (int i = 0; i < 8; i++) printf("%d ", arr[i]);
    printf("\n");
    
    // calloc - zero-initialized
    int *zeros = (int*)calloc(5, sizeof(int));
    for (int i = 0; i < 5; i++) printf("%d ", zeros[i]);
    printf("\n");
    
    free(arr);
    free(zeros);
    return 0;
}

// File I/O in C
#include <stdio.h>

int main() {
    // Write to file
    FILE *fp = fopen("test.txt", "w");
    if (fp == NULL) {
        printf("Cannot open file\n");
        return 1;
    }
    fprintf(fp, "Hello, C File I/O!\n");
    fprintf(fp, "Line 2\n");
    fclose(fp);
    
    // Read from file
    fp = fopen("test.txt", "r");
    char line[100];
    while (fgets(line, sizeof(line), fp) != NULL) {
        printf("%s", line);
    }
    fclose(fp);
    
    // Append to file
    fp = fopen("test.txt", "a");
    fprintf(fp, "Appended line\n");
    fclose(fp);
    
    return 0;
}

// Pointer to Function
#include <stdio.h>

int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }
int multiply(int a, int b) { return a * b; }

// Function that takes function pointer
int operate(int a, int b, int (*op)(int, int)) {
    return op(a, b);
}

int main() {
    int (*fp)(int, int);  // function pointer declaration
    
    fp = add;
    printf("add: %d\n", fp(10, 5));
    
    fp = subtract;
    printf("subtract: %d\n", fp(10, 5));
    
    // Passing as argument
    printf("operate add: %d\n", operate(10, 5, add));
    printf("operate mul: %d\n", operate(10, 5, multiply));
    
    return 0;
}

// Pointer to Pointer
#include <stdio.h>

void changeValue(int **pp) {
    **pp = 999;
}

int main() {
    int x = 10;
    int *p = &x;
    int **pp = &p;   // pointer to pointer
    
    printf("x = %d\n", x);
    printf("*p = %d\n", *p);
    printf("**pp = %d\n", **pp);
    
    **pp = 42;
    printf("After **pp = 42, x = %d\n", x);
    
    changeValue(&p);
    printf("After changeValue, x = %d\n", x);
    
    return 0;
}

// Linked List in C
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

struct Node* createNode(int data) {
    struct Node *node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

void append(struct Node **head, int data) {
    struct Node *newNode = createNode(data);
    if (*head == NULL) { *head = newNode; return; }
    struct Node *curr = *head;
    while (curr->next) curr = curr->next;
    curr->next = newNode;
}

void display(struct Node *head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node *head = NULL;
    append(&head, 10);
    append(&head, 20);
    append(&head, 30);
    display(head);
    return 0;
}

// Stack using Array
#include <stdio.h>
#define MAX 100

struct Stack {
    int items[MAX];
    int top;
};

void init(struct Stack *s) { s->top = -1; }

int isEmpty(struct Stack *s) { return s->top == -1; }
int isFull(struct Stack *s)  { return s->top == MAX - 1; }

void push(struct Stack *s, int val) {
    if (isFull(s)) { printf("Stack Overflow\n"); return; }
    s->items[++s->top] = val;
}

int pop(struct Stack *s) {
    if (isEmpty(s)) { printf("Stack Underflow\n"); return -1; }
    return s->items[s->top--];
}

int peek(struct Stack *s) {
    if (isEmpty(s)) return -1;
    return s->items[s->top];
}

int main() {
    struct Stack s;
    init(&s);
    push(&s, 10); push(&s, 20); push(&s, 30);
    printf("Top: %d\n", peek(&s));
    printf("Pop: %d\n", pop(&s));
    printf("Pop: %d\n", pop(&s));
    return 0;
}

// Queue using Array
#include <stdio.h>
#define MAX 100

struct Queue {
    int items[MAX];
    int front, rear;
};

void init(struct Queue *q) { q->front = q->rear = -1; }

int isEmpty(struct Queue *q) { return q->front == -1; }
int isFull(struct Queue *q)  { return q->rear == MAX - 1; }

void enqueue(struct Queue *q, int val) {
    if (isFull(q)) { printf("Queue Full\n"); return; }
    if (isEmpty(q)) q->front = 0;
    q->items[++q->rear] = val;
}

int dequeue(struct Queue *q) {
    if (isEmpty(q)) { printf("Queue Empty\n"); return -1; }
    int val = q->items[q->front];
    if (q->front == q->rear) { q->front = q->rear = -1; }
    else q->front++;
    return val;
}

int main() {
    struct Queue q;
    init(&q);
    enqueue(&q, 10); enqueue(&q, 20); enqueue(&q, 30);
    printf("Dequeue: %d\n", dequeue(&q));
    printf("Dequeue: %d\n", dequeue(&q));
    return 0;
}

// Binary Search in C
#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    int idx = binarySearch(arr, n, 23);
    if (idx != -1)
        printf("Found at index: %d\n", idx);
    else
        printf("Not found\n");
    
    printf("Search 99: %d\n", binarySearch(arr, n, 99));
    return 0;
}

// Bubble Sort in C
#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break; // already sorted
    }
}

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Before: "); printArray(arr, n);
    bubbleSort(arr, n);
    printf("After:  "); printArray(arr, n);
    
    return 0;
}

// Selection Sort in C
#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        // Swap
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Before: "); printArray(arr, n);
    selectionSort(arr, n);
    printf("After:  "); printArray(arr, n);
    
    return 0;
}

// Insertion Sort in C
#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

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

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Before: "); printArray(arr, n);
    insertionSort(arr, n);
    printf("After:  "); printArray(arr, n);
    
    return 0;
}

// Merge Sort in C
#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int *L = malloc(n1 * sizeof(int));
    int *R = malloc(n2 * sizeof(int));
    
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    
    free(L); free(R);
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

// Quick Sort in C
#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a; *a = *b; *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

// Preprocessor Directives
#include <stdio.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define SQUARE(x) ((x) * (x))
#define PI 3.14159

#ifdef DEBUG
    #define LOG(msg) printf("DEBUG: %s\n", msg)
#else
    #define LOG(msg)
#endif

int main() {
    printf("MAX(5,9) = %d\n", MAX(5, 9));
    printf("MIN(5,9) = %d\n", MIN(5, 9));
    printf("SQUARE(7) = %d\n", SQUARE(7));
    printf("PI = %.5f\n", PI);
    
    LOG("This only prints in debug mode");
    
    return 0;
}

// Enumerations in C
#include <stdio.h>

typedef enum {
    MON = 1, TUE, WED, THU, FRI, SAT, SUN
} Day;

typedef enum {
    RED = 0xFF0000,
    GREEN = 0x00FF00,
    BLUE = 0x0000FF
} Color;

void printDay(Day d) {
    const char *days[] = {"", "Monday", "Tuesday",
        "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
    printf("Day: %s (%d)\n", days[d], d);
}

int main() {
    Day today = WED;
    printDay(today);
    
    Color c = RED;
    printf("RED = 0x%X\n", c);
    
    for (Day d = MON; d <= SUN; d++) {
        printDay(d);
    }
    
    return 0;
}

// Bit Fields in Structures
#include <stdio.h>

struct Permissions {
    unsigned int read    : 1;
    unsigned int write   : 1;
    unsigned int execute : 1;
    unsigned int unused  : 5;
};

struct Date {
    unsigned int day   : 5;   // 1-31
    unsigned int month : 4;   // 1-12
    unsigned int year  : 12;  // 0-4095
};

int main() {
    struct Permissions perm = {1, 1, 0};
    printf("Read: %d\n", perm.read);
    printf("Write: %d\n", perm.write);
    printf("Execute: %d\n", perm.execute);
    printf("Size: %lu bytes\n", sizeof(perm));
    
    struct Date d = {15, 8, 2024};
    printf("Date: %d/%d/%d\n", d.day, d.month, d.year);
    
    return 0;
}

// String Operations in C
#include <stdio.h>
#include <string.h>
#include <ctype.h>

// Reverse a string
void reverseStr(char str[]) {
    int n = strlen(str);
    for (int i = 0; i < n / 2; i++) {
        char temp = str[i];
        str[i] = str[n - 1 - i];
        str[n - 1 - i] = temp;
    }
}

// Check palindrome
int isPalindrome(char str[]) {
    int n = strlen(str);
    for (int i = 0; i < n / 2; i++)
        if (str[i] != str[n - 1 - i]) return 0;
    return 1;
}

int main() {
    char str[] = "Hello";
    printf("Original: %s\n", str);
    reverseStr(str);
    printf("Reversed: %s\n", str);
    
    char test[] = "racecar";
    printf("%s is%s palindrome\n", test,
           isPalindrome(test) ? "" : " not");
    
    // toupper / tolower
    char s[] = "Hello World";
    for (int i = 0; s[i]; i++) s[i] = toupper(s[i]);
    printf("Upper: %s\n", s);
    
    return 0;
}

// Two Dimensional Array Operations
#include <stdio.h>

void matrixAdd(int a[][3], int b[][3], int res[][3], int r, int c) {
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            res[i][j] = a[i][j] + b[i][j];
}

void matrixMul(int a[][3], int b[][3], int res[][3], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            res[i][j] = 0;
            for (int k = 0; k < n; k++)
                res[i][j] += a[i][k] * b[k][j];
        }
}

void printMatrix(int m[][3], int r, int c) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) printf("%4d", m[i][j]);
        printf("\n");
    }
}

int main() {
    int A[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    int B[3][3] = {{9,8,7},{6,5,4},{3,2,1}};
    int C[3][3];
    
    matrixAdd(A, B, C, 3, 3);
    printf("Sum:\n"); printMatrix(C, 3, 3);
    
    matrixMul(A, B, C, 3);
    printf("Product:\n"); printMatrix(C, 3, 3);
    return 0;
}

// Doubly Linked List
#include <stdio.h>
#include <stdlib.h>

struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
};

struct DNode* createNode(int data) {
    struct DNode *node = malloc(sizeof(struct DNode));
    node->data = data;
    node->prev = node->next = NULL;
    return node;
}

void insertFront(struct DNode **head, int data) {
    struct DNode *node = createNode(data);
    if (*head) { node->next = *head; (*head)->prev = node; }
    *head = node;
}

void display(struct DNode *head) {
    while (head) {
        printf("%d <-> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    struct DNode *head = NULL;
    insertFront(&head, 30);
    insertFront(&head, 20);
    insertFront(&head, 10);
    display(head);
    return 0;
}

// Circular Linked List
#include <stdio.h>
#include <stdlib.h>

struct CNode {
    int data;
    struct CNode *next;
};

void append(struct CNode **tail, int data) {
    struct CNode *node = malloc(sizeof(struct CNode));
    node->data = data;
    if (*tail == NULL) {
        node->next = node;
        *tail = node;
        return;
    }
    node->next = (*tail)->next;
    (*tail)->next = node;
    *tail = node;
}

void display(struct CNode *tail) {
    if (!tail) return;
    struct CNode *curr = tail->next;
    do {
        printf("%d -> ", curr->data);
        curr = curr->next;
    } while (curr != tail->next);
    printf("(back to head)\n");
}

int main() {
    struct CNode *tail = NULL;
    append(&tail, 10);
    append(&tail, 20);
    append(&tail, 30);
    display(tail);
    return 0;
}

// Binary Tree in C
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* newNode(int data) {
    struct TreeNode *node = malloc(sizeof(struct TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

void inorder(struct TreeNode *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void preorder(struct TreeNode *root) {
    if (!root) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

int main() {
    struct TreeNode *root = newNode(1);
    root->left  = newNode(2);
    root->right = newNode(3);
    root->left->left  = newNode(4);
    root->left->right = newNode(5);
    
    printf("Inorder:  "); inorder(root);  printf("\n");
    printf("Preorder: "); preorder(root); printf("\n");
    return 0;
}

// BST Insert and Search
#include <stdio.h>
#include <stdlib.h>

struct BST {
    int data;
    struct BST *left, *right;
};

struct BST* insert(struct BST *root, int data) {
    if (!root) {
        struct BST *node = malloc(sizeof(struct BST));
        node->data = data;
        node->left = node->right = NULL;
        return node;
    }
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

int search(struct BST *root, int key) {
    if (!root) return 0;
    if (root->data == key) return 1;
    if (key < root->data) return search(root->left, key);
    return search(root->right, key);
}

void inorder(struct BST *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main() {
    struct BST *root = NULL;
    int vals[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) root = insert(root, vals[i]);
    
    inorder(root); printf("\n");
    printf("Search 40: %s\n", search(root, 40) ? "Found" : "Not Found");
    printf("Search 99: %s\n", search(root, 99) ? "Found" : "Not Found");
    return 0;
}

// Graph - Adjacency Matrix
#include <stdio.h>
#define V 5

void addEdge(int graph[][V], int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;  // undirected
}

void printGraph(int graph[][V]) {
    printf("  ");
    for (int i = 0; i < V; i++) printf("%d ", i);
    printf("\n");
    for (int i = 0; i < V; i++) {
        printf("%d ", i);
        for (int j = 0; j < V; j++)
            printf("%d ", graph[i][j]);
        printf("\n");
    }
}

int main() {
    int graph[V][V] = {0};
    
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    
    printGraph(graph);
    return 0;
}

// BFS on Graph
#include <stdio.h>
#include <stdlib.h>
#define V 6

int adj[V][V];
int visited[V];
int queue[V];
int front = -1, rear = -1;

void enqueue(int v) { queue[++rear] = v; if (front == -1) front = 0; }
int  dequeue()      { return queue[front++]; }
int  isEmpty()      { return front > rear; }

void bfs(int start) {
    visited[start] = 1;
    enqueue(start);
    
    while (!isEmpty()) {
        int v = dequeue();
        printf("%d ", v);
        for (int i = 0; i < V; i++) {
            if (adj[v][i] && !visited[i]) {
                visited[i] = 1;
                enqueue(i);
            }
        }
    }
    printf("\n");
}

int main() {
    adj[0][1]=adj[1][0]=1;
    adj[0][2]=adj[2][0]=1;
    adj[1][3]=adj[3][1]=1;
    adj[2][4]=adj[4][2]=1;
    adj[3][5]=adj[5][3]=1;
    
    printf("BFS from 0: ");
    bfs(0);
    return 0;
}

// DFS on Graph
#include <stdio.h>
#define V 6

int adj[V][V];
int visited[V];

void dfs(int v) {
    visited[v] = 1;
    printf("%d ", v);
    
    for (int i = 0; i < V; i++) {
        if (adj[v][i] && !visited[i]) {
            dfs(i);
        }
    }
}

int main() {
    adj[0][1]=adj[1][0]=1;
    adj[0][2]=adj[2][0]=1;
    adj[1][3]=adj[3][1]=1;
    adj[2][4]=adj[4][2]=1;
    adj[3][5]=adj[5][3]=1;
    
    printf("DFS from 0: ");
    dfs(0);
    printf("\n");
    return 0;
}

// Heap Sort in C
#include <stdio.h>

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

// Counting Sort in C
#include <stdio.h>
#include <string.h>

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
    
    int count[max + 1];
    memset(count, 0, sizeof(count));
    
    for (int i = 0; i < n; i++) count[arr[i]]++;
    
    int idx = 0;
    for (int i = 0; i <= max; i++)
        while (count[i]-- > 0)
            arr[idx++] = i;
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1, 7, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    countingSort(arr, n);
    
    printf("Sorted: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

// Command Line Arguments
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    printf("Program: %s\n", argv[0]);
    printf("Arguments: %d\n", argc - 1);
    
    if (argc < 3) {
        printf("Usage: %s num1 num2\n", argv[0]);
        return 1;
    }
    
    int a = atoi(argv[1]);
    int b = atoi(argv[2]);
    
    printf("Sum of %d + %d = %d\n", a, b, a + b);
    printf("Product of %d * %d = %d\n", a, b, a * b);
    
    for (int i = 1; i < argc; i++) {
        printf("argv[%d] = %s\n", i, argv[i]);
    }
    
    return 0;
}

// Storage Classes in C
#include <stdio.h>

int globalVar = 100;    // global - static storage

void counter() {
    static int count = 0;   // static local - persists
    count++;
    printf("Count: %d\n", count);
}

void demonstrate() {
    auto int autoVar = 10;      // auto - stack
    register int regVar = 20;   // register - hint for CPU reg
    extern int globalVar;        // extern - reference global
    
    printf("auto: %d\n", autoVar);
    printf("register: %d\n", regVar);
    printf("extern global: %d\n", globalVar);
}

int main() {
    counter(); counter(); counter();  // Count: 1, 2, 3
    demonstrate();
    return 0;
}

// Void Pointer and Type Casting
#include <stdio.h>
#include <stdlib.h>

void printValue(void *ptr, char type) {
    switch (type) {
        case 'i': printf("int: %d\n", *(int*)ptr); break;
        case 'f': printf("float: %.2f\n", *(float*)ptr); break;
        case 'c': printf("char: %c\n", *(char*)ptr); break;
    }
}

int main() {
    int i = 42;
    float f = 3.14f;
    char c = 'Z';
    
    void *vp;
    
    vp = &i; printValue(vp, 'i');
    vp = &f; printValue(vp, 'f');
    vp = &c; printValue(vp, 'c');
    
    // Generic swap using void pointer
    int x = 10, y = 20;
    void *temp = malloc(sizeof(int));
    memcpy(temp, &x, sizeof(int));
    memcpy(&x, &y, sizeof(int));
    memcpy(&y, temp, sizeof(int));
    free(temp);
    
    printf("x=%d, y=%d\n", x, y);
    return 0;
}

// Function Pointers Array
#include <stdio.h>

int add(int a, int b)      { return a + b; }
int subtract(int a, int b) { return a - b; }
int multiply(int a, int b) { return a * b; }
int divide(int a, int b)   { return b ? a / b : 0; }

int main() {
    // Array of function pointers
    int (*ops[4])(int, int) = {add, subtract, multiply, divide};
    char *names[] = {"Add", "Subtract", "Multiply", "Divide"};
    
    int a = 20, b = 5;
    
    for (int i = 0; i < 4; i++) {
        printf("%s(%d, %d) = %d\n", names[i], a, b, ops[i](a, b));
    }
    
    // Callback pattern
    void applyOp(int x, int y, int (*op)(int, int)) {
        printf("Result: %d\n", op(x, y));
    }
    
    return 0;
}

// Variadic Functions
#include <stdio.h>
#include <stdarg.h>

int mySum(int count, ...) {
    va_list args;
    va_start(args, count);
    
    int total = 0;
    for (int i = 0; i < count; i++) {
        total += va_arg(args, int);
    }
    
    va_end(args);
    return total;
}

double myAverage(int count, ...) {
    va_list args;
    va_start(args, count);
    
    double sum = 0;
    for (int i = 0; i < count; i++) {
        sum += va_arg(args, double);
    }
    
    va_end(args);
    return sum / count;
}

int main() {
    printf("Sum(1,2,3): %d\n", mySum(3, 1, 2, 3));
    printf("Sum(1..5): %d\n", mySum(5, 1, 2, 3, 4, 5));
    printf("Avg: %.2f\n", myAverage(4, 1.0, 2.0, 3.0, 4.0));
    return 0;
}

// Scope Resolution and Nested Structs
#include <stdio.h>
#include <string.h>

struct Address {
    char street[100];
    char city[50];
    int pincode;
};

struct Employee {
    int id;
    char name[50];
    float salary;
    struct Address addr;  // nested struct
};

void printEmployee(struct Employee *e) {
    printf("ID: %d\n", e->id);
    printf("Name: %s\n", e->name);
    printf("Salary: %.2f\n", e->salary);
    printf("City: %s\n", e->addr.city);
    printf("PIN: %d\n", e->addr.pincode);
}

int main() {
    struct Employee emp;
    emp.id = 1001;
    strcpy(emp.name, "Alice");
    emp.salary = 75000.0;
    strcpy(emp.addr.street, "123 Main St");
    strcpy(emp.addr.city, "Mumbai");
    emp.addr.pincode = 400001;
    
    printEmployee(&emp);
    return 0;
}

// Linked List Reversal
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

struct Node* newNode(int data) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = data; n->next = NULL; return n;
}

struct Node* reverse(struct Node *head) {
    struct Node *prev = NULL, *curr = head, *nxt = NULL;
    while (curr) {
        nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

void display(struct Node *head) {
    while (head) { printf("%d -> ", head->data); head = head->next; }
    printf("NULL\n");
}

int main() {
    struct Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    
    printf("Original: "); display(head);
    head = reverse(head);
    printf("Reversed: "); display(head);
    return 0;
}

// Floyd's Cycle Detection
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

struct Node* newNode(int data) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = data; n->next = NULL; return n;
}

int detectCycle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;  // cycle detected
    }
    return 0;
}

int main() {
    struct Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    
    // Create cycle: 4 -> 2
    head->next->next->next->next = head->next;
    
    if (detectCycle(head))
        printf("Cycle detected!\n");
    else
        printf("No cycle\n");
    
    return 0;
}

// Tower of Hanoi
#include <stdio.h>

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);
}

int main() {
    int n = 3;
    printf("Tower of Hanoi with %d disks:\n", n);
    hanoi(n, 'A', 'C', 'B');
    
    // Number of moves = 2^n - 1
    int moves = 1;
    for (int i = 0; i < n; i++) moves *= 2;
    printf("Total moves: %d\n", moves - 1);
    
    return 0;
}

// GCD and LCM
#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

// Recursive GCD
int gcdRecursive(int a, int b) {
    if (b == 0) return a;
    return gcdRecursive(b, a % b);
}

int main() {
    int a = 48, b = 18;
    printf("GCD(%d,%d) = %d\n", a, b, gcd(a, b));
    printf("LCM(%d,%d) = %d\n", a, b, lcm(a, b));
    printf("GCD recursive: %d\n", gcdRecursive(a, b));
    
    // Extended Euclidean for multiple numbers
    int nums[] = {12, 24, 36, 48};
    int result = nums[0];
    for (int i = 1; i < 4; i++) result = gcd(result, nums[i]);
    printf("GCD of [12,24,36,48] = %d\n", result);
    
    return 0;
}

// Prime Number Sieve of Eratosthenes
#include <stdio.h>
#include <string.h>
#define LIMIT 100

int isPrime(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0) return 0;
    return 1;
}

void sieve(int limit) {
    int notPrime[limit + 1];
    memset(notPrime, 0, sizeof(notPrime));
    
    notPrime[0] = notPrime[1] = 1;
    
    for (int i = 2; i * i <= limit; i++) {
        if (!notPrime[i]) {
            for (int j = i * i; j <= limit; j += i)
                notPrime[j] = 1;
        }
    }
    
    printf("Primes up to %d: ", limit);
    for (int i = 2; i <= limit; i++)
        if (!notPrime[i]) printf("%d ", i);
    printf("\n");
}

int main() {
    printf("isPrime(17): %s\n", isPrime(17) ? "Yes" : "No");
    printf("isPrime(20): %s\n", isPrime(20) ? "Yes" : "No");
    sieve(50);
    return 0;
}

// Number Conversion
#include <stdio.h>

void decToBin(int n) {
    if (n == 0) { printf("0"); return; }
    int bin[32]; int idx = 0;
    while (n > 0) { bin[idx++] = n % 2; n /= 2; }
    for (int i = idx - 1; i >= 0; i--) printf("%d", bin[i]);
}

void decToOct(int n) { printf("%o", n); }
void decToHex(int n) { printf("%X", n); }

int binToDec(char bin[]) {
    int dec = 0, base = 1, len = 0;
    while (bin[len]) len++;
    for (int i = len - 1; i >= 0; i--) {
        if (bin[i] == '1') dec += base;
        base *= 2;
    }
    return dec;
}

int main() {
    int n = 255;
    printf("Decimal: %d\n", n);
    printf("Binary: "); decToBin(n); printf("\n");
    printf("Octal: "); decToOct(n); printf("\n");
    printf("Hex: "); decToHex(n); printf("\n");
    printf("Binary 11111111 to Decimal: %d\n", binToDec("11111111"));
    return 0;
}

// Pattern Printing
#include <stdio.h>

void rightTriangle(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) printf("* ");
        printf("\n");
    }
}

void pyramid(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = i; j < n; j++) printf("  ");
        for (int j = 1; j <= 2 * i - 1; j++) printf("* ");
        printf("\n");
    }
}

void diamondPattern(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = i; j < n; j++) printf(" ");
        for (int j = 1; j <= 2*i-1; j++) printf("*");
        printf("\n");
    }
    for (int i = n-1; i >= 1; i--) {
        for (int j = n; j > i; j--) printf(" ");
        for (int j = 1; j <= 2*i-1; j++) printf("*");
        printf("\n");
    }
}

int main() {
    printf("Right Triangle (n=4):\n"); rightTriangle(4);
    printf("Pyramid (n=4):\n"); pyramid(4);
    printf("Diamond (n=4):\n"); diamondPattern(4);
    return 0;
}

// Kadane's Algorithm in C
#include <stdio.h>

int maxSubarraySum(int arr[], int n) {
    int maxSum = arr[0];
    int currentSum = arr[0];
    int start = 0, end = 0, tempStart = 0;
    
    for (int i = 1; i < n; i++) {
        if (arr[i] > currentSum + arr[i]) {
            currentSum = arr[i];
            tempStart = i;
        } else {
            currentSum += arr[i];
        }
        
        if (currentSum > maxSum) {
            maxSum = currentSum;
            start = tempStart;
            end = i;
        }
    }
    
    printf("Subarray: ");
    for (int i = start; i <= end; i++) printf("%d ", arr[i]);
    printf("\n");
    
    return maxSum;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Max Sum: %d\n", maxSubarraySum(arr, n));
    return 0;
}

// Two Sum Problem in C
#include <stdio.h>
#include <stdlib.h>

// Brute Force O(n^2)
void twoSumBrute(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) {
                printf("Indices: [%d, %d] -> [%d, %d]\n",
                       i, j, arr[i], arr[j]);
            }
        }
    }
}

// Two Pointer O(n log n) - requires sorted array
void twoSumPointer(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            printf("Pair: [%d, %d]\n", arr[left], arr[right]);
            left++; right--;
        } else if (sum < target) left++;
        else right--;
    }
}

int main() {
    int arr[] = {2, 7, 11, 15};
    twoSumBrute(arr, 4, 9);
    
    int sorted[] = {1, 2, 3, 4, 6};
    twoSumPointer(sorted, 5, 6);
    return 0;
}

// Trapping Rain Water in C
#include <stdio.h>

int trap(int height[], int n) {
    int left = 0, right = n - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax)
                leftMax = height[left];
            else
                water += leftMax - height[left];
            left++;
        } else {
            if (height[right] >= rightMax)
                rightMax = height[right];
            else
                water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

int main() {
    int h[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int n = sizeof(h) / sizeof(h[0]);
    printf("Water trapped: %d\n", trap(h, n));  // 6
    
    int h2[] = {4, 2, 0, 3, 2, 5};
    printf("Water trapped: %d\n", trap(h2, 6));  // 9
    return 0;
}

// Palindrome Check (Number & String)
#include <stdio.h>
#include <string.h>

int isNumPalindrome(int n) {
    if (n < 0) return 0;
    int original = n, reversed = 0;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return original == reversed;
}

int isStrPalindrome(char str[]) {
    int l = 0, r = strlen(str) - 1;
    while (l < r) {
        if (str[l] != str[r]) return 0;
        l++; r--;
    }
    return 1;
}

int main() {
    printf("121 palindrome: %s\n", isNumPalindrome(121) ? "Yes" : "No");
    printf("123 palindrome: %s\n", isNumPalindrome(123) ? "Yes" : "No");
    printf("racecar palindrome: %s\n", isStrPalindrome("racecar") ? "Yes" : "No");
    printf("hello palindrome: %s\n",   isStrPalindrome("hello") ? "Yes" : "No");
    return 0;
}

// Fibonacci Variants
#include <stdio.h>

// Iterative O(n) time O(1) space
long long fibIterative(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b; a = b; b = c;
    }
    return b;
}

// Matrix Exponentiation O(log n)
void matMul(long long m[2][2], long long r[2][2]) {
    long long a = m[0][0]*r[0][0] + m[0][1]*r[1][0];
    long long b = m[0][0]*r[0][1] + m[0][1]*r[1][1];
    long long c = m[1][0]*r[0][0] + m[1][1]*r[1][0];
    long long d = m[1][0]*r[0][1] + m[1][1]*r[1][1];
    m[0][0]=a; m[0][1]=b; m[1][0]=c; m[1][1]=d;
}

int main() {
    printf("Fibonacci sequence:\n");
    for (int i = 0; i <= 10; i++)
        printf("fib(%d) = %lld\n", i, fibIterative(i));
    return 0;
}

// Array Rotation
#include <stdio.h>

void reverseArr(int arr[], int l, int r) {
    while (l < r) {
        int temp = arr[l]; arr[l] = arr[r]; arr[r] = temp;
        l++; r--;
    }
}

// Left rotate by d using reversal algorithm O(n) O(1)
void leftRotate(int arr[], int n, int d) {
    d = d % n;
    reverseArr(arr, 0, d - 1);
    reverseArr(arr, d, n - 1);
    reverseArr(arr, 0, n - 1);
}

// Right rotate
void rightRotate(int arr[], int n, int d) {
    leftRotate(arr, n, n - d);
}

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

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = 7;
    
    printf("Original: "); print(arr, n);
    leftRotate(arr, n, 3);
    printf("Left Rotate by 3: "); print(arr, n);
    rightRotate(arr, n, 3);
    printf("Right Rotate by 3: "); print(arr, n);
    return 0;
}

// Anagram Check in C
#include <stdio.h>
#include <string.h>

int isAnagram(char s1[], char s2[]) {
    if (strlen(s1) != strlen(s2)) return 0;
    
    int count[256] = {0};
    
    for (int i = 0; s1[i]; i++) count[(int)s1[i]]++;
    for (int i = 0; s2[i]; i++) count[(int)s2[i]]--;
    
    for (int i = 0; i < 256; i++)
        if (count[i] != 0) return 0;
    
    return 1;
}

int main() {
    char s1[] = "listen";
    char s2[] = "silent";
    printf("'%s' and '%s' are%s anagrams\n",
           s1, s2, isAnagram(s1, s2) ? "" : " not");
    
    char s3[] = "hello";
    char s4[] = "world";
    printf("'%s' and '%s' are%s anagrams\n",
           s3, s4, isAnagram(s3, s4) ? "" : " not");
    return 0;
}

// Missing Number in Array
#include <stdio.h>

// Using sum formula
int missingNumber(int arr[], int n) {
    long long expected = (long long)n * (n + 1) / 2;
    long long actual = 0;
    for (int i = 0; i < n - 1; i++) actual += arr[i];
    return (int)(expected - actual);
}

// Using XOR - no overflow
int missingXOR(int arr[], int n) {
    int xor1 = 0, xor2 = 0;
    for (int i = 1; i <= n; i++) xor1 ^= i;
    for (int i = 0; i < n - 1; i++) xor2 ^= arr[i];
    return xor1 ^ xor2;
}

int main() {
    int arr[] = {1, 2, 4, 5, 6};  // missing 3
    int n = 6;
    printf("Missing (sum): %d\n", missingNumber(arr, n));
    printf("Missing (XOR): %d\n", missingXOR(arr, n));
    
    int arr2[] = {3, 0, 1};  // missing 2
    printf("Missing: %d\n", missingXOR(arr2, 3));
    return 0;
}

// Find Duplicates in Array
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Using auxiliary array O(n) time O(n) space
void findDuplicates(int arr[], int n) {
    int *seen = calloc(n + 1, sizeof(int));
    printf("Duplicates: ");
    for (int i = 0; i < n; i++) {
        if (seen[arr[i]]) printf("%d ", arr[i]);
        else seen[arr[i]] = 1;
    }
    printf("\n");
    free(seen);
}

// Floyd's cycle for find duplicate in [1,n] array
int findOneDuplicate(int arr[], int n) {
    int slow = arr[0], fast = arr[0];
    do {
        slow = arr[slow];
        fast = arr[arr[fast]];
    } while (slow != fast);
    
    slow = arr[0];
    while (slow != fast) {
        slow = arr[slow];
        fast = arr[fast];
    }
    return slow;
}

int main() {
    int arr[] = {3, 1, 3, 4, 2};
    findDuplicates(arr, 5);
    printf("Duplicate: %d\n", findOneDuplicate(arr, 5));
    return 0;
}

// N-th Fibonacci using Dynamic Programming
#include <stdio.h>
#include <string.h>
#define MAXN 100

long long dp[MAXN];
int solved[MAXN];

long long fib(int n) {
    if (n <= 1) return n;
    if (solved[n]) return dp[n];
    solved[n] = 1;
    return dp[n] = fib(n-1) + fib(n-2);
}

// Tabulation approach
void fibTable(int n) {
    long long table[n + 1];
    table[0] = 0; table[1] = 1;
    for (int i = 2; i <= n; i++)
        table[i] = table[i-1] + table[i-2];
    
    printf("Fibonacci series up to %d:\n", n);
    for (int i = 0; i <= n; i++)
        printf("fib[%d] = %lld\n", i, table[i]);
}

int main() {
    memset(solved, 0, sizeof(solved));
    printf("fib(10) = %lld\n", fib(10));
    printf("fib(20) = %lld\n", fib(20));
    fibTable(10);
    return 0;
}

// Subset Sum Problem
#include <stdio.h>

int subsetSum(int arr[], int n, int target) {
    int dp[n + 1][target + 1];
    
    for (int i = 0; i <= n; i++) dp[i][0] = 1;
    for (int j = 1; j <= target; j++) dp[0][j] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= target; j++) {
            dp[i][j] = dp[i-1][j];
            if (arr[i-1] <= j)
                dp[i][j] = dp[i][j] || dp[i-1][j - arr[i-1]];
        }
    }
    return dp[n][target];
}

int main() {
    int arr[] = {3, 34, 4, 12, 5, 2};
    int n = 6;
    
    printf("Subset sum 9: %s\n",
           subsetSum(arr, n, 9) ? "Yes" : "No");
    printf("Subset sum 30: %s\n",
           subsetSum(arr, n, 30) ? "Yes" : "No");
    printf("Subset sum 100: %s\n",
           subsetSum(arr, n, 100) ? "Yes" : "No");
    return 0;
}

// Longest Common Subsequence in C
#include <stdio.h>
#include <string.h>

int lcs(char s1[], char s2[]) {
    int m = strlen(s1), n = strlen(s2);
    int dp[m + 1][n + 1];
    
    for (int i = 0; i <= m; i++) dp[i][0] = 0;
    for (int j = 0; j <= n; j++) dp[0][j] = 0;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = dp[i-1][j] > dp[i][j-1] ?
                            dp[i-1][j] : dp[i][j-1];
        }
    }
    return dp[m][n];
}

int main() {
    char s1[] = "ABCBDAB";
    char s2[] = "BDCAB";
    printf("LCS of '%s' and '%s' = %d\n", s1, s2, lcs(s1, s2));
    
    char s3[] = "AGGTAB";
    char s4[] = "GXTXAYB";
    printf("LCS of '%s' and '%s' = %d\n", s3, s4, lcs(s3, s4));
    return 0;
}

// Edit Distance in C
#include <stdio.h>
#include <string.h>

int min3(int a, int b, int c) {
    return a < b ? (a < c ? a : c) : (b < c ? b : c);
}

int editDistance(char s1[], char s2[]) {
    int m = strlen(s1), n = strlen(s2);
    int dp[m + 1][n + 1];
    
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + min3(dp[i-1][j],
                                     dp[i][j-1],
                                     dp[i-1][j-1]);
        }
    }
    return dp[m][n];
}

int main() {
    printf("Edit distance 'sunday' -> 'saturday': %d\n",
           editDistance("sunday", "saturday"));
    printf("Edit distance 'cat' -> 'cut': %d\n",
           editDistance("cat", "cut"));
    return 0;
}

// Coin Change Problem
#include <stdio.h>
#include <limits.h>

int coinChange(int coins[], int numCoins, int amount) {
    int dp[amount + 1];
    for (int i = 1; i <= amount; i++) dp[i] = INT_MAX;
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < numCoins; j++) {
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                int val = dp[i - coins[j]] + 1;
                if (val < dp[i]) dp[i] = val;
            }
        }
    }
    
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int coins1[] = {1, 5, 6, 9};
    printf("Min coins for 11: %d\n",
           coinChange(coins1, 4, 11));   // 2
    
    int coins2[] = {1, 2, 5};
    printf("Min coins for 11: %d\n",
           coinChange(coins2, 3, 11));   // 3
    return 0;
}

// Spiral Matrix Traversal
#include <stdio.h>

void spiralPrint(int mat[][4], int rows, int cols) {
    int top = 0, bottom = rows - 1;
    int left = 0, right = cols - 1;
    
    while (top <= bottom && left <= right) {
        for (int i = left; i <= right; i++)
            printf("%d ", mat[top][i]);
        top++;
        
        for (int i = top; i <= bottom; i++)
            printf("%d ", mat[i][right]);
        right--;
        
        if (top <= bottom) {
            for (int i = right; i >= left; i--)
                printf("%d ", mat[bottom][i]);
            bottom--;
        }
        
        if (left <= right) {
            for (int i = bottom; i >= top; i--)
                printf("%d ", mat[i][left]);
            left++;
        }
    }
    printf("\n");
}

int main() {
    int mat[4][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9,10,11,12},
        {13,14,15,16}
    };
    printf("Spiral: ");
    spiralPrint(mat, 4, 4);
    return 0;
}

// Rotate Matrix 90 Degrees
#include <stdio.h>
#define N 3

void transpose(int mat[][N]) {
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++) {
            int temp = mat[i][j];
            mat[i][j] = mat[j][i];
            mat[j][i] = temp;
        }
}

void reverseRows(int mat[][N]) {
    for (int i = 0; i < N; i++) {
        int left = 0, right = N - 1;
        while (left < right) {
            int temp = mat[i][left];
            mat[i][left] = mat[i][right];
            mat[i][right] = temp;
            left++; right--;
        }
    }
}

void printMatrix(int mat[][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) printf("%3d", mat[i][j]);
        printf("\n");
    }
}

int main() {
    int mat[N][N] = {{1,2,3},{4,5,6},{7,8,9}};
    printf("Original:\n"); printMatrix(mat);
    transpose(mat);
    reverseRows(mat);
    printf("Rotated 90 CW:\n"); printMatrix(mat);
    return 0;
}

// Valid Parentheses using Stack
#include <stdio.h>
#include <string.h>

int isValid(char str[]) {
    int n = strlen(str);
    char stack[n + 1];
    int top = -1;
    
    for (int i = 0; str[i]; i++) {
        char c = str[i];
        if (c == '(' || c == '{' || c == '[') {
            stack[++top] = c;
        } else {
            if (top == -1) return 0;
            char t = stack[top--];
            if (c == ')' && t != '(') return 0;
            if (c == '}' && t != '{') return 0;
            if (c == ']' && t != '[') return 0;
        }
    }
    return top == -1;
}

int main() {
    char tests[][20] = {"()[]{}", "([)]", "{[]}", "((("};
    for (int i = 0; i < 4; i++) {
        printf("'%s': %s\n", tests[i],
               isValid(tests[i]) ? "Valid" : "Invalid");
    }
    return 0;
}

// Power Function Fast Exponentiation
#include <stdio.h>

long long power(long long base, long long exp) {
    if (exp == 0) return 1;
    if (exp % 2 == 0) {
        long long half = power(base, exp / 2);
        return half * half;
    }
    return base * power(base, exp - 1);
}

// Modular Exponentiation
long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) result = result * base % mod;
        exp /= 2;
        base = base * base % mod;
    }
    return result;
}

int main() {
    printf("2^10 = %lld\n", power(2, 10));     // 1024
    printf("3^5 = %lld\n", power(3, 5));        // 243
    printf("2^10 mod 1000 = %lld\n",
           modPow(2, 10, 1000));                  // 24
    return 0;
}

// Number of Islands (Flood Fill)
#include <stdio.h>
#define R 5
#define C 5

void dfs(int grid[][C], int r, int c) {
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] == 0)
        return;
    grid[r][c] = 0;  // mark visited
    dfs(grid, r+1, c); dfs(grid, r-1, c);
    dfs(grid, r, c+1); dfs(grid, r, c-1);
}

int numIslands(int grid[][C]) {
    int count = 0;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == 1) {
                count++;
                dfs(grid, r, c);
            }
    return count;
}

int main() {
    int grid[R][C] = {
        {1,1,0,0,0},
        {1,1,0,0,0},
        {0,0,1,0,0},
        {0,0,0,1,1},
        {0,0,0,1,1}
    };
    printf("Number of islands: %d\n", numIslands(grid));  // 3
    return 0;
}

// Longest Increasing Subsequence
#include <stdio.h>

int lis(int arr[], int n) {
    int dp[n];
    for (int i = 0; i < n; i++) dp[i] = 1;
    
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[j] < arr[i] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;
    
    int max = dp[0];
    for (int i = 1; i < n; i++)
        if (dp[i] > max) max = dp[i];
    
    return max;
}

// Binary search approach O(n log n)
int lisBS(int arr[], int n) {
    int tails[n], len = 0;
    
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] < arr[i]) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = arr[i];
        if (lo == len) len++;
    }
    return len;
}

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = 8;
    printf("LIS (DP): %d\n", lis(arr, n));   // 4
    printf("LIS (BS): %d\n", lisBS(arr, n)); // 4
    return 0;
}

// Generic Swap and Sort with Void Pointers
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(void *a, void *b, size_t size) {
    char temp[size];
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
}

int cmpInt(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int cmpFloat(const void *a, const void *b) {
    float diff = *(float*)a - *(float*)b;
    return (diff > 0) - (diff < 0);
}

int cmpStr(const void *a, const void *b) {
    return strcmp(*(char**)a, *(char**)b);
}

int main() {
    int ints[] = {5, 3, 8, 1, 9, 2};
    qsort(ints, 6, sizeof(int), cmpInt);
    for (int i = 0; i < 6; i++) printf("%d ", ints[i]);
    printf("\n");
    
    char *strs[] = {"banana", "apple", "cherry", "date"};
    qsort(strs, 4, sizeof(char*), cmpStr);
    for (int i = 0; i < 4; i++) printf("%s ", strs[i]);
    printf("\n");
    return 0;
}

// Memory Pool Allocator
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define POOL_SIZE 1024

typedef struct {
    char buffer[POOL_SIZE];
    size_t offset;
} MemPool;

void pool_init(MemPool *pool) { pool->offset = 0; }

void* pool_alloc(MemPool *pool, size_t size) {
    if (pool->offset + size > POOL_SIZE) return NULL;
    void *ptr = pool->buffer + pool->offset;
    pool->offset += size;
    return ptr;
}

void pool_reset(MemPool *pool) { pool->offset = 0; }

int main() {
    MemPool pool;
    pool_init(&pool);
    
    int *a = pool_alloc(&pool, sizeof(int));
    int *b = pool_alloc(&pool, sizeof(int));
    *a = 42; *b = 100;
    
    printf("a = %d, b = %d\n", *a, *b);
    printf("Pool used: %zu bytes\n", pool.offset);
    
    pool_reset(&pool);
    printf("Pool reset. Offset: %zu\n", pool.offset);
    
    return 0;
}

// Trie Data Structure in C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHA 26

struct TrieNode {
    struct TrieNode *children[ALPHA];
    int isEnd;
};

struct TrieNode* newTrieNode() {
    struct TrieNode *node = calloc(1, sizeof(struct TrieNode));
    node->isEnd = 0;
    return node;
}

void insert(struct TrieNode *root, char *word) {
    struct TrieNode *curr = root;
    for (int i = 0; word[i]; i++) {
        int idx = word[i] - 'a';
        if (!curr->children[idx])
            curr->children[idx] = newTrieNode();
        curr = curr->children[idx];
    }
    curr->isEnd = 1;
}

int search(struct TrieNode *root, char *word) {
    struct TrieNode *curr = root;
    for (int i = 0; word[i]; i++) {
        int idx = word[i] - 'a';
        if (!curr->children[idx]) return 0;
        curr = curr->children[idx];
    }
    return curr->isEnd;
}

int main() {
    struct TrieNode *root = newTrieNode();
    insert(root, "hello");
    insert(root, "world");
    insert(root, "help");
    
    printf("Search 'hello': %s\n", search(root, "hello") ? "Found" : "Not Found");
    printf("Search 'hell': %s\n",  search(root, "hell")  ? "Found" : "Not Found");
    printf("Search 'world': %s\n", search(root, "world") ? "Found" : "Not Found");
    return 0;
}

// Min Stack
#include <stdio.h>
#include <limits.h>
#define MAX 100

struct MinStack {
    int stack[MAX];
    int minStack[MAX];
    int top;
};

void init(struct MinStack *ms) { ms->top = -1; }

void push(struct MinStack *ms, int val) {
    ms->stack[++ms->top] = val;
    if (ms->top == 0)
        ms->minStack[ms->top] = val;
    else {
        int prevMin = ms->minStack[ms->top - 1];
        ms->minStack[ms->top] = val < prevMin ? val : prevMin;
    }
}

int pop(struct MinStack *ms) {
    if (ms->top < 0) return INT_MIN;
    return ms->stack[ms->top--];
}

int getMin(struct MinStack *ms) {
    if (ms->top < 0) return INT_MIN;
    return ms->minStack[ms->top];
}

int main() {
    struct MinStack ms;
    init(&ms);
    push(&ms, -2); push(&ms, 0); push(&ms, -3);
    printf("Min: %d\n", getMin(&ms));  // -3
    pop(&ms);
    printf("Top: %d\n", ms.stack[ms.top]); // 0
    printf("Min: %d\n", getMin(&ms));  // -2
    return 0;
}

// Graph Topological Sort (Kahn's Algorithm)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define V 6

int adj[V][V];
int inDegree[V];

void topoSort() {
    int queue[V], front = 0, rear = -1;
    
    for (int i = 0; i < V; i++)
        if (inDegree[i] == 0)
            queue[++rear] = i;
    
    printf("Topological Order: ");
    while (front <= rear) {
        int v = queue[front++];
        printf("%d ", v);
        for (int i = 0; i < V; i++) {
            if (adj[v][i]) {
                inDegree[i]--;
                if (inDegree[i] == 0)
                    queue[++rear] = i;
            }
        }
    }
    printf("\n");
}

int main() {
    memset(adj, 0, sizeof(adj));
    memset(inDegree, 0, sizeof(inDegree));
    
    int edges[][2] = {{5,2},{5,0},{4,0},{4,1},{2,3},{3,1}};
    for (int i = 0; i < 6; i++) {
        int u = edges[i][0], v = edges[i][1];
        adj[u][v] = 1;
        inDegree[v]++;
    }
    
    topoSort();
    return 0;
}

// String Compression (Run-Length Encoding)
#include <stdio.h>
#include <string.h>

void compress(char input[], char output[]) {
    int n = strlen(input);
    int j = 0;
    
    for (int i = 0; i < n; ) {
        char ch = input[i];
        int count = 0;
        while (i < n && input[i] == ch) { i++; count++; }
        output[j++] = ch;
        if (count > 1) {
            int digits = 0;
            char buf[10];
            sprintf(buf, "%d", count);
            int len = strlen(buf);
            for (int k = 0; k < len; k++) output[j++] = buf[k];
        }
    }
    output[j] = '\0';
}

void decompress(char input[], char output[]) {
    int j = 0;
    for (int i = 0; input[i]; i++) {
        if (input[i] >= 'a' && input[i] <= 'z') {
            char ch = input[i++];
            int count = 0;
            while (input[i] >= '0' && input[i] <= '9')
                count = count * 10 + (input[i++] - '0');
            if (count == 0) count = 1;
            for (int k = 0; k < count; k++) output[j++] = ch;
            i--;
        }
    }
    output[j] = '\0';
}

int main() {
    char input[] = "aabbbcccc";
    char compressed[50], decompressed[50];
    compress(input, compressed);
    printf("Compressed: %s\n", compressed);
    decompress(compressed, decompressed);
    printf("Decompressed: %s\n", decompressed);
    return 0;
}

// Priority Queue (Min-Heap)
#include <stdio.h>
#define MAX 100

struct PriorityQueue {
    int heap[MAX];
    int size;
};

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void push(struct PriorityQueue *pq, int val) {
    pq->heap[pq->size] = val;
    int i = pq->size++;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (pq->heap[parent] > pq->heap[i]) {
            swap(&pq->heap[parent], &pq->heap[i]);
            i = parent;
        } else break;
    }
}

int pop(struct PriorityQueue *pq) {
    int min = pq->heap[0];
    pq->heap[0] = pq->heap[--pq->size];
    int i = 0;
    while (1) {
        int l = 2*i+1, r = 2*i+2, smallest = i;
        if (l < pq->size && pq->heap[l] < pq->heap[smallest]) smallest = l;
        if (r < pq->size && pq->heap[r] < pq->heap[smallest]) smallest = r;
        if (smallest == i) break;
        swap(&pq->heap[i], &pq->heap[smallest]);
        i = smallest;
    }
    return min;
}

int main() {
    struct PriorityQueue pq = {.size = 0};
    push(&pq, 5); push(&pq, 1); push(&pq, 9); push(&pq, 3);
    printf("%d\n", pop(&pq));  // 1
    printf("%d\n", pop(&pq));  // 3
    printf("%d\n", pop(&pq));  // 5
    return 0;
}

// Hash Table with Chaining
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10

struct Node {
    char key[50];
    int value;
    struct Node *next;
};

struct Node *table[SIZE];

int hash(char *key) {
    int sum = 0;
    for (int i = 0; key[i]; i++) sum += key[i];
    return sum % SIZE;
}

void insert(char *key, int val) {
    int idx = hash(key);
    struct Node *node = malloc(sizeof(struct Node));
    strcpy(node->key, key);
    node->value = val;
    node->next = table[idx];
    table[idx] = node;
}

int get(char *key) {
    int idx = hash(key);
    struct Node *curr = table[idx];
    while (curr) {
        if (strcmp(curr->key, key) == 0) return curr->value;
        curr = curr->next;
    }
    return -1;
}

int main() {
    memset(table, 0, sizeof(table));
    insert("name", 1); insert("age", 25); insert("score", 99);
    printf("name: %d\n",  get("name"));
    printf("age: %d\n",   get("age"));
    printf("score: %d\n", get("score"));
    printf("xyz: %d\n",   get("xyz"));   // -1
    return 0;
}

// Union-Find Disjoint Set
#include <stdio.h>
#define N 10

int parent[N], rankArr[N];

void init() {
    for (int i = 0; i < N; i++) { parent[i] = i; rankArr[i] = 0; }
}

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // path compression
    return parent[x];
}

void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    if (rankArr[px] < rankArr[py]) parent[px] = py;
    else if (rankArr[px] > rankArr[py]) parent[py] = px;
    else { parent[py] = px; rankArr[px]++; }
}

int connected(int x, int y) { return find(x) == find(y); }

int main() {
    init();
    unite(0, 1); unite(1, 2); unite(3, 4);
    
    printf("0-2 connected: %s\n", connected(0, 2) ? "Yes" : "No");
    printf("0-3 connected: %s\n", connected(0, 3) ? "Yes" : "No");
    printf("3-4 connected: %s\n", connected(3, 4) ? "Yes" : "No");
    
    unite(2, 3);
    printf("After unite(2,3), 0-4: %s\n", connected(0, 4) ? "Yes" : "No");
    return 0;
}

// Segment Tree
#include <stdio.h>
#define MAXN 100

int tree[4 * MAXN];

void build(int arr[], int node, int start, int end) {
    if (start == end) { tree[node] = arr[start]; return; }
    int mid = (start + end) / 2;
    build(arr, 2*node, start, mid);
    build(arr, 2*node+1, mid+1, end);
    tree[node] = tree[2*node] + tree[2*node+1];
}

void update(int node, int start, int end, int idx, int val) {
    if (start == end) { tree[node] = val; return; }
    int mid = (start + end) / 2;
    if (idx <= mid) update(2*node, start, mid, idx, val);
    else update(2*node+1, mid+1, end, idx, val);
    tree[node] = tree[2*node] + tree[2*node+1];
}

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return query(2*node, start, mid, l, r) +
           query(2*node+1, mid+1, end, l, r);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = 6;
    build(arr, 1, 0, n-1);
    printf("Sum [1,3]: %d\n", query(1, 0, n-1, 1, 3));  // 15
    update(1, 0, n-1, 1, 10);
    printf("Sum [1,3] after update: %d\n", query(1, 0, n-1, 1, 3));  // 22
    return 0;
}

// Dijkstra's Shortest Path
#include <stdio.h>
#include <limits.h>
#define V 5

int minDist(int dist[], int visited[]) {
    int min = INT_MAX, minIdx = -1;
    for (int v = 0; v < V; v++)
        if (!visited[v] && dist[v] <= min) {
            min = dist[v]; minIdx = v;
        }
    return minIdx;
}

void dijkstra(int graph[][V], int src) {
    int dist[V], visited[V];
    for (int i = 0; i < V; i++) { dist[i] = INT_MAX; visited[i] = 0; }
    dist[src] = 0;
    
    for (int count = 0; count < V - 1; count++) {
        int u = minDist(dist, visited);
        visited[u] = 1;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] &&
                dist[u] != INT_MAX &&
                dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
        }
    }
    
    printf("Vertex\tDistance from src %d\n", src);
    for (int i = 0; i < V; i++)
        printf("%d\t%d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = {
        {0,10,0,0,5}, {0,0,1,0,2}, {0,0,0,4,0},
        {7,0,6,0,0},  {0,3,9,2,0}
    };
    dijkstra(graph, 0);
    return 0;
}

// Kruskal's Minimum Spanning Tree
#include <stdio.h>
#include <stdlib.h>
#define V 4
#define E 5

struct Edge { int src, dest, weight; };

int parent[V], rnk[V];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (rnk[px] < rnk[py]) parent[px] = py;
    else if (rnk[px] > rnk[py]) parent[py] = px;
    else { parent[py] = px; rnk[px]++; }
}

int cmpEdge(const void *a, const void *b) {
    return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

int main() {
    struct Edge edges[E] = {
        {0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4}
    };
    
    qsort(edges, E, sizeof(struct Edge), cmpEdge);
    for (int i = 0; i < V; i++) { parent[i] = i; rnk[i] = 0; }
    
    int mstCost = 0;
    printf("MST Edges:\n");
    for (int i = 0; i < E; i++) {
        int u = edges[i].src, v = edges[i].dest;
        if (find(u) != find(v)) {
            unite(u, v);
            printf("%d -- %d (weight %d)\n", u, v, edges[i].weight);
            mstCost += edges[i].weight;
        }
    }
    printf("MST Cost: %d\n", mstCost);
    return 0;
}

// Bellman-Ford Algorithm
#include <stdio.h>
#include <limits.h>
#define V 5
#define E 8

struct Edge { int src, dest, weight; };

void bellmanFord(struct Edge edges[], int src) {
    int dist[V];
    for (int i = 0; i < V; i++) dist[i] = INT_MAX;
    dist[src] = 0;
    
    for (int i = 1; i < V; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j].src, v = edges[j].dest, w = edges[j].weight;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    
    // Check negative cycle
    for (int j = 0; j < E; j++) {
        int u = edges[j].src, v = edges[j].dest, w = edges[j].weight;
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            printf("Negative cycle detected!\n"); return;
        }
    }
    
    printf("Distances from src %d:\n", src);
    for (int i = 0; i < V; i++) printf("%d: %d\n", i, dist[i]);
}

int main() {
    struct Edge edges[E] = {
        {0,1,-1},{0,2,4},{1,2,3},{1,3,2},
        {1,4,2},{3,2,5},{3,1,1},{4,3,-3}
    };
    bellmanFord(edges, 0);
    return 0;
}

// Floyd-Warshall All Pairs Shortest Path
#include <stdio.h>
#include <limits.h>
#define V 4
#define INF 99999

void floydWarshall(int graph[][V]) {
    int dist[V][V];
    
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
    
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
    
    printf("All-Pairs Shortest Distances:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) printf("%5s", "INF");
            else printf("%5d", dist[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V] = {
        {0,   3,   INF, 7},
        {8,   0,   2,   INF},
        {5,   INF, 0,   1},
        {2,   INF, INF, 0}
    };
    floydWarshall(graph);
    return 0;
}

// N-Queens Problem
#include <stdio.h>
#define N 8

int board[N][N];
int solutions = 0;

int isSafe(int row, int col) {
    for (int i = 0; i < col; i++)
        if (board[row][i]) return 0;
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j]) return 0;
    for (int i = row, j = col; i < N && j >= 0; i++, j--)
        if (board[i][j]) return 0;
    return 1;
}

void solve(int col) {
    if (col == N) {
        solutions++;
        if (solutions == 1) {
            printf("One solution:\n");
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++)
                    printf("%s", board[i][j] ? "Q " : ". ");
                printf("\n");
            }
        }
        return;
    }
    for (int i = 0; i < N; i++) {
        if (isSafe(i, col)) {
            board[i][col] = 1;
            solve(col + 1);
            board[i][col] = 0;
        }
    }
}

int main() {
    solve(0);
    printf("Total solutions for %d-Queens: %d\n", N, solutions);
    return 0;
}

// Sudoku Solver in C
#include <stdio.h>
#define N 9

int grid[N][N] = {
    {5,3,0,0,7,0,0,0,0},
    {6,0,0,1,9,5,0,0,0},
    {0,9,8,0,0,0,0,6,0},
    {8,0,0,0,6,0,0,0,3},
    {4,0,0,8,0,3,0,0,1},
    {7,0,0,0,2,0,0,0,6},
    {0,6,0,0,0,0,2,8,0},
    {0,0,0,4,1,9,0,0,5},
    {0,0,0,0,8,0,0,7,9}
};

int isValid(int row, int col, int num) {
    for (int j = 0; j < N; j++) if (grid[row][j] == num) return 0;
    for (int i = 0; i < N; i++) if (grid[i][col] == num) return 0;
    int sr = row - row%3, sc = col - col%3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (grid[sr+i][sc+j] == num) return 0;
    return 1;
}

int solve() {
    for (int r = 0; r < N; r++)
        for (int c = 0; c < N; c++)
            if (grid[r][c] == 0) {
                for (int num = 1; num <= 9; num++) {
                    if (isValid(r, c, num)) {
                        grid[r][c] = num;
                        if (solve()) return 1;
                        grid[r][c] = 0;
                    }
                }
                return 0;
            }
    return 1;
}

int main() {
    if (solve()) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) printf("%d ", grid[i][j]);
            printf("\n");
        }
    }
    return 0;
}

// KMP String Matching
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void computeLPS(char *pattern, int m, int *lps) {
    int len = 0, i = 1;
    lps[0] = 0;
    while (i < m) {
        if (pattern[i] == pattern[len]) { lps[i++] = ++len; }
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
}

void kmpSearch(char *text, char *pattern) {
    int n = strlen(text), m = strlen(pattern);
    int *lps = malloc(m * sizeof(int));
    computeLPS(pattern, m, lps);
    
    int i = 0, j = 0;
    printf("Pattern '%s' found at indices: ", pattern);
    while (i < n) {
        if (text[i] == pattern[j]) { i++; j++; }
        if (j == m) {
            printf("%d ", i - j);
            j = lps[j - 1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j) j = lps[j - 1];
            else i++;
        }
    }
    printf("\n");
    free(lps);
}

int main() {
    kmpSearch("AABAACAADAABAABA", "AABA");
    kmpSearch("GEEKS FOR GEEKS", "GEEK");
    return 0;
}

// Product of Array Except Self
#include <stdio.h>

void productExceptSelf(int arr[], int n, int result[]) {
    result[0] = 1;
    
    // Left pass
    for (int i = 1; i < n; i++)
        result[i] = result[i-1] * arr[i-1];
    
    // Right pass
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= right;
        right *= arr[i];
    }
}

int main() {
    int arr[] = {1, 2, 3, 4};
    int n = 4;
    int result[4];
    
    productExceptSelf(arr, n, result);
    
    printf("Input:  ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    
    printf("Output: ");
    for (int i = 0; i < n; i++) printf("%d ", result[i]);
    printf("\n");  // 24 12 8 6
    
    return 0;
}

// Pascal's Triangle in C
#include <stdio.h>

void pascalTriangle(int rows) {
    long long triangle[rows][rows];
    
    for (int i = 0; i < rows; i++) {
        triangle[i][0] = 1;
        triangle[i][i] = 1;
        for (int j = 1; j < i; j++)
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
    }
    
    for (int i = 0; i < rows; i++) {
        for (int sp = 0; sp < rows - i; sp++) printf("  ");
        for (int j = 0; j <= i; j++) printf("%4lld", triangle[i][j]);
        printf("\n");
    }
}

// Nth row using combination formula
void nthRow(int n) {
    long long c = 1;
    printf("Row %d: ", n);
    for (int i = 0; i <= n; i++) {
        printf("%lld ", c);
        c = c * (n - i) / (i + 1);
    }
    printf("\n");
}

int main() {
    printf("Pascal's Triangle (6 rows):\n");
    pascalTriangle(6);
    nthRow(5);
    return 0;
}

// Maximum Sliding Window in C
#include <stdio.h>

void maxSlidingWindow(int arr[], int n, int k) {
    int deque[n];
    int front = 0, rear = -1;
    
    printf("Max in each window of size %d: ", k);
    
    for (int i = 0; i < n; i++) {
        // Remove elements outside window
        while (front <= rear && deque[front] < i - k + 1)
            front++;
        
        // Remove smaller elements from rear
        while (front <= rear && arr[deque[rear]] < arr[i])
            rear--;
        
        deque[++rear] = i;
        
        if (i >= k - 1)
            printf("%d ", arr[deque[front]]);
    }
    printf("\n");
}

int main() {
    int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int n = 8, k = 3;
    maxSlidingWindow(arr, n, k);
    // Output: 3 3 5 5 6 7
    
    int arr2[] = {9, 7, 2, 4, 6, 8, 2, 1, 5};
    maxSlidingWindow(arr2, 9, 3);
    return 0;
}

// Word Search in Grid
#include <stdio.h>
#include <string.h>
#define R 3
#define C 4

char grid[R][C] = {
    {'A','B','C','E'},
    {'S','F','C','S'},
    {'A','D','E','E'}
};

int visited[R][C];
int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0};

int dfs(int r, int c, char *word, int idx) {
    if (word[idx] == '\0') return 1;
    if (r<0||r>=R||c<0||c>=C||visited[r][c]||grid[r][c]!=word[idx])
        return 0;
    
    visited[r][c] = 1;
    for (int d = 0; d < 4; d++)
        if (dfs(r+dr[d], c+dc[d], word, idx+1)) {
            visited[r][c] = 0;
            return 1;
        }
    visited[r][c] = 0;
    return 0;
}

int wordSearch(char *word) {
    memset(visited, 0, sizeof(visited));
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (dfs(r, c, word, 0)) return 1;
    return 0;
}

int main() {
    printf("'ABCCED': %s\n", wordSearch("ABCCED") ? "Found" : "Not Found");
    printf("'SEE': %s\n",    wordSearch("SEE")    ? "Found" : "Not Found");
    printf("'ABCB': %s\n",   wordSearch("ABCB")   ? "Found" : "Not Found");
    return 0;
}

// Radix Sort in C
#include <stdio.h>
#include <string.h>

int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i];
    return max;
}

void countSort(int arr[], int n, int exp) {
    int output[n], count[10];
    memset(count, 0, sizeof(count));
    
    for (int i = 0; i < n; i++) count[(arr[i]/exp)%10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i--) {
        output[count[(arr[i]/exp)%10]-1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }
    for (int i = 0; i < n; i++) arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int m = getMax(arr, n);
    for (int exp = 1; m/exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = 8;
    
    printf("Before: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    
    radixSort(arr, n);
    
    printf("\nAfter:  ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

// Shell Sort in C
#include <stdio.h>

void shellSort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90, 1, 55, 47};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Before Shell Sort: "); print(arr, n);
    shellSort(arr, n);
    printf("After  Shell Sort: "); print(arr, n);
    return 0;
}

// Interpolation Search in C
#include <stdio.h>

int interpolationSearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    
    while (low <= high &&
           target >= arr[low] &&
           target <= arr[high]) {
        
        if (low == high) {
            if (arr[low] == target) return low;
            return -1;
        }
        
        // Estimate position using interpolation formula
        int pos = low + ((double)(high - low) /
                  (arr[high] - arr[low])) *
                  (target - arr[low]);
        
        if (arr[pos] == target) return pos;
        if (arr[pos] < target)  low  = pos + 1;
        else                    high = pos - 1;
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    int idx = interpolationSearch(arr, n, 70);
    printf("Search 70:  index = %d\n", idx);   // 6
    
    idx = interpolationSearch(arr, n, 45);
    printf("Search 45:  index = %d\n", idx);   // -1
    
    idx = interpolationSearch(arr, n, 10);
    printf("Search 10:  index = %d\n", idx);   // 0
    
    idx = interpolationSearch(arr, n, 100);
    printf("Search 100: index = %d\n", idx);   // 9
    
    return 0;
}

// Bit Manipulation in C
#include <stdio.h>

// Check if bit at position p is set
int isBitSet(int n, int p) { return (n >> p) & 1; }

// Set bit at position p
int setBit(int n, int p) { return n | (1 << p); }

// Clear bit at position p
int clearBit(int n, int p) { return n & ~(1 << p); }

// Toggle bit at position p
int toggleBit(int n, int p) { return n ^ (1 << p); }

// Count set bits (Brian Kernighan)
int countBits(int n) {
    int count = 0;
    while (n) { n &= (n - 1); count++; }
    return count;
}

// Check power of 2
int isPowerOf2(int n) { return n > 0 && (n & (n - 1)) == 0; }

// Swap without temp
void swapBits(int *a, int *b) { *a ^= *b; *b ^= *a; *a ^= *b; }

// Find only non-duplicate in array (all others appear twice)
int findUnique(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++) result ^= arr[i];
    return result;
}

int main() {
    int n = 0b10110100;  // 180
    printf("Number: %d\n", n);
    printf("Bit 2 set? %d\n",    isBitSet(n, 2));
    printf("Set bit 0:    %d\n", setBit(n, 0));
    printf("Clear bit 4:  %d\n", clearBit(n, 4));
    printf("Toggle bit 7: %d\n", toggleBit(n, 7));
    printf("Count bits:   %d\n", countBits(n));
    printf("isPowerOf2(16): %d\n", isPowerOf2(16));
    printf("isPowerOf2(18): %d\n", isPowerOf2(18));
    
    int x = 15, y = 27;
    swapBits(&x, &y);
    printf("After swap: x=%d, y=%d\n", x, y);
    
    int arr[] = {2, 3, 5, 4, 5, 3, 4};
    printf("Unique element: %d\n", findUnique(arr, 7));  // 2
    
    return 0;
}

// Multithreading in C using pthreads
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define NUM_THREADS 4
#define ARRAY_SIZE  1000000

int array[ARRAY_SIZE];
long long partialSums[NUM_THREADS];
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
long long globalCounter = 0;

typedef struct {
    int threadId;
    int start;
    int end;
} ThreadArgs;

// Thread function: compute partial sum
void* computeSum(void *arg) {
    ThreadArgs *args = (ThreadArgs*)arg;
    long long sum = 0;
    
    for (int i = args->start; i < args->end; i++)
        sum += array[i];
    
    partialSums[args->threadId] = sum;
    
    // Thread-safe counter increment
    pthread_mutex_lock(&mutex);
    globalCounter++;
    printf("Thread %d done. Counter = %lld\n",
           args->threadId, globalCounter);
    pthread_mutex_unlock(&mutex);
    
    pthread_exit(NULL);
}

int main() {
    // Initialize array
    for (int i = 0; i < ARRAY_SIZE; i++) array[i] = 1;
    
    pthread_t threads[NUM_THREADS];
    ThreadArgs args[NUM_THREADS];
    int chunkSize = ARRAY_SIZE / NUM_THREADS;
    
    // Create threads
    for (int i = 0; i < NUM_THREADS; i++) {
        args[i].threadId = i;
        args[i].start    = i * chunkSize;
        args[i].end      = (i == NUM_THREADS - 1) ?
                            ARRAY_SIZE : (i + 1) * chunkSize;
        
        if (pthread_create(&threads[i], NULL, computeSum, &args[i])) {
            fprintf(stderr, "Error creating thread %d\n", i);
            return 1;
        }
    }
    
    // Wait for all threads
    for (int i = 0; i < NUM_THREADS; i++)
        pthread_join(threads[i], NULL);
    
    // Combine results
    long long totalSum = 0;
    for (int i = 0; i < NUM_THREADS; i++)
        totalSum += partialSums[i];
    
    printf("Total Sum: %lld\n", totalSum);  // 1000000
    printf("Expected:  %d\n",   ARRAY_SIZE);
    
    pthread_mutex_destroy(&mutex);
    return 0;
}