Arrays: Day 6 Challenges

Welcome to Day 6 of the 100 Days DSA Challenge! Today, we'll tackle some fundamental array problems using C language. Let's dive into the problems and their solutions.

1. Rotate an Array to the Right by k Steps

Problem: Write a program to rotate an array of size n by k steps to the right in O(n) time without using extra space.

#include <stdio.h>

void reverse(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

void rotateRight(int arr[], int n, int k) {
    k = k % n; // In case k is greater than n
    reverse(arr, 0, n - 1);
    reverse(arr, 0, k - 1);
    reverse(arr, k, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    rotateRight(arr, n, k);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2. Find the Missing Number

Problem: Given an array containing n-1 distinct integers in the range of 1 to n, write a program to find the missing number in O(n) time using a mathematical formula or XOR.

#include <stdio.h>

int findMissingNumber(int arr[], int n) {
    int total = n * (n + 1) / 2;
    int sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum += arr[i];
    }
    return total - sum;
}

int main() {
    int arr[] = {1, 2, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]) + 1;
    int missingNumber = findMissingNumber(arr, n);
    printf("The missing number is %d\n", missingNumber);
    return 0;
}

3. Rearrange an Array

Problem: Rearrange an array such that the first element is the largest, the second is the smallest, the third is the second largest, and so on. Solve this in O(n) time using no extra space.

#include <stdio.h>

void rearrangeArray(int arr[], int n) {
    int maxIdx = n - 1, minIdx = 0;
    int maxElement = arr[maxIdx] + 1;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            arr[i] += (arr[maxIdx] % maxElement) * maxElement;
            maxIdx--;
        } else {
            arr[i] += (arr[minIdx] % maxElement) * maxElement;
            minIdx++;
        }
    }
    for (int i = 0; i < n; i++) {
        arr[i] /= maxElement;
    }
}

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

4. Maximum Sum Subarray

Problem: Write a program to find the contiguous subarray with the maximum sum in O(n) time.

#include <stdio.h>
#include <limits.h>

int maxSubArraySum(int arr[], int n) {
    int maxSum = INT_MIN, currentSum = 0;
    for (int i = 0; i < n; i++) {
        currentSum += arr[i];
        if (maxSum < currentSum) {
            maxSum = currentSum;
        }
        if (currentSum < 0) {
            currentSum = 0;
        }
    }
    return maxSum;
}

int main() {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxSum = maxSubArraySum(arr, n);
    printf("Max. contiguous subarray sum is %d\n", maxSum);
    return 0;
}

5. Frequency of Each Element

Problem: Write a program to count the frequency of each element in an array in O(n) time without using extra space (modify the array temporarily if needed).

#include <stdio.h>

void countFrequencies(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i]--;
    }
    for (int i = 0; i < n; i++) {
        arr[arr[i] % n] += n;
    }
    for (int i = 0; i < n; i++) {
        printf("Element %d: %d times\n", i + 1, arr[i] / n);
    }
    for (int i = 0; i < n; i++) {
        arr[i] = arr[i] % n + 1;
    }
}

int main() {
    int arr[] = {2, 3, 3, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    countFrequencies(arr, n);
    return 0;
}

Conclusion

That wraps up Day 6 of our DSA challenge! Stay tuned for more exciting problems and solutions as we continue to improve our skills in data structures and algorithms

Day 6 of the 100 Days DSA Challenge: Arrays - Problems

Table of contents