Welcome to Day 6 of my 100 Days of DSA challenge! 🚀 Today was all about diving deeper into the world of arrays. I focused on solving five challenging problems that tested my understanding of advanced array manipulations. Each problem pushed me to think critically about optimizing both time and space complexity, making the learning process even more rewarding.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s keep the momentum going and continue exploring the fascinating depths of data structures and algorithms! 🤖✨
1. Rotate an Array by k Steps to the Right (O(n) Time, No Extra Space)
This program rotates an array to the right by a given number of steps using an in-place reversal method. It begins by reversing the entire array, then reverses the first k elements to reposition them correctly, and finally reverses the remaining elements to restore their order. This ensures efficient rotation in O(n) time without extra space.
Code:
#include <iostream>
using namespace std;
// Function to reverse a portion of the array
void reverse(int arr[], int start, int end) {
while (start < end) {
swap(arr[start], arr[end]);
start++;
end--;
}
}
// Function to rotate the array
void rotateArray(int arr[], int n, int k) {
// Handle cases where k > n
k = k % n;
// Step 1: Reverse the entire array
reverse(arr, 0, n - 1);
// Step 2: Reverse the first k elements
reverse(arr, 0, k - 1);
// Step 3: Reverse the remaining n-k elements
reverse(arr, k, n - 1);
}
int main() {
int n, k;
cout << "Enter the size of the array: ";
cin >> n;
int *arr = new int[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Enter the number of steps to rotate: ";
cin >> k;
rotateArray(arr, n, k);
cout << "The rotated array is: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
delete[] arr;
return 0;
}
Output:
2. Find the Missing Number in an Array of Size n-1 (O(n) Time)
This program finds the missing number in an array of size n−1n-1n−1, containing distinct integers in the range of 1 to nnn. It uses the mathematical formula for the sum of the first nnn natural numbers to compute the expected total sum of the array elements. The program then calculates the actual sum of the given elements, and the missing number is determined by subtracting the actual sum from the expected sum.
Code:
#include <iostream>
using namespace std;
// Function to find the missing number using the sum formula
int missing_number(int arr[], int n) {
// Calculate the expected sum of the first n natural numbers
int correct_sum = n * (n + 1) / 2;
// Calculate the sum of the given array elements
int wrong_sum = 0;
for (int i = 0; i < n - 1; i++) {
wrong_sum += arr[i];
}
// Missing number is the difference between the expected sum and the actual sum
int missing_num = correct_sum - wrong_sum;
return missing_num;
}
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int *arr = new int[n - 1]; // Allocate memory for the array of size n-1 as one element is missing
cout << "Enter the elements of the array: ";
for (int i = 0; i < n - 1; i++) {
cin >> arr[i];
}
int a = missing_number(arr, n);
cout << "The missing number is: " << a;
delete[] arr;
return 0;
}
Output:
3. Rearrange Array Alternately (Largest, Smallest, Second Largest, etc.) in O(n) Time
This program rearranges an array such that the first element is the largest, the second is the smallest, the third is the second largest, and so on. The array is first sorted to ensure order. Then, a rearrangement is performed using modular arithmetic, temporarily storing both the current and rearranged values in each element. The largest elements are placed at even indices, and the smallest elements at odd indices. Finally, each element is divided by a scaling factor to decode the rearranged values. This approach operates in O(n) time and uses no extra space beyond the array itself.
Code:
#include <iostream>
#include <algorithm>
using namespace std;
void rearrange_array(int arr[], int n) {
// Initialize variables for maximum and minimum indices
int max_idx = n - 1; // Index for the largest element
int min_idx = 0; // Index for the smallest element
int max_elem = arr[max_idx] + 1; // Store a number greater than the maximum element
// Traverse the array and rearrange elements
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
// Place the largest element at even indices
arr[i] += (arr[max_idx] % max_elem) * max_elem;
max_idx--;
}
else {
// Place the smallest element at odd indices
arr[i] += (arr[min_idx] % max_elem) * max_elem;
min_idx++;
}
}
// Divide all elements by max_elem to get the final rearranged array
for (int i = 0; i < n; i++) {
arr[i] /= max_elem;
}
}
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int *arr = new int[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr, arr + n);
rearrange_array(arr, n);
cout << "The rearranged array is: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
delete[] arr;
return 0;
}
Output:
4. Contiguous Subarray with Maximum Sum in O(n) Time
The program finds the maximum sum of a contiguous subarray using a cumulative sum approach, similar to Kadane's algorithm, but also tracks the start and end indices of the subarray that yields this maximum sum. It iterates through the array, updating the cumulative sum and keeping track of the minimum cumulative sum encountered so far. Whenever a larger sum is found, it updates the maximum sum and stores the indices of the subarray. Finally, the program prints both the maximum sum and the elements of the subarray that produce this sum.
Code:
#include <iostream>
#include <climits>
using namespace std;
void max_subarray_sum(int arr[], int n) {
int max_sum = INT_MIN; // Store the maximum sum
int cum_sum = 0; // Track the running cumulative sum
int min_sum = 0; // Track the minimum cumulative sum encountered so far
// To store the starting and ending indices of the subarray with the maximum sum
int start = 0, end = 0, temp_start = 0;
for (int i = 0; i < n; i++) {
cum_sum += arr[i]; // Update the cumulative sum
// Check if the current subarray gives a larger sum
if (cum_sum - min_sum > max_sum) {
max_sum = cum_sum - min_sum;
start = temp_start;
end = i;
}
// Update the minimum cumulative sum and potential start of the subarray
if (cum_sum < min_sum) {
min_sum = cum_sum;
temp_start = i + 1;
}
}
// Print the result
cout << "The maximum sum of a contiguous subarray is: " << max_sum << endl;
cout << "The subarray with the maximum sum is: ";
for (int i = start; i <= end; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int *arr = new int[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
max_subarray_sum(arr, n);
delete[] arr;
return 0;
}
Output:
5. Count Frequency of Each Element in O(n) Time Without Extra Space
The program counts the frequency of each element in the array by modifying the array itself. It uses the value of each element to index into the array and marks the frequency by adding n to the value at the corresponding index. After processing the entire array, the frequency of each element is obtained by dividing the value at each index by n. Finally, the program restores the array to its original state. This approach runs in O(n) time and uses O(1) extra space.
Code:
#include <iostream>
using namespace std;
//Function to count frequencies of each element in array
void count_frequencies(int arr[], int n) {
for (int i = 0; i < n; i++) {
// Get the index of the current element, assuming elements are in the range [0, n-1]
int index = arr[i] % n; // Use modulo to avoid out-of-bound access
// Increment the value at the calculated index by n
arr[index] += n;
}
for (int i = 0; i < n; i++) {
// The frequency of the element at index 'i' is the number of times n has been added
cout << "Element " << i << " appears " << arr[i] / n << " times." << endl;
}
for (int i = 0; i < n; i++) {
arr[i] = arr[i] % n; // Restore the original array values
}
}
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int *arr = new int[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
count_frequencies(arr, n);
delete[] arr;
return 0;
}
Output:
Day 6 was a deep dive into advanced array manipulation, where I tackled problems that required optimizing both time and space. The challenges, especially those focused on in-place modifications and efficiently counting frequencies, really tested my problem-solving skills and made me think outside the box. It’s been a great experience pushing the boundaries of what can be achieved without extra space or complex data structures.
Looking forward to what Day 7 has in store! 🚀