C++ array questions
Arrays
Find a pair with the given sum in an array
#include <iostream>
#include <algorithm>
using namespace std;
// Function to find a pair in an array with a given sum using sorting
void findPair(int arr[], int n, int sum)
{
// sort the array in ascending order
sort(arr, arr + n);
// maintain two indices pointing to endpoints of the array
int low = 0;
int high = n - 1;
// reduce the search space `arr[low…high]` at each iteration of the loop
// loop till the search space is exhausted
while (low < high)
{ // sum found
if (arr[low] + arr[high] == sum)
{
cout << "Pair found (" << arr[low] << ", " << arr[high] << ")" << endl;
return;
}
// increment `low` index if the total is less than the desired sum;
// decrement `high` index if the total is more than the desired sum
(arr[low] + arr[high] < sum)? low++: high--;
}
cout << "Pair not found";
}
int main()
{
int arr[] = { 8, 7, 2, 5, 3, 1 };
int sum = 10;
int n = sizeof(arr)/sizeof(arr[0]);
findPair(arr, n, sum);
return 0;
}
pair found (2,8)
Check if a subarray with 0 sum exists or not
#include <iostream>
#include <unordered_set>
using namespace std;
// Function to check if subarray with zero-sum is present in a given array or not
bool hasZeroSumSubarray(int A[], int n)
{
// create an empty set to store the sum of elements of each
// subarray `A[0…i]`, where `0 <= i < n`
unordered_set<int> set;
// insert 0 into the set to handle the case when subarray with
// zero-sum starts from index 0
set.insert(0);
int sum = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// sum of elements so far
sum += A[i];
// if the sum is seen before, we have found a subarray with zero-sum
if (set.find(sum) != set.end()) {
return true;
}
else {
// insert sum so far into the set
set.insert(sum);
}
}
// we reach here when no subarray with zero-sum exists
return false;
}
int main()
{ int A[] = { 4, 2, -3, -1, 0, 4 };
int n = sizeof(A)/sizeof(A[0]);
hasZeroSumSubarray(A, n) ?
cout << "Subarray exists":
cout << "Subarray does not exist";
return 0;
}
Output:
Subarray exists
Print all subarrays with 0 sum
#include <iostream>
#include <unordered_map>
using namespace std;
// Function to print all subarrays with a zero-sum
// in a given array
void printAllSubarrays(int arr[], int n)
{
// consider all subarrays starting from `i`
for (int i = 0; i < n; i++)
{
int sum = 0;
// consider all subarrays ending at `j`
for (int j = i; j < n; j++)
{ // sum of elements so far
sum += arr[j];
// if the sum is seen before, we have found a subarray
// with zero-sum
if (sum == 0) {
cout << "Subarray [" << i << "…" << j << "]\n";
}
}
}
}
int main()
{
int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
int n = sizeof(arr)/sizeof(arr[0]);
printAllSubarrays(arr, n);
return 0;
}
Output:
Subarray [0…2]
Subarray [0…9]
Subarray [1…3]
Subarray [2…5]
Subarray [3…9]
Subarray [5…. ]
Sort binary array in linear time
#include <stdio.h>
// Function to sort a binary array in linear time
int sort(int A[], int n)
{
// `k` stores index of next available position
int k = 0;
// do for each element
for (int i = 0; i < n; i++)
{
// if the current element is zero, put 0 at the next free
// position in the array
if (A[i] == 0) {
A[k++] = 0;
}
}
// fill all remaining indices by 1
for (int i = k; i < n; i++) {
A[k++] = 1;
}
}
int main(void)
{
int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 };
int n = sizeof(A)/sizeof(A[0]);
sort(A, n);
// print the rearranged array
for (int i = 0; i < n; i++) {
printf("%d ", A[i]);
}
return 0;
}
Output:
0 0 0 0 0 0 1 1 1 1
Find the duplicate element in a limited range array
#include <iostream>
using namespace std;
// Function to find a duplicate element in a limited range array
int findDuplicate(int arr[], int n)
{
// create a visited array of size `n+1`
// we can also use a map instead of a visited array
bool visited[n];
fill(visited, visited + n, 0); // sets every value in the array to 0
// mark each array element as visited and
// return it if seen before
for (int i = 0; i < n; i++)
{
// if the element is seen before
if (visited[arr[i]]) {
return arr[i];
}
// mark element as visited
visited[arr[i]] = true;
}
// no duplicate found
return -1;
}
int main()
{
// input array contains `n` numbers between 1 and `n-1`
// with one duplicate
int arr[] = { 1, 2, 3, 4, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The duplicate element is " << findDuplicate(arr, n);
return 0;
}
L
Output:
The duplicate element is 4
Find the largest subarray formed by consecutive integers
#include <iostream>
#include <vector>
using namespace std;
// Function to check if subarray `A[i…j]` is formed by consecutive integers.
// Here, `min` and `max` denote the minimum and maximum element in the subarray.
bool isConsecutive(int A[], int i, int j, int min, int max)
{
// for an array to contain consecutive integers, the difference
// between the maximum and minimum element in it should be exactly `j-i`
if (max - min != j - i) {
return false;
}
// create a visited array (we can also use a set)
vector<bool> visited(j - i + 1);
// traverse the subarray and check if each element appears only once
for (int k = i; k <= j; k++)
{
// if the element is seen before, return false
if (visited[A[k] - min]) {
return false;
}
// mark the element as seen
visited[A[k] - min] = true;
}
// we reach here when all elements in the array are distinct
return true;
}
// Find the largest subarray formed by consecutive integers
void findMaxSubarray(int A[], int n)
{
int len = 1;
int start = 0, end = 0;
// consider each subarray formed by `A[i…j]`
// `i` denotes the beginning of the subarray
for (int i = 0; i < n - 1; i++)
{
// stores the minimum and maximum element in subarray `A[i…j]`
int min_val = A[i], max_val = A[i];
// `j` denotes the end of the subarray
for (int j = i + 1; j < n; j++)
{
// update the minimum and maximum elements of the subarray
min_val = min(min_val, A[j]);
max_val = max(max_val, A[j]);
// check if subarray `A[i…j]` is formed by consecutive integers
if (isConsecutive(A, i, j, min_val, max_val))
{
if (len < max_val - min_val + 1)
{
len = max_val - min_val + 1,
start = i, end = j;
}
}
}
}
// print the maximum length subarray
cout << "The largest subarray is [" << start << ", " << end << "]";
}
int main()
{
int A[] = { 2, 0, 2, 1, 4, 3, 1, 0 };
int n = sizeof(A) / sizeof(A[0]);
findMaxSubarray(A, n);
return 0;
}
Output:
The largest subarray is [1, 5]
Find the largest subarray having an equal number of 0’s and 1’s
Given a binary array containing 0’s and 1’s, find the largest subarray with equal numbers of 0’s and 1’s.
#include <iostream>
#include <unordered_map>
using namespace std;
// Function to find the largest subarray having an equal number
// of 0's and 1's
void findLargestSubarray(int arr[], int n)
{
// create an empty map to store the ending index of the first subarray
// having some sum
unordered_map<int, int> map;
// insert `(0, -1)` pair into the set to handle the case when a
// subarray with zero-sum starts from index 0
map[0] = -1;
// `len` stores the maximum length of subarray with zero-sum
int len = 0;
// stores ending index of the largest subarray having zero-sum
int ending_index = -1;
int sum = 0;
// Traverse through the given array
for (int i = 0; i < n; i++)
{
// sum of elements so far (replace 0 with -1)
sum += (arr[i] == 0)? -1 : 1;
// if the sum is seen before
if (map.find(sum) != map.end())
{
// update length and ending index of largest subarray having zero-sum
if (len < i - map[sum])
{
len = i - map[sum];
ending_index = i;
}
}
// if the sum is seen for the first time, insert the sum with its
// index into the map
else {
map[sum] = i;
}
}
// print the subarray if present
if (ending_index != -1) {
cout << "[" << ending_index - len + 1 << ", " << ending_index << "]";
}
else {
cout << "No subarray exists";
}
}
int main()
{
int arr[] = { 0, 0, 1, 0, 1, 0, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
findLargestSubarray(arr, n);
return 0;
}
Output:
[1, 4]
Sort an array of 0’s, 1’s, and 2’s (Dutch National Flag Problem)
#include <stdio.h>
// Utility function to swap elements `A[i]` and `A[j]` in an array
void swap(int A[], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// Linear time partition routine to sort an array containing 0, 1, and 2.
// It is similar to 3–way partitioning for the Dutch national flag problem.
void threeWayPartition(int A[], int end)
{
int start = 0, mid = 0;
int pivot = 1;
while (mid <= end)
{
if (A[mid] < pivot) // current element is 0
{
swap(A, start, mid);
++start, ++mid;
}
else if (A[mid] > pivot) // current element is 2
{
swap(A, mid, end);
--end;
}
else { // current element is 1
++mid;
}
}
}
int main()
{
int A[] = { 0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0 };
int n = sizeof(A)/sizeof(A[0]);
threeWayPartition(A, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", A[i]);
}
return 0;
}
Output:
0 0 0 0 0 1 1 1 1 2 2 2
In-place merge two sorted arrays
Given two sorted arrays, X[] and Y[] of size m and n each, merge elements of X[] with elements of array Y[] by maintaining the sorted order, i.e., fill X[] with the first m smallest elements and fill Y[] with remaining elements.
#include <iostream>
#include <algorithm>
using namespace std;
// Utility function to print contents of an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
// Function to in-place merge two sorted arrays X[] and Y[]
// invariant: `X[]` and `Y[]` are sorted at any point
void merge(int X[], int Y[], int m, int n)
{
// Consider each element `X[i]` of array `X` and ignore the element if it is
// already in the correct order; otherwise, swap it with the next smaller
// element, which happens to be the first element of `Y`.
for (int i = 0; i < m; i++)
{
// compare the current element of `X[]` with the first element of `Y[]`
if (X[i] > Y[0])
{
swap(X[i], Y[0]);
int first = Y[0];
// move `Y[0]` to its correct position to maintain the sorted
// order of `Y[]`. Note: `Y[1…n-1]` is already sorted
int k;
for (k = 1; k < n && Y[k] < first; k++) {
Y[k - 1] = Y[k];
}
Y[k - 1] = first;
}
}
}
int main()
{
int X[] = { 1, 4, 7, 8, 10 };
int Y[] = { 2, 3, 9 };
int m = sizeof(X) / sizeof(X[0]);
int n = sizeof(Y) / sizeof(Y[0]);
merge(X, Y, m, n);
cout << "X: "; printArray(X, m);
cout << "Y: "; printArray(Y, n);
return 0;
}
Print continuous subarray with maximum sum
#include <iostream>
#include <climits>
using namespace std;
// Function to print contiguous subarray with the largest sum
// in a given set of integers
void kadane(int arr[], int n)
{
// base case
if (n <= 0) {
return;
}
// stores maximum sum subarray found so far
int max_so_far = INT_MIN;
// stores the maximum sum of subarray ending at the current position
int max_ending_here = 0;
// stores endpoints of maximum sum subarray found so far
int start = 0, end = 0;
// stores starting index of a positive-sum sequence
int beg = 0;
// traverse the given array
for (int i = 0; i < n; i++)
{
// update the maximum sum of subarray "ending" at index `i`
max_ending_here = max_ending_here + arr[i];
// if the maximum sum becomes less than the current element,
// start from the current element
if (max_ending_here < arr[i])
{
max_ending_here = arr[i];
beg = i;
}
// update result if the current subarray sum is found to be greater
if (max_so_far < max_ending_here)
{
max so_far = max_ending_here;
start = beg;
end = i;
}
}
cout << "The contiguous subarray with the largest sum is ";
for (int i = start; i <= end; i++) {
cout << arr[i] << " ";
}
}
int main()
{
int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int n = sizeof(arr)/sizeof(arr[0]);
kadane(arr, n);
return 0;
}
Output:
The contiguous subarray with the largest sum is 4 -1 2 1
Find all distinct combinations of a given length with repetition allowed
Given an integer array, find all distinct combinations of a given length k, where the repetition of elements is allowed
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to print the contents of the vector
void printVector(vector<int> const &out)
{
for (auto it = out.begin(); it != out.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
// Function to print all distinct combinations of length `k`, where the
// repetition of elements is allowed
void findCombinations(int arr[], vector<int> &out, int k, int i, int n)
{
// base case: if the combination size is `k`, print it
if (out.size() == k)
{
printVector(out);
return;
}
// start from the previous element in the current combination
// till the last element
for (int j = i; j < n; j++)
{
// add current element `arr[j]` to the solution and recur with the
// same index `j` (as repeated elements are allowed in combinations)
out.push_back(arr[j]);
findCombinations(arr, out, k, j, n);
// backtrack: remove the current element from the solution
out.pop_back();
// code to handle duplicates – skip adjacent duplicates
while (j < n - 1 && arr[j] == arr[j + 1]) {
j++;
}
}
}
int main()
{
int arr[] = { 1, 2, 1 };
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
// if the array contains repeated elements, sort the array to
// handle duplicates combinations
sort (arr, arr + n);
vector<int> out;
findCombinations(arr, out, k, 0, n);
return 0;
}
Output:
1 1
1 2
2 2
Find a subarray having the given sum in an integer array
#include <stdio.h>
// Function to print subarray having a given sum using
// sliding window technique
void findSubarray(int arr[], int n, int sum)
{
// maintains the sum of the current window
int windowSum = 0;
// maintain a window `[low, high-1]`
int low = 0, high = 0;
// consider every subarray starting from the `low` index
for (low = 0; low < n; low++)
{
// if the current window's sum is less than the given sum,
// then add elements to the current window from the right
while (windowSum < sum && high < n)
{
windowSum += arr[high];
high++;
}
// if the current window's sum is equal to the given sum
if (windowSum == sum)
{
printf("Subarray found [%d–%d]\n", low, high - 1);
return;
}
// At this point, the current window's sum is more than the given sum.
// Remove the current element (leftmost element) from the window
windowSum -= arr[low];
}
}
int main(void)
{
// an array of positive integers
int arr[] = { 2, 6, 0, 9, 7, 3, 1, 4, 1, 10 };
int sum = 15;
int n = sizeof(arr)/sizeof(arr[0]);
findSubarray(arr, n, sum);
return 0;
}
Output:
Subarray found [1–3]
Find the smallest window in an array sorting which will make the entire array sorted
#include <iostream>
#include <climits>
using namespace std;
// Function to find the smallest window in an array, sorting which will
// make the entire array sorted
void findSubarray(int arr[], int n)
{
int leftIndex = -1, rightIndex = -1;
// traverse from left to right and keep track of maximum so far
int max_so_far = INT_MIN;
for (int i = 0; i < n; i++)
{
if (max_so_far < arr[i]) {
max_so_far = arr[i];
}
// find the last position that is less than the maximum so far
if (arr[i] < max_so_far) {
rightIndex = i;
}
}
// traverse from right to left and keep track of the minimum so far
int min_so_far = INT_MAX;
for (int i = n - 1; i >= 0; i--)
{
if (min_so_far > arr[i]) {
min_so_far = arr[i];
}
// find the last position that is more than the minimum so far
if (arr[i] > min_so_far) {
leftIndex = i;
}
}
if (leftIndex == -1) {
cout << "Array is already sorted";
return;
}
cout << "Sort array from index " << leftIndex << " to " << rightIndex;
}
int main()
{
int arr[] = { 1, 3, 2, 7, 5, 6, 4, 8 };
int n = sizeof(arr)/sizeof(arr[0]);
findSubarray(arr, n);
return 0;
}
Output:
Sort array from index 1 to 6
Find maximum sum path involving elements of given arrays
#include <stdio.h>
// Utility function to find the minimum of two integers
int max (int x, int y) {
return (x > y) ? x : y;
}
// Function to find the maximum sum path in two given arrays.
// The code is similar to the merge routine of the merge sort algorithm
int findMaxSum(int X[], int Y[], int m, int n)
{
int sum = 0;
int sum_x = 0, sum_y = 0;
// `i` and `j` denotes the current index of `X` and `Y`, respectively
int i = 0, j = 0;
// loop till `X` and `Y` are empty
while (i < m && j < n)
{
// to handle the duplicate elements in `X`
while (i < m-1 && X[i] == X[i+1]) {
sum_x += X[i++];
}
// to handle the duplicate elements in `Y`
while (j < n-1 && Y[j] == Y[j+1]) {
sum_y += Y[j++];
}
// if the current element of `Y` is less than the current element of `X`
if (Y[j] < X[i])
{
sum_y += Y[j];
j++;
}
// if the current element of `X` is less than the current element of `Y`
else if (X[i] < Y[j])
{
sum_x += X[i];
i++;
}
else // if (X[i] == Y[j])
{
// consider the maximum sum and include the current cell's value
sum += max(sum_x, sum_y) + X[i];
// move both indices by 1 position
i++, j++;
// reset both sums
sum_x = 0, sum_y = 0;
}
}
// process the remaining elements of `X` (if any)
while (i < m) {
sum_x += X[i++];
}
// process the remaining elements of `Y` (if any)
while (j < n) {
sum_y += Y[j++];
}
sum += max(sum_x, sum_y);
return sum;
}
int main()
{
int X[] = { 3, 6, 7, 8, 10, 12, 15, 18, 100 };
int Y[] = { 1, 2, 3, 5, 7, 9, 10, 11, 15, 16, 18, 25, 50 };
int m = sizeof(X)/sizeof(X[0]);
int n = sizeof(Y)/sizeof(Y[0]);
printf("The maximum sum is %d", findMaxSum(X, Y, m, n));
return 0;
}
Output:
The maximum sum is 199
Hope you find the article useful. Make sure you share it.
