Lab Sheet 5: Advanced Topics

DSA Programming Solutions | Instructor: Prof. N L Bhanu Murthy

Authors

PARTH MUNJAL

AKARSH JAIN

Published

March 30, 2026

Q1: Rectangle Sum

Description: Print 2D Prefix Sum Matrix and the sum of a sub-rectangle (a1, b1) to (a2, b2) in O(1) after O(MN) preprocessing.

Sample Input

Sample Output

Sum=23

Solution

#include <stdio.h>
#include <stdlib.h>

int main() {
    int m, n;
    if (scanf("%d %d", &m, &n) != 2) return 1;
    int **mat = (int **)malloc(m * sizeof(int *));
    for (int i = 0; i < m; i++) {
        mat[i] = (int *)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) scanf("%d", &mat[i][j]);
    }

    int **prefix = (int **)malloc((m + 1) * sizeof(int *));
    for (int i = 0; i <= m; i++) prefix[i] = (int *)calloc(n + 1, sizeof(int));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            prefix[i][j] = mat[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
        }
    }

    int a1, b1, a2, b2;
    if (scanf("%d %d %d %d", &a1, &b1, &a2, &b2) == 4) {
        int sum = prefix[a2+1][b2+1] - prefix[a1][b2+1] - prefix[a2+1][b1] + prefix[a1][b1];
        printf("%d\n", sum);
    }

    for (int i = 0; i < m; i++) free(mat[i]);
    free(mat);
    for (int i = 0; i <= m; i++) free(prefix[i]);
    free(prefix);
    return 0;
}

Q2: Maximum Subarray with Equal Difference

Description: Longest subarray where the difference between every adjacent element is equal (Arithmetic Progression).

Test Cases

Case 1: Mixing APs

Input:

10
1 2 3 4 5 10 8 6 4 2

Output: 5 (Both 1..5 and 10..2 have length 5)

Case 2: All Same (Zero Difference)

Input:

4
5 5 5 5

Output: 4

Case 3: Alternating (No AP > 2)

Input:

5
1 10 2 11 3

Output: 2

Case 4: Negative Progressions

Input:

5
-5 -2 1 4 7

Output: 5

Solution

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    if (n < 2) { printf("%d\n", n); free(arr); return 0; }
    int maxLen = 2, currentLen = 2;
    int diff = arr[1] - arr[0];
    for (int i = 2; i < n; i++) {
        if (arr[i] - arr[i-1] == diff) {
            currentLen++;
        } else {
            diff = arr[i] - arr[i-1];
            currentLen = 2;
        }
        if (currentLen > maxLen) maxLen = currentLen;
    }
    printf("%d\n", maxLen);
    free(arr);
    return 0;
}

Q3: Equal XOR on sides

Description: Index where XOR of left elements equals XOR of right elements. O(N) time, O(1) space.

Sample Input

8
2 3 4 2 3 2 6 2

Sample Output

4 6

Solution

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    int totalXor = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        totalXor ^= arr[i];
    }
    
    int leftXor = 0, found = 0;
    for (int i = 0; i < n; i++) {
        int rightXor = totalXor ^ leftXor ^ arr[i];
        if (leftXor == rightXor) {
            printf("%s%d", found ? " " : "", i);
            found = 1;
        }
        leftXor ^= arr[i];
    }
    if (!found) printf("-1");
    printf("\n");
    free(arr);
    return 0;
}

Q4: Maximizing the Minimum Distance Between Towers

Description: Select K towers such that the smallest distance between any two is maximized.

Sample Input

4 3
0 5 8 13

Sample Output

Solution

#include <stdio.h>
#include <stdlib.h>

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

int canPlace(int pos[], int n, int k, int dist) {
    int count = 1, last = pos[0];
    for (int i = 1; i < n; i++) {
        if (pos[i] - last >= dist) {
            count++;
            last = pos[i];
        }
    }
    return count >= k;
}

int main() {
    int n, k;
    if (scanf("%d %d", &n, &k) != 2) return 1;
    int *pos = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &pos[i]);
    qsort(pos, n, sizeof(int), compare);
    
    int low = 1, high = pos[n-1] - pos[0], ans = 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canPlace(pos, n, k, mid)) {
            ans = mid;
            low = mid + 1;
        } else high = mid - 1;
    }
    printf("%d\n", ans);
    free(pos);
    return 0;
}

Q5: The Divisor-Based Ranker

Description: Sort by number of divisors (asc), then by value (desc).

Sample Input

4
6 10 2 4

Sample Output

2 4 10 6

Solution

#include <stdio.h>
#include <stdlib.h>

int countDivisors(int n) {
    int count = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            count++;
            if (i * i != n) count++;
        }
    }
    return count;
}

typedef struct {
    int val, divs;
} Number;

int compare(const void* a, const void* b) {
    Number* n1 = (Number*)a;
    Number* n2 = (Number*)b;
    if (n1->divs != n2->divs) return n1->divs - n2->divs;
    return n2->val - n1->val;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    Number *nums = (Number *)malloc(n * sizeof(Number));
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i].val);
        nums[i].divs = countDivisors(nums[i].val);
    }
    qsort(nums, n, sizeof(Number), compare);
    for (int i = 0; i < n; i++) printf("%d%s", nums[i].val, (i == n - 1) ? "" : " ");
    printf("\n");
    free(nums);
    return 0;
}

Q6: The Matrix Perimeter Erosion

Description: Rotate matrix layers alternating clockwise and counter-clockwise.

Sample Input

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

Sample Output

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

Solution

#include <stdio.h>
#include <stdlib.h>

void rotateLayer(int **mat, int r, int c, int layer, int clockwise) {
    int top = layer, left = layer, bottom = r - 1 - layer, right = c - 1 - layer;
    if (top >= bottom || left >= right) return;

    if (clockwise) {
        int temp = mat[top][left];
        for (int i = top; i < bottom; i++) mat[i][left] = mat[i+1][left];
        for (int i = left; i < right; i++) mat[bottom][i] = mat[bottom][i+1];
        for (int i = bottom; i > top; i--) mat[i][right] = mat[i-1][right];
        for (int i = right; i > left + 1; i--) mat[top][i] = mat[top][i-1];
        mat[top][left+1] = temp;
    } else {
        int temp = mat[top][left];
        for (int i = left; i < right; i++) mat[top][i] = mat[top][i+1];
        for (int i = top; i < bottom; i++) mat[i][right] = mat[i+1][right];
        for (int i = right; i > left; i--) mat[bottom][i] = mat[bottom][i-1];
        for (int i = bottom; i > top + 1; i--) mat[i][left] = mat[i-1][left];
        mat[top+1][left] = temp;
    }
}

int main() {
    int r, c;
    if (scanf("%d %d", &r, &c) != 2) return 1;
    int **mat = (int **)malloc(r * sizeof(int *));
    for (int i = 0; i < r; i++) {
        mat[i] = (int *)malloc(c * sizeof(int));
        for (int j = 0; j < c; j++) scanf("%d", &mat[i][j]);
    }

    int layers = (r < c ? r : c) / 2;
    for (int i = 0; i < layers; i++) {
        rotateLayer(mat, r, c, i, (i % 2 == 0));
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) printf("%d%s", mat[i][j], (j == c - 1) ? "" : " ");
        printf("\n");
        free(mat[i]);
    }
    free(mat);
    return 0;
}

Q7: Kth Largest Element

Description: Find kth largest element using Quick Select.

Sample Input

6
3 2 1 5 6 4
2

Sample Output

Solution

#include <stdio.h>
#include <stdlib.h>

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

int partition(int arr[], int left, int right) {
    int pivot = arr[right], i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) swap(&arr[i++], &arr[j]);
    }
    swap(&arr[i], &arr[right]);
    return i;
}

int quickSelect(int arr[], int left, int right, int k) {
    if (left <= right) {
        int p = partition(arr, left, right);
        if (p == k) return arr[p];
        if (p > k) return quickSelect(arr, left, p - 1, k);
        return quickSelect(arr, p + 1, right, k);
    }
    return -1;
}

int main() {
    int n, k;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    if (scanf("%d", &k) != 1) { free(arr); return 1; }
    
    printf("%d\n", quickSelect(arr, 0, n - 1, n - k));
    free(arr);
    return 0;
}

Q8: The Conference Hall (Merge Intervals)

Description: Merge overlapping time intervals.

Sample Input

Sample Output

1 6
8 10
15 18

Solution

#include <stdio.h>
#include <stdlib.h>

typedef struct { int start, end; } Interval;

int compare(const void* a, const void* b) { return ((Interval*)a)->start - ((Interval*)b)->start; }

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    Interval *inters = (Interval *)malloc(n * sizeof(Interval));
    for (int i = 0; i < n; i++) scanf("%d %d", &inters[i].start, &inters[i].end);
    
    qsort(inters, n, sizeof(Interval), compare);
    
    int k = 0;
    for (int i = 1; i < n; i++) {
        if (inters[k].end >= inters[i].start) {
            if (inters[i].end > inters[k].end) inters[k].end = inters[i].end;
        } else {
            k++;
            inters[k] = inters[i];
        }
    }
    for (int i = 0; i <= k; i++) printf("%d %d\n", inters[i].start, inters[i].end);
    free(inters);
    return 0;
}

Q9: The Zero-Sum Triplets (3Sum)

Description: Find all unique triplets that sum to zero.

Sample Input

6
-1 0 1 2 -1 -4

Sample Output

-1 -1 2
-1 0 1

Solution

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    int *nums = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &nums[i]);
    
    qsort(nums, n, sizeof(int), compare);
    int found = 0;
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                printf("%d %d %d\n", nums[i], nums[l], nums[r]);
                found = 1;
                while (l < r && nums[l] == nums[l+1]) l++;
                while (l < r && nums[r] == nums[r-1]) r--;
                l++; r--;
            } else if (sum < 0) l++;
            else r--;
        }
    }
    if (!found) printf("No triplets found\n");
    free(nums);
    return 0;
}

Q10: Radix Sort

Description: Sort an array using Radix Sort (base 10).

Sample Input

8
170 45 75 90 802 24 2 66

Sample Output

2 24 45 66 75 90 170 802

Solution

#include <stdio.h>
#include <stdlib.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 = (int *)malloc(n * sizeof(int));
    int count[10] = {0};
    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];
    free(output);
}

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

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    int *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    radixSort(arr, n);
    for (int i = 0; i < n; i++) printf("%d%s", arr[i], (i == n - 1) ? "" : " ");
    printf("\n");
    free(arr);
    return 0;
}

--- title: "Lab Sheet 5: Advanced Topics" subtitle: "DSA Programming Solutions | Instructor: Prof. N L Bhanu Murthy" author: - "PARTH MUNJAL" - "AKARSH JAIN" date: last-modified format: html: toc: true toc-depth: 3 code-tools: true number-sections: false theme: cosmo robots: noindex --- # Q1: Rectangle Sum **Description:** Print 2D Prefix Sum Matrix and the sum of a sub-rectangle (a1, b1) to (a2, b2) in $O(1)$ after $O(MN)$ preprocessing. ::: {.callout-note title="Sample Input"} ``` 3 3 1 3 5 2 4 6 3 4 1 1 2 3 3 ``` ::: ::: {.callout-note title="Sample Output"} ``` Sum=23 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int main() { int m, n; if (scanf("%d %d", &m, &n) != 2) return 1; int **mat = (int **)malloc(m * sizeof(int *)); for (int i = 0; i < m; i++) { mat[i] = (int *)malloc(n * sizeof(int)); for (int j = 0; j < n; j++) scanf("%d", &mat[i][j]); } int **prefix = (int **)malloc((m + 1) * sizeof(int *)); for (int i = 0; i <= m; i++) prefix[i] = (int *)calloc(n + 1, sizeof(int)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefix[i][j] = mat[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]; } } int a1, b1, a2, b2; if (scanf("%d %d %d %d", &a1, &b1, &a2, &b2) == 4) { int sum = prefix[a2+1][b2+1] - prefix[a1][b2+1] - prefix[a2+1][b1] + prefix[a1][b1]; printf("%d\n", sum); } for (int i = 0; i < m; i++) free(mat[i]); free(mat); for (int i = 0; i <= m; i++) free(prefix[i]); free(prefix); return 0; } ``` ::: # Q2: Maximum Subarray with Equal Difference **Description:** Longest subarray where the difference between every adjacent element is equal (Arithmetic Progression). ::: {.callout-note title="Test Cases"} #### Case 1: Mixing APs **Input:** ``` 10 1 2 3 4 5 10 8 6 4 2 ``` **Output:** `5` (Both `1..5` and `10..2` have length 5) --- #### Case 2: All Same (Zero Difference) **Input:** ``` 4 5 5 5 5 ``` **Output:** `4` --- #### Case 3: Alternating (No AP > 2) **Input:** ``` 5 1 10 2 11 3 ``` **Output:** `2` --- #### Case 4: Negative Progressions **Input:** ``` 5 -5 -2 1 4 7 ``` **Output:** `5` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int main() { int n; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); if (n < 2) { printf("%d\n", n); free(arr); return 0; } int maxLen = 2, currentLen = 2; int diff = arr[1] - arr[0]; for (int i = 2; i < n; i++) { if (arr[i] - arr[i-1] == diff) { currentLen++; } else { diff = arr[i] - arr[i-1]; currentLen = 2; } if (currentLen > maxLen) maxLen = currentLen; } printf("%d\n", maxLen); free(arr); return 0; } ``` ::: # Q3: Equal XOR on sides **Description:** Index where XOR of left elements equals XOR of right elements. $O(N)$ time, $O(1)$ space. ::: {.callout-note title="Sample Input"} ``` 8 2 3 4 2 3 2 6 2 ``` ::: ::: {.callout-note title="Sample Output"} ``` 4 6 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int main() { int n; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); int totalXor = 0; for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); totalXor ^= arr[i]; } int leftXor = 0, found = 0; for (int i = 0; i < n; i++) { int rightXor = totalXor ^ leftXor ^ arr[i]; if (leftXor == rightXor) { printf("%s%d", found ? " " : "", i); found = 1; } leftXor ^= arr[i]; } if (!found) printf("-1"); printf("\n"); free(arr); return 0; } ``` ::: # Q4: Maximizing the Minimum Distance Between Towers **Description:** Select K towers such that the smallest distance between any two is maximized. ::: {.callout-note title="Sample Input"} ``` 4 3 0 5 8 13 ``` ::: ::: {.callout-note title="Sample Output"} ``` 5 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int compare(const void* a, const void* b) { return *(int*)a - *(int*)b; } int canPlace(int pos[], int n, int k, int dist) { int count = 1, last = pos[0]; for (int i = 1; i < n; i++) { if (pos[i] - last >= dist) { count++; last = pos[i]; } } return count >= k; } int main() { int n, k; if (scanf("%d %d", &n, &k) != 2) return 1; int *pos = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &pos[i]); qsort(pos, n, sizeof(int), compare); int low = 1, high = pos[n-1] - pos[0], ans = 1; while (low <= high) { int mid = low + (high - low) / 2; if (canPlace(pos, n, k, mid)) { ans = mid; low = mid + 1; } else high = mid - 1; } printf("%d\n", ans); free(pos); return 0; } ``` ::: # Q5: The Divisor-Based Ranker **Description:** Sort by number of divisors (asc), then by value (desc). ::: {.callout-note title="Sample Input"} ``` 4 6 10 2 4 ``` ::: ::: {.callout-note title="Sample Output"} ``` 2 4 10 6 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int countDivisors(int n) { int count = 0; for (int i = 1; i * i <= n; i++) { if (n % i == 0) { count++; if (i * i != n) count++; } } return count; } typedef struct { int val, divs; } Number; int compare(const void* a, const void* b) { Number* n1 = (Number*)a; Number* n2 = (Number*)b; if (n1->divs != n2->divs) return n1->divs - n2->divs; return n2->val - n1->val; } int main() { int n; if (scanf("%d", &n) != 1) return 1; Number *nums = (Number *)malloc(n * sizeof(Number)); for (int i = 0; i < n; i++) { scanf("%d", &nums[i].val); nums[i].divs = countDivisors(nums[i].val); } qsort(nums, n, sizeof(Number), compare); for (int i = 0; i < n; i++) printf("%d%s", nums[i].val, (i == n - 1) ? "" : " "); printf("\n"); free(nums); return 0; } ``` ::: # Q6: The Matrix Perimeter Erosion **Description:** Rotate matrix layers alternating clockwise and counter-clockwise. ::: {.callout-note title="Sample Input"} ``` 4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ``` ::: ::: {.callout-note title="Sample Output"} ``` 5 1 2 3 9 7 11 4 13 6 10 8 14 15 16 12 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> void rotateLayer(int **mat, int r, int c, int layer, int clockwise) { int top = layer, left = layer, bottom = r - 1 - layer, right = c - 1 - layer; if (top >= bottom || left >= right) return; if (clockwise) { int temp = mat[top][left]; for (int i = top; i < bottom; i++) mat[i][left] = mat[i+1][left]; for (int i = left; i < right; i++) mat[bottom][i] = mat[bottom][i+1]; for (int i = bottom; i > top; i--) mat[i][right] = mat[i-1][right]; for (int i = right; i > left + 1; i--) mat[top][i] = mat[top][i-1]; mat[top][left+1] = temp; } else { int temp = mat[top][left]; for (int i = left; i < right; i++) mat[top][i] = mat[top][i+1]; for (int i = top; i < bottom; i++) mat[i][right] = mat[i+1][right]; for (int i = right; i > left; i--) mat[bottom][i] = mat[bottom][i-1]; for (int i = bottom; i > top + 1; i--) mat[i][left] = mat[i-1][left]; mat[top+1][left] = temp; } } int main() { int r, c; if (scanf("%d %d", &r, &c) != 2) return 1; int **mat = (int **)malloc(r * sizeof(int *)); for (int i = 0; i < r; i++) { mat[i] = (int *)malloc(c * sizeof(int)); for (int j = 0; j < c; j++) scanf("%d", &mat[i][j]); } int layers = (r < c ? r : c) / 2; for (int i = 0; i < layers; i++) { rotateLayer(mat, r, c, i, (i % 2 == 0)); } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) printf("%d%s", mat[i][j], (j == c - 1) ? "" : " "); printf("\n"); free(mat[i]); } free(mat); return 0; } ``` ::: # Q7: Kth Largest Element **Description:** Find kth largest element using Quick Select. ::: {.callout-note title="Sample Input"} ``` 6 3 2 1 5 6 4 2 ``` ::: ::: {.callout-note title="Sample Output"} ``` 5 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int partition(int arr[], int left, int right) { int pivot = arr[right], i = left; for (int j = left; j < right; j++) { if (arr[j] <= pivot) swap(&arr[i++], &arr[j]); } swap(&arr[i], &arr[right]); return i; } int quickSelect(int arr[], int left, int right, int k) { if (left <= right) { int p = partition(arr, left, right); if (p == k) return arr[p]; if (p > k) return quickSelect(arr, left, p - 1, k); return quickSelect(arr, p + 1, right, k); } return -1; } int main() { int n, k; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); if (scanf("%d", &k) != 1) { free(arr); return 1; } printf("%d\n", quickSelect(arr, 0, n - 1, n - k)); free(arr); return 0; } ``` ::: # Q8: The Conference Hall (Merge Intervals) **Description:** Merge overlapping time intervals. ::: {.callout-note title="Sample Input"} ``` 4 1 3 2 6 8 10 15 18 ``` ::: ::: {.callout-note title="Sample Output"} ``` 1 6 8 10 15 18 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> typedef struct { int start, end; } Interval; int compare(const void* a, const void* b) { return ((Interval*)a)->start - ((Interval*)b)->start; } int main() { int n; if (scanf("%d", &n) != 1) return 1; Interval *inters = (Interval *)malloc(n * sizeof(Interval)); for (int i = 0; i < n; i++) scanf("%d %d", &inters[i].start, &inters[i].end); qsort(inters, n, sizeof(Interval), compare); int k = 0; for (int i = 1; i < n; i++) { if (inters[k].end >= inters[i].start) { if (inters[i].end > inters[k].end) inters[k].end = inters[i].end; } else { k++; inters[k] = inters[i]; } } for (int i = 0; i <= k; i++) printf("%d %d\n", inters[i].start, inters[i].end); free(inters); return 0; } ``` ::: # Q9: The Zero-Sum Triplets (3Sum) **Description:** Find all unique triplets that sum to zero. ::: {.callout-note title="Sample Input"} ``` 6 -1 0 1 2 -1 -4 ``` ::: ::: {.callout-note title="Sample Output"} ``` -1 -1 2 -1 0 1 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int compare(const void* a, const void* b) { return *(int*)a - *(int*)b; } int main() { int n; if (scanf("%d", &n) != 1) return 1; int *nums = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &nums[i]); qsort(nums, n, sizeof(int), compare); int found = 0; for (int i = 0; i < n - 2; i++) { if (i > 0 && nums[i] == nums[i-1]) continue; int l = i + 1, r = n - 1; while (l < r) { int sum = nums[i] + nums[l] + nums[r]; if (sum == 0) { printf("%d %d %d\n", nums[i], nums[l], nums[r]); found = 1; while (l < r && nums[l] == nums[l+1]) l++; while (l < r && nums[r] == nums[r-1]) r--; l++; r--; } else if (sum < 0) l++; else r--; } } if (!found) printf("No triplets found\n"); free(nums); return 0; } ``` ::: # Q10: Radix Sort **Description:** Sort an array using Radix Sort (base 10). ::: {.callout-note title="Sample Input"} ``` 8 170 45 75 90 802 24 2 66 ``` ::: ::: {.callout-note title="Sample Output"} ``` 2 24 45 66 75 90 170 802 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.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 = (int *)malloc(n * sizeof(int)); int count[10] = {0}; 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]; free(output); } void radixSort(int arr[], int n) { if (n <= 0) return; int m = getMax(arr, n); for (int exp = 1; m / exp > 0; exp *= 10) countSort(arr, n, exp); } int main() { int n; if (scanf("%d", &n) != 1) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); radixSort(arr, n); for (int i = 0; i < n; i++) printf("%d%s", arr[i], (i == n - 1) ? "" : " "); printf("\n"); free(arr); return 0; } ``` :::