C Programming: Array Manipulation Techniques (Peak Finding and Reversal)

This tutorial explores array manipulation in C programming, focusing on efficient techniques for finding a peak element (using a modified binary search) and reversing an array (using recursion). Learn these advanced array operations to improve your C programming skills.

Top Coding Interview Questions on Arrays (C)

Arrays in C

An array in C is a collection of elements of the same data type, stored in contiguous memory locations. Elements are accessed using their index (starting from 0).

Finding a Peak Element

Question 1: First Element Not Smaller Than Neighbors

Find the first element in an array that is greater than or equal to both its left and right neighbors (a "peak" element).

Approach:

This uses a modified binary search. Since we only need *one* peak element, we can efficiently eliminate parts of the array that don't contain it.

C Code:

C Code


int Peak(int arr[], int l, int h, int n) {
    int mid = l + (h - l) / 2;
    if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid + 1] <= arr[mid])) {
        return mid;
    }
    if (mid > 0 && arr[mid - 1] > arr[mid]) {
        return Peak(arr, l, mid - 1, n);
    } else {
        return Peak(arr, mid + 1, h, n);
    }
}

Reversing an Array (Recursive)

Question 2: Reversing an Array Using Recursion

Reverse the elements of an array using recursion.

Approach:

Recursively swap elements from the beginning and end of the array until the middle is reached.

C Code:

C Code


void reverse(int l, int h, int arr[]) {
    if (l >= h) return;
    int temp = arr[l];
    arr[l] = arr[h];
    arr[h] = temp;
    reverse(l + 1, h - 1, arr);
}

Segregating 0s and 1s

Question 3: Segregating 0s and 1s

Segregate an array containing only 0s and 1s into 0s followed by 1s, with only one pass through the array.

Approach:

Two approaches are shown below using different pointer strategies. Both achieve the goal in a single pass.

C Code (Two Pointers, Opposite Ends):

C Code (Two Pointers, Opposite Ends)


int* segregation(int arr[], int n) {
    int l = 0, h = n - 1;
    while (l < h) {
        if (arr[l] == 1 && arr[h] == 0) {
            int temp = arr[l];
            arr[l] = arr[h];
            arr[h] = temp;
        }
        if (arr[l] == 0) l++;
        if (arr[h] == 1) h--;
    }
    return arr;
}

C Code (Two Pointers, From Beginning):

C Code (Two Pointers, From Beginning)


int* segregation(int arr[], int n) {
    int i, j = 0;
    for (i = 0; i < n; i++) {
        if (arr[i] == 0) {
            if (i != j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            j++;
        }
    }
    return arr;
}

Moving Negative Elements

Question 4: Moving Negative Elements

Rearrange an array of positive and negative integers so that all negative integers appear before all positive integers.

Approach:

Similar to the 0s and 1s segregation, we use two pointers to efficiently rearrange elements in a single pass.

C Code (Two Pointers, Opposite Ends):

C Code (Two Pointers, Opposite Ends)


int* arrangement(int arr[], int n) {
    int l = 0, h = n - 1;
    while (l < h) {
        if (arr[l] < 0) l++;
        else if (arr[h] >= 0) h--;
        else {
            int temp = arr[l];
            arr[l] = arr[h];
            arr[h] = temp;
        }
    }
    return arr;
}

C Code (Two Pointers, From Beginning):

C Code (Two Pointers, From Beginning)


int* arrangement(int arr[], int n) {
    int i, j = 0;
    for (i = 0; i < n; i++) {
        if (arr[i] < 0) {
            if (i != j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            j++;
        }
    }
    return arr;
}

Maximum Sum of k Consecutive Elements

Question 5: Maximum Sum of k Consecutive Elements

Find the maximum sum of any k consecutive elements within a given array.

Approach:

The efficient approach uses the "sliding window technique".

C Code:

C Code


int maxsum(int a[], int k, int n) {
    if (n < k) return -1;
    int i, sum = 0, maxm = 0;
    for (i = 0; i < k; i++) maxm += a[i];
    sum = maxm;
    for (i = k; i < n; i++) {
        sum += a[i] - a[i - k];
        if (sum > maxm) maxm = sum;
    }
    return maxm;
}

Subarray with a Given Sum

Question 6: Subarray with Given Sum

Find a subarray within an array of non-negative numbers that sums to a given target sum.

Approach:

This uses a sliding window technique, taking advantage of the fact that all numbers are non-negative.

C Code:

C Code


void subarray(int a[], int sum, int n) {
    int cursum = a[0], start = 0, i;
    for (i = 1; i <= n; i++) {
        while (cursum > sum && start < i - 1) {
            cursum -= a[start];
            start++;
        }
        if (cursum == sum) {
            printf("Sub-array found from index %d to %d\n", start, i - 1);
            return;
        }
        if (i < n) cursum += a[i];
    }
    printf("No sub-array found with the given sum\n");
}

Counting Occurrences in a Sorted Array

Question 7: Counting Occurrences

Count the occurrences of a given integer in a sorted array.

Approach:

A binary search can efficiently find the first and last occurrences of the target number. The difference in their indices gives the count.

Counting Occurrences in a Sorted Array (Continued)

Question 7: Counting Occurrences (Continued)

This problem efficiently counts occurrences using a modified binary search to find the first and last indices of the target value.

C Code:

firstoc Function (Finds First Occurrence)


int firstoc(int arr[], int l, int h, int k, int n) {
    if (h >= l) {
        int mid = l + (h - l) / 2;
        if ((mid == 0 || k > arr[mid - 1]) && arr[mid] == k) {
            return mid;
        } else if (k > arr[mid]) {
            return firstoc(arr, mid + 1, h, k, n);
        } else {
            return firstoc(arr, l, mid - 1, k, n);
        }
    }
    return -1;
}

lastoc Function (Finds Last Occurrence)


int lastoc(int arr[], int l, int h, int k, int n) {
    if (h >= l) {
        int mid = l + (h - l) / 2;
        if ((mid == n - 1 || k < arr[mid + 1]) && arr[mid] == k) {
            return mid;
        } else if (k < arr[mid]) {
            return lastoc(arr, l, mid - 1, k, n);
        } else {
            return lastoc(arr, mid + 1, h, k, n);
        }
    }
    return -1;
}

count Function (Counts Occurrences)


int count(int arr[], int k, int n) {
    int first = firstoc(arr, 0, n - 1, k, n);
    if (first == -1) return 0;
    int last = lastoc(arr, first, n - 1, k, n);
    return last - first + 1;
}

Finding LCM Using GCD

Question 8: Finding LCM Using GCD

Efficiently calculate the least common multiple (LCM) of two numbers using their greatest common divisor (GCD).

Approach:

Uses the relationship: LCM(a, b) = (a * b) / GCD(a, b)

C Code:

C Code


int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

Sum and Reverse of Digits

Question 9: Sum and Reverse of Digits

Calculate the sum of the digits of a number and print the number in reversed order.

C Code:

C Code


int rev(int num) {
    int sum = 0, reversed = 0, remainder;
    while (num > 0) {
        remainder = num % 10;
        sum += remainder;
        reversed = reversed * 10 + remainder;
        num /= 10;
    }
    printf("Sum of digits: %d\n", sum);
    return reversed;
}

Leap Year Check

Question 10: Leap Year Check

Determine whether a given year is a leap year.

C Code:

C Code


void leap(int year) {
    if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
        printf("%d is a leap year\n", year);
    } else {
        printf("%d is not a leap year\n", year);
    }
}