Lab Sheet 4: Advanced Search & Sorting

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

Authors

PARTH MUNJAL

AKARSH JAIN

Published

March 30, 2026

Q1: Search in a sorted 2D matrix

Description: Search for K in an M x N matrix where rows and columns are sorted. Time Complexity: O(M + N).

Sample Input

4 4
10 20 30 40
15 25 35 45
27 29 37 48
32 33 39 50
29

Sample Output

2 1

Solution

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

void searchMatrix(int m, int n, int **matrix, int k) {
    int i = 0, j = n - 1;
    while (i < m && j >= 0) {
        if (matrix[i][j] == k) {
            printf("%d %d\n", i, j);
            return;
        }
        if (matrix[i][j] > k) j--;
        else i++;
    }
    printf("-1\n");
}

int main() {
    int m, n, k;
    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]);
    }
    if (scanf("%d", &k) != 1) k = 0;
    searchMatrix(m, n, mat, k);
    
    for (int i = 0; i < m; i++) free(mat[i]);
    free(mat);
    return 0;
}

Q2: Zig-Zag Group Sorting

Description: Process elements in groups of increasing size (1, 2, 3…), alternating between front and back.

Sample Input

10
10 9 8 7 6 5 4 3 2 1

Sample Output

10 7 8 9 3 4 5 6 1 2

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 *arr = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    int left = 0, right = n - 1, k = 1;
    int fromFront = 1;
    while (left <= right) {
        int len = (right - left + 1 < k) ? (right - left + 1) : k;
        if (fromFront) {
            qsort(&arr[left], len, sizeof(int), compare);
            left += len;
        } else {
            qsort(&arr[right - len + 1], len, sizeof(int), compare);
            right -= len;
        }
        k++;
        fromFront = !fromFront;
    }
    for (int i = 0; i < n; i++) printf("%d%s", arr[i], (i == n - 1) ? "" : " ");
    printf("\n");
    free(arr);
    return 0;
}

Q3: Same Element beyond K

Description: Find if there exist two equal elements with distance > K using sorting.

Sample Input

6 2
1 2 3 1 4 5

Sample Output

0 3

Solution

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

typedef struct {
    int val;
    int idx;
} Element;

int comp(const void* a, const void* b) {
    Element* e1 = (Element*)a;
    Element* e2 = (Element*)b;
    if (e1->val != e2->val) return e1->val - e2->val;
    return e1->idx - e2->idx;
}

int main() {
    int n, k;
    if (scanf("%d %d", &n, &k) != 2) return 1;
    Element *elements = (Element *)malloc(n * sizeof(Element));
    for (int i = 0; i < n; i++) {
        scanf("%d", &elements[i].val);
        elements[i].idx = i;
    }
    qsort(elements, n, sizeof(Element), comp);
    
    for (int i = 0; i < n - 1; i++) {
        if (elements[i].val == elements[i+1].val) {
            int minIdx = elements[i].idx, maxIdx = elements[i].idx;
            int j = i + 1;
            while(j < n && elements[j].val == elements[i].val) {
                if(elements[j].idx < minIdx) minIdx = elements[j].idx;
                if(elements[j].idx > maxIdx) maxIdx = elements[j].idx;
                j++;
            }
            if (maxIdx - minIdx > k) { 
                printf("%d %d\n", minIdx, maxIdx); 
                free(elements);
                return 0; 
            }
            i = j - 1;
        }
    }
    printf("-1\n");
    free(elements);
    return 0;
}

Q4: where is gROOT?

Description: Largest integer X such that X^2 \le K.

Sample Input

Sample Output

Solution

#include <stdio.h>

int main() {
    long long k;
    if (scanf("%lld", &k) != 1) return 1;
    long long low = 0, high = k, ans = 0;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (mid <= 3037000499LL && mid * mid <= k) { // mid*mid < 2^63
            ans = mid;
            low = mid + 1;
        } else if (mid > 3037000499LL) high = mid - 1;
        else high = mid - 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Q5: Bitwise Strength Sort

Description: Sort by count of 1s (desc), then by value (desc).

Sample Input

4
3 5 7 8

Sample Output

7 5 3 8

Solution

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

int countSetBits(int n) {
    int count = 0;
    while (n > 0) { n &= (n - 1); count++; }
    return count;
}

typedef struct {
    int val;
    int strength;
} Num;

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

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

Q6: Finding the Middle Score

Description: Find median of a matrix where each row is sorted.

Sample Input

Sample Output

Solution

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

int countLessEqual(int r, int c, int **mat, int mid) {
    int count = 0;
    for (int i = 0; i < r; i++) {
        int low = 0, high = c - 1;
        while (low <= high) {
            int m = low + (high - low) / 2;
            if (mat[i][m] <= mid) low = m + 1;
            else high = m - 1;
        }
        count += low;
    }
    return count;
}

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 low = -2e9, high = 2e9;
    int target = (r * c + 1) / 2;
    int ans = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (countLessEqual(r, c, mat, mid) >= target) {
            ans = mid;
            high = mid - 1;
        } else low = mid + 1;
    }
    printf("%d\n", ans);
    for (int i = 0; i < r; i++) free(mat[i]);
    free(mat);
    return 0;
}

Q7: The K-th Missing Frequency

Description: Find the K-th missing positive integer in a sorted list.

Sample Input

5 5
2 3 4 7 11

Sample Output

Solution

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

int findKthMissing(int arr[], int n, int k) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int missing = arr[mid] - (mid + 1);
        if (missing < k) low = mid + 1;
        else high = mid - 1;
    }
    return low + k;
}

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

Q8: The Minimum Timeline for Painting

Description: Assign boards to K painters to minimize maximum workload.

Sample Input

4 2
10 20 30 40

Sample Output

Solution

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

int canPaint(int arr[], int n, int k, int limit) {
    int painters = 1, current = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > limit) return 0;
        if (current + arr[i] > limit) {
            painters++;
            current = arr[i];
        } else current += arr[i];
    }
    return painters <= k;
}

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

Q9: The Memory Map Validator

Description: Check if total assigned memory intervals are contiguous or fragmented.

Sample Input

Sample Output

0 10
0 30
5 15
10 25
Contiguous

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);
    
    for (int i = 0; i < n; i++) printf("%d %d\n", inters[i].start, inters[i].end);
    
    int maxEnd = inters[0].end;
    for (int i = 1; i < n; i++) {
        if (inters[i].start > maxEnd) {
            printf("Fragmented\n");
            free(inters);
            return 0;
        }
        if (inters[i].end > maxEnd) maxEnd = inters[i].end;
    }
    printf("Contiguous\n");
    free(inters);
    return 0;
}

Q10: The Fair Tax Cap Optimizer

Description: Find smallest integer Cap C such that total tax collected \ge G.

Sample Input

3 25
10 20 30

Sample Output

Solution

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

long long calculateTax(int incomes[], int n, int cap) {
    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += (incomes[i] < cap) ? incomes[i] : cap;
    }
    return total;
}

int main() {
    int n;
    long long g;
    if (scanf("%d %lld", &n, &g) != 2) return 1;
    int *incomes = (int *)malloc(n * sizeof(int));
    int maxInc = 0;
    long long totalPossible = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &incomes[i]);
        if (incomes[i] > maxInc) maxInc = incomes[i];
        totalPossible += incomes[i];
    }
    
    if (totalPossible < g) {
        printf("-1\n");
        free(incomes);
        return 0;
    }
    
    int low = 0, high = maxInc, ans = maxInc;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (calculateTax(incomes, n, mid) >= g) {
            ans = mid;
            high = mid - 1;
        } else low = mid + 1;
    }
    printf("%d\n", ans);
    free(incomes);
    return 0;
}

--- title: "Lab Sheet 4: Advanced Search & Sorting" 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: Search in a sorted 2D matrix **Description:** Search for K in an M x N matrix where rows and columns are sorted. Time Complexity: $O(M + N)$. ::: {.callout-note title="Sample Input"} ``` 4 4 10 20 30 40 15 25 35 45 27 29 37 48 32 33 39 50 29 ``` ::: ::: {.callout-note title="Sample Output"} ``` 2 1 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> void searchMatrix(int m, int n, int **matrix, int k) { int i = 0, j = n - 1; while (i < m && j >= 0) { if (matrix[i][j] == k) { printf("%d %d\n", i, j); return; } if (matrix[i][j] > k) j--; else i++; } printf("-1\n"); } int main() { int m, n, k; 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]); } if (scanf("%d", &k) != 1) k = 0; searchMatrix(m, n, mat, k); for (int i = 0; i < m; i++) free(mat[i]); free(mat); return 0; } ``` ::: # Q2: Zig-Zag Group Sorting **Description:** Process elements in groups of increasing size (1, 2, 3...), alternating between front and back. ::: {.callout-note title="Sample Input"} ``` 10 10 9 8 7 6 5 4 3 2 1 ``` ::: ::: {.callout-note title="Sample Output"} ``` 10 7 8 9 3 4 5 6 1 2 ``` ::: ::: {.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 *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); int left = 0, right = n - 1, k = 1; int fromFront = 1; while (left <= right) { int len = (right - left + 1 < k) ? (right - left + 1) : k; if (fromFront) { qsort(&arr[left], len, sizeof(int), compare); left += len; } else { qsort(&arr[right - len + 1], len, sizeof(int), compare); right -= len; } k++; fromFront = !fromFront; } for (int i = 0; i < n; i++) printf("%d%s", arr[i], (i == n - 1) ? "" : " "); printf("\n"); free(arr); return 0; } ``` ::: # Q3: Same Element beyond K **Description:** Find if there exist two equal elements with distance $> K$ using sorting. ::: {.callout-note title="Sample Input"} ``` 6 2 1 2 3 1 4 5 ``` ::: ::: {.callout-note title="Sample Output"} ``` 0 3 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> typedef struct { int val; int idx; } Element; int comp(const void* a, const void* b) { Element* e1 = (Element*)a; Element* e2 = (Element*)b; if (e1->val != e2->val) return e1->val - e2->val; return e1->idx - e2->idx; } int main() { int n, k; if (scanf("%d %d", &n, &k) != 2) return 1; Element *elements = (Element *)malloc(n * sizeof(Element)); for (int i = 0; i < n; i++) { scanf("%d", &elements[i].val); elements[i].idx = i; } qsort(elements, n, sizeof(Element), comp); for (int i = 0; i < n - 1; i++) { if (elements[i].val == elements[i+1].val) { int minIdx = elements[i].idx, maxIdx = elements[i].idx; int j = i + 1; while(j < n && elements[j].val == elements[i].val) { if(elements[j].idx < minIdx) minIdx = elements[j].idx; if(elements[j].idx > maxIdx) maxIdx = elements[j].idx; j++; } if (maxIdx - minIdx > k) { printf("%d %d\n", minIdx, maxIdx); free(elements); return 0; } i = j - 1; } } printf("-1\n"); free(elements); return 0; } ``` ::: # Q4: where is gROOT? **Description:** Largest integer $X$ such that $X^2 \le K$. ::: {.callout-note title="Sample Input"} ``` 148000 ``` ::: ::: {.callout-note title="Sample Output"} ``` 384 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> int main() { long long k; if (scanf("%lld", &k) != 1) return 1; long long low = 0, high = k, ans = 0; while (low <= high) { long long mid = low + (high - low) / 2; if (mid <= 3037000499LL && mid * mid <= k) { // mid*mid < 2^63 ans = mid; low = mid + 1; } else if (mid > 3037000499LL) high = mid - 1; else high = mid - 1; } printf("%lld\n", ans); return 0; } ``` ::: # Q5: Bitwise Strength Sort **Description:** Sort by count of 1s (desc), then by value (desc). ::: {.callout-note title="Sample Input"} ``` 4 3 5 7 8 ``` ::: ::: {.callout-note title="Sample Output"} ``` 7 5 3 8 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int countSetBits(int n) { int count = 0; while (n > 0) { n &= (n - 1); count++; } return count; } typedef struct { int val; int strength; } Num; int compare(const void* a, const void* b) { Num* n1 = (Num*)a; Num* n2 = (Num*)b; if (n1->strength != n2->strength) return n2->strength - n1->strength; return n2->val - n1->val; } int main() { int n; if (scanf("%d", &n) != 1) return 1; Num *nums = (Num *)malloc(n * sizeof(Num)); for (int i = 0; i < n; i++) { scanf("%d", &nums[i].val); nums[i].strength = countSetBits(nums[i].val); } qsort(nums, n, sizeof(Num), compare); for (int i = 0; i < n; i++) printf("%d%s", nums[i].val, (i == n - 1) ? "" : " "); printf("\n"); free(nums); return 0; } ``` ::: # Q6: Finding the Middle Score **Description:** Find median of a matrix where each row is sorted. ::: {.callout-note title="Sample Input"} ``` 3 3 1 10 20 2 15 25 3 30 40 ``` ::: ::: {.callout-note title="Sample Output"} ``` 15 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int countLessEqual(int r, int c, int **mat, int mid) { int count = 0; for (int i = 0; i < r; i++) { int low = 0, high = c - 1; while (low <= high) { int m = low + (high - low) / 2; if (mat[i][m] <= mid) low = m + 1; else high = m - 1; } count += low; } return count; } 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 low = -2e9, high = 2e9; int target = (r * c + 1) / 2; int ans = high; while (low <= high) { int mid = low + (high - low) / 2; if (countLessEqual(r, c, mat, mid) >= target) { ans = mid; high = mid - 1; } else low = mid + 1; } printf("%d\n", ans); for (int i = 0; i < r; i++) free(mat[i]); free(mat); return 0; } ``` ::: # Q7: The K-th Missing Frequency **Description:** Find the K-th missing positive integer in a sorted list. ::: {.callout-note title="Sample Input"} ``` 5 5 2 3 4 7 11 ``` ::: ::: {.callout-note title="Sample Output"} ``` 9 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int findKthMissing(int arr[], int n, int k) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; int missing = arr[mid] - (mid + 1); if (missing < k) low = mid + 1; else high = mid - 1; } return low + k; } int main() { int n, k; if (scanf("%d %d", &n, &k) != 2) return 1; int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); printf("%d\n", findKthMissing(arr, n, k)); free(arr); return 0; } ``` ::: # Q8: The Minimum Timeline for Painting **Description:** Assign boards to K painters to minimize maximum workload. ::: {.callout-note title="Sample Input"} ``` 4 2 10 20 30 40 ``` ::: ::: {.callout-note title="Sample Output"} ``` 60 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> int canPaint(int arr[], int n, int k, int limit) { int painters = 1, current = 0; for (int i = 0; i < n; i++) { if (arr[i] > limit) return 0; if (current + arr[i] > limit) { painters++; current = arr[i]; } else current += arr[i]; } return painters <= k; } int main() { int n, k; if (scanf("%d %d", &n, &k) != 2) return 1; int *arr = (int *)malloc(n * sizeof(int)); int low = 0, high = 0; for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); if (arr[i] > low) low = arr[i]; high += arr[i]; } int ans = high; while (low <= high) { int mid = low + (high - low) / 2; if (canPaint(arr, n, k, mid)) { ans = mid; high = mid - 1; } else low = mid + 1; } printf("%d\n", ans); free(arr); return 0; } ``` ::: # Q9: The Memory Map Validator **Description:** Check if total assigned memory intervals are contiguous or fragmented. ::: {.callout-note title="Sample Input"} ``` 4 10 25 0 30 5 15 0 10 ``` ::: ::: {.callout-note title="Sample Output"} ``` 0 10 0 30 5 15 10 25 Contiguous ``` ::: ::: {.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); for (int i = 0; i < n; i++) printf("%d %d\n", inters[i].start, inters[i].end); int maxEnd = inters[0].end; for (int i = 1; i < n; i++) { if (inters[i].start > maxEnd) { printf("Fragmented\n"); free(inters); return 0; } if (inters[i].end > maxEnd) maxEnd = inters[i].end; } printf("Contiguous\n"); free(inters); return 0; } ``` ::: # Q10: The Fair Tax Cap Optimizer **Description:** Find smallest integer Cap C such that total tax collected $\ge G$. ::: {.callout-note title="Sample Input"} ``` 3 25 10 20 30 ``` ::: ::: {.callout-note title="Sample Output"} ``` 9 ``` ::: ::: {.callout-tip collapse="true" title="Solution"} ```c #include <stdio.h> #include <stdlib.h> long long calculateTax(int incomes[], int n, int cap) { long long total = 0; for (int i = 0; i < n; i++) { total += (incomes[i] < cap) ? incomes[i] : cap; } return total; } int main() { int n; long long g; if (scanf("%d %lld", &n, &g) != 2) return 1; int *incomes = (int *)malloc(n * sizeof(int)); int maxInc = 0; long long totalPossible = 0; for (int i = 0; i < n; i++) { scanf("%d", &incomes[i]); if (incomes[i] > maxInc) maxInc = incomes[i]; totalPossible += incomes[i]; } if (totalPossible < g) { printf("-1\n"); free(incomes); return 0; } int low = 0, high = maxInc, ans = maxInc; while (low <= high) { int mid = low + (high - low) / 2; if (calculateTax(incomes, n, mid) >= g) { ans = mid; high = mid - 1; } else low = mid + 1; } printf("%d\n", ans); free(incomes); return 0; } ``` :::