Table of contents
- Q1. Write a program to rotate an array of size n by k steps to the right in O(n) time without using extra space.
- Q2. 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.
- Q3. 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.
- Q4. Write a program to find the contiguous subarray with the maximum sum in O(n) time.
- Q5. 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).
Today’s practice focused on solving array manipulation problems with a variety of techniques. I worked on challenges like rotating an array by a given number of steps, finding the missing number in a range, rearranging an array with alternating largest and smallest elements, finding the maximum sum subarray, and counting element frequencies efficiently without extra space. Each problem helped me strengthen my understanding of arrays, providing me with useful methods for optimization and efficiency.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. 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 <iostream>
using namespace std;
void reverse(int arr[], int start, int end){ // Function to reverse the array from start to end indices
while(start<end){
swap(arr[start],arr[end]); // Swap elements at the start and end indices
start++;
end--;
}
}
void rotate_array(int arr[],int n,int k){ // Function to rotate array elements by k positions
if(k>n){ // If k is greater than the array length, take the modulo
k=k%n;
}
reverse(arr,n-k,n-1); // Reverse the last k elements
reverse(arr,0,n-k-1); // Reverse the first n-k elements
reverse(arr,0,n-1); // Reverse the whole array to get the final rotated array
cout<<"The shifted array is: ";
for(int i=0;i<n;i++){
cout<<arr[i];
}
}
int main()
{
int n,k;
cout<<"Enter length of array: ";
cin>>n;
int arr[n];
cout<<"Enter elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<"Enter how many positions you want to shift it by?: ";
cin>>k;
rotate_array(arr,n,k);
return 0;
}
This program rotates an array by k positions to the right. The reverse function reverses the order of elements in a given segment of the array. The rotate_array function works by first reversing the last k elements, then reversing the first n-k elements, and finally reversing the entire array. This series of reversals effectively shifts the array elements to the right by k positions. The input consists of the array and the number of positions to shift, and the rotated array is displayed as output.
Q2. 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.
// Q. 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 <iostream>
using namespace std;
void find_missing_no(int arr[],int n){
int sumofn=(n+1)*(n+2)/2; //calculating sum of the range n natural nos
int sumofarray=0;
for(int i=0;i<n;i++){ //calculating the sum of the elements of the array
sumofarray+=arr[i];
}
cout<<"The missing no is: "<<sumofn-sumofarray; //subtracting both sums to obtain the missing no.
}
int main()
{
int n;
cout<<"Enter length of array: ";
cin>>n;
int arr[n];
cout<<"Enter elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
find_missing_no(arr,n);
return 0;
}
This program finds the missing number in an array containing n-1 distinct integers within the range of 1 to n. The approach used is based on the mathematical formula for the sum of the first n natural numbers, which is (n*(n+1))/2. The program calculates the expected sum of the numbers from 1 to n and subtracts the sum of the elements present in the array. The difference between the expected sum and the actual sum gives the missing number. The input consists of the length of the array and its elements, and the missing number is displayed as output. This solution runs in O(n) time due to the summing operation.
Q3. 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.
// Q. 3. 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 <iostream>
using namespace std;
#include <algorithm>
void rearrange_array(int arr[], int n) {
int end = n-1; // Pointer to track the largest element
int start = 0; // Pointer to track the smallest element
int maxe = arr[n-1]+1; // A number greater than the largest element to use for encoding
// Traverse the array and encode values
for (int i=0;i<n;i++) {
if (i%2==0) {
// Place the largest element
arr[i] += (arr[end] % maxe) * maxe;
end--;
} else {
// Place the smallest element
arr[i] += (arr[start] % maxe) * maxe;
start++;
}
}
// Decode the array to retrieve final values
for (int i=0;i<n;i++) {
arr[i]/= maxe;
}
cout<<"The rearranged array is:";
for(int i=0;i<n;i++){
cout<<arr[i];
}
}
int main() {
int n;
cout << "Enter the length of the array: ";
cin >> n;
int arr[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);
return 0;
}
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 approach uses two pointers, start for the smallest element and end for the largest element. A number maxe greater than the largest element is chosen to encode values without using extra space. During the traversal of the array, the largest and smallest elements are placed alternately by encoding their values using the formula arr[i] += (arr[end] % maxe) * maxe for the largest and arr[i] += (arr[start] % maxe) * maxe for the smallest. After encoding, the array is decoded by dividing each element by maxe to restore the actual values. The time complexity is O(n) as it only requires two passes over the array.
Q4. Write a program to find the contiguous subarray with the maximum sum in O(n) time.
#include <iostream>
using namespace std;
void max_sum_subarray(int arr[], int n) {
int max_sum = arr[0];
int current = arr[0];
int start = 0, end = 0;
int temp_start = 0;
for (int i = 1; i < n; i++) {
if (current + arr[i] < arr[i]) { // Check if adding the current element reduces the sum.
current = arr[i]; // Start a new subarray.
temp_start = i; // Update the temporary starting index.
} else {
current += arr[i]; // Otherwise, add the element to the current subarray sum.
}
// Update max_sum and the start/end indices if the current sum is greater than max_sum.
if (current > max_sum) {
max_sum = current;
start = temp_start;
end = i;
}
}
cout << "Max sum is: " << max_sum << endl;
cout << "The elements giving max sum are: ";
for (int j = start; j <= end; j++) {
cout << arr[j] << " ";
}
cout << endl;
}
int main() {
int n;
cout << "Enter length of array: ";
cin >> n;
int arr[n];
cout << "Enter elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
max_sum_subarray(arr, n);
return 0;
}
The program finds the contiguous subarray with the maximum sum by iterating through the array while maintaining two variables: the current sum of the subarray and the maximum sum encountered so far. Whenever the current sum becomes negative, it is reset to zero, essentially ignoring negative sums and starting fresh from the next element. This ensures that only subarrays with positive or zero sums are considered, allowing the algorithm to focus solely on finding the maximum possible sum. Additionally, the program tracks the start and end indices of the subarray that provides this maximum sum, ensuring that both the sum and the elements contributing to it are identified.
Q5. 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 <iostream>
using namespace std;
void count_frequency(int arr[], int n) {
// Iterate through the array and use element values as indices
for (int i = 0; i < n; i++) {
int index = arr[i] % (n + 1) - 1; // Map the value to an index
arr[index] += (n + 1); // Increment the value at the mapped index
}
// Display the frequency of each element
cout << "Element frequencies:" << endl;
for (int i = 0; i < n; i++) {
int freq = arr[i] / (n + 1); // Retrieve frequency
if (freq > 0) {
cout << (i + 1) << " appears " << freq << " times" << endl;
}
arr[i] %= (n + 1); // Restore the original values
}
}
int main() {
int n;
cout << "Enter the length of the array: ";
cin >> n;
int arr[n];
cout << "Enter the elements (positive integers): ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
count_frequency(arr, n);
return 0;
}
This code calculates the frequency of each element in an array in O(n)O(n) time by temporarily modifying the array values. Each element is treated as an index (adjusted using % (n + 1) - 1), and the value at that index is incremented by n+1n + 1 to store frequency information alongside the original values. The first loop updates the array to encode frequencies. The second loop decodes the frequency by dividing each value by n+1n + 1 and restores the original array by taking modulo n+1n + 1. This method avoids using extra space and is limited to arrays with positive integers in the range of the array length.
Today’s practice helped me dive deeper into array manipulation. Whether it was rotating the array, finding missing numbers, rearranging elements, or solving for maximum subarray sums, each problem added a new dimension to my problem-solving toolkit. I'm eager to continue enhancing my skills in array operations and tackle even more advanced challenges. Onward to Day 8!