QUESTION 1 Find a pair with the given sum in an array

For example,

Input: nums = [8, 7, 2, 5, 3, 1]target = 10

SOLUTION

#include <iostream>

#include <algorithm>

using namespace std;

// Function to find a pair in an array with a given sum using sorting

void findPair(int nums[], int n, int target)

// sort the array in ascending order

sort(nums, nums + n);

// maintain two indices pointing to endpoints of the array

int low = 0;

int high = n - 1;

// reduce the search space `nums[low…high]` at each iteration of the loop

// loop till the search space is exhausted

// sum found

if (nums[low] + nums[high] == target)

cout << "Pair found (" << nums[low] << ", " << nums[high] << ")\n";

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

(nums[low] + nums[high] < target)? low++: high--;

// we reach here if the pair is not found

cout << "Pair not found";

int main()

int nums[] = { 8, 7, 2, 5, 3, 1 };

int target = 10;

int n = sizeof(nums)/sizeof(nums[0]);
 findPair(nums, n, target);

return 0;

QUESTION 2

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 nums[], int n)

// create an empty set to store the sum of elements of each

// subarray `nums[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 += nums[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 nums[] = { 4, 2, -3, -1, 0, 4 };

int n = sizeof(nums)/sizeof(nums[0]);
 hasZeroSumSubarray(nums, n) ?

cout << "Subarray exists":

cout << "Subarray does not exist";

return 0;

QUESTION 3

FINDING THE EQUILIBRUM INDEX OF AN ARRAY

#include <iostream>

#include <numeric>

using namespace std;

// Optimized method to find the equilibrium index of an array

void findEquilibriumIndex(int A[], int n)

// `total` stores the sum of all the array elements

int total = accumulate(A, A + n, 0);

// `right` stores the sum of elements of subarray `A[i+1…n)`

int right = 0;

// traverse the array from right to left

/* `i` is an equilibrium index if the sum of elements of subarray `A[0…i-1]`

is equal to the sum of elements of the subarray `A[i+1…n)` i.e.

`(A[0] + A[1] + … + A[i-1])` = `(A[i+1] + A[i+2] + … + A[n-1])` */

// sum of elements of the left subarray `A[0…i-1]` is `total - (A[i] + right)`

if (right == total - (A[i] + right)) {

cout << "Equilibrium Index found " << i << endl;

// new right is `A[i] + (A[i+1] + A[i+2] + … + A[n-1])`

right += A[i];

int main()

int A[] = { 0, -3, 5, -4, -2, 3, 1, 0 };

int n = sizeof(A) / sizeof(A[0]);

findEquilibriumIndex(A, n);

return 0;

}
QUESTION 4

MAXIMUM PRODUCT SUBARRAY PROBLEM

#include <stdio.h>

// Utility function to find a minimum of two numbers

int min(int x, int y) {

return (x < y) ? x : y;

// Utility function to find a maximum of two numbers

int max(int x, int y) {

return (x > y) ? x : y;

// Function to return the maximum product of a subarray of a given array

int findMaxProduct(int arr[], int n)

// base case

if (n == 0) {

return 0;

// maintain two variables to store the maximum and minimum product

int max_ending = arr[0], min_ending = arr[0];

// to store the maximum product subarray found so far

int max_so_far = arr[0];

// traverse the given array

for (int i = 1; i < n; i++)

int temp = max_ending;

// update the maximum product ending at the current index

max_ending = max(arr[i], max(arr[i] * max_ending, arr[i] * min_ending));

// update the minimum product ending at the current index

min_ending = min(arr[i], min(arr[i] * temp, arr[i] * min_ending));

max_so_far = max(max_so_far, max_ending);

// return maximum product

return max_so_far;

int main(void)
{

int arr[] = { -6, 4, -5, 8, -10, 0, 8 };

int n = sizeof(arr) / sizeof(arr[0]);

printf("The maximum product of a subarray is %d",

findMaxProduct(arr, n));

return 0;

QUESTION 5

DECODE AN ARRAY CONSTRUCTED FROM AN ANOTHER ARRAY

#include <iostream>

#include <cmath>

using namespace std;

// Function to decode given array to get back the original array elements

void decode(int inp[], int m)

// base case

if (m == 0 || m == 2) {

return;

}
// calculate the size of the original array

int n = (sqrt(8*m + 1) + 1) / 2;

// create an auxiliary array of size `n` to store elements

// of the original array

int A[n];

// calculate the first element of the original array

if (n == 1 || m == 1) {

A[0] = inp[0];

else if (n == 2) {

A[0] = inp[0] - inp[1];

else {

A[0] = (inp[0] + inp[1] - inp[n - 1]) / 2;

// calculate the remaining elements of the original array using

// the first element

for (int i = 1; i < n; i++) {

A[i] = inp[i - 1] - A[0];

// print the original array

cout << A[i] << " ";

int main()

int inp[] = { 3, 4, 5, 6, 5, 6, 7, 7, 8, 9 };

int m = sizeof(inp)/sizeof(inp[0]);

decode(inp, m);

return 0;

QUESTION 6

FIND PAIRS WITH DIFFERENCE 'K' IN AN ARRAY

#include <iostream>

#include <unordered_set>

#include <algorithm>

using namespace std;

// Function to find a pair with the given difference in an array.

// This method does not handle duplicates in the array

// array is unsorted

// take an empty set

unordered_set<int> set;

// do for every array element

for (int i = 0; i < n; i++)

// check if pair with the given difference `(arr[i], arr[i]-diff)` exists

if (set.find(arr[i] - diff) != set.end()) {

cout << "(" << arr[i] << ", " << arr[i] - diff<< ")\n";

// check if pair with the given difference `(arr[i]+diff, arr[i])` exists

if (set.find(arr[i] + diff) != set.end()) {

cout << "(" << arr[i] + diff << ", " << arr[i] << ")\n";

// insert the current element into the set

set.insert(arr[i]);

}
int main()

int arr[] = { 1, 5, 2, 2, 2, 5, 5, 4};

int diff = 3;

int n = sizeof(arr) / sizeof(arr[0]);

findPair(arr, n, diff);

return 0;

QUESTION 7

Print all quadruplets with a given sum | 4 sum problem extended

#include <iostream>

#include <algorithm>

using namespace std;

// Function to print all quadruplet present in an array with a given sum

void quadTuple(int arr[], int n, int target)

// sort the array in ascending order

sort (arr, arr + n);

// subarray `arr[j+1…n)`

for (int i = 0; i <= n - 4; i++)

for (int j = i + 1; j <= n - 3; j++)

// `k` stores remaining sum

int k = target - (arr[i] + arr[j]);

// check for sum `k` in subarray `arr[j+1…n)`

int low = j + 1, high = n - 1;

while (low < high)

if (arr[low] + arr[high] < k) {

low++;

else if (arr[low] + arr[high] > k) {

high--;

// quadruplet with a given sum found

else {

cout << "(" << arr[i] << " " << arr[j] << " " <<
 arr[low] << " " << arr[high] << ")\n";

low++, high--;

int main()

int arr[] = { 2, 7, 4, 0, 9, 5, 1, 3 };

int target = 20;

int n = sizeof(arr) / sizeof(arr[0]);

quadTuple(arr, n, target);

return 0;

QUESTION 8

Generate random input from an array according to given probabilities

#include <vector>

#include <unordered_map>

#include <cstdlib>

#include <ctime>

using namespace std;

// Function to generate random nums from a vector according to the given probabilities

int random(vector<int> const &nums, vector<int> const &probability)

int n = nums.size();

if (n != probability.size()) {

return -1; // error

// construct a sum vector from the given probabilities

vector<int> prob_sum(n, 0);

// `prob_sum[i]` holds sum of all `probability[j]` for `0 <= j <=i`

prob_sum[0] = probability[0];

for (int i = 1; i < n; i++) {

prob_sum[i] = prob_sum.at(i-1) + probability[i];

// generate a random integer from 1 to 100 and check where it lies in `prob_sum[]`
 int r = (rand() % 100) + 1;

// based on the comparison result, return the corresponding

// element from the nums vector

if (r <= prob_sum[0]) { // handle 0th index separately

return nums[0];

for (int i = 1; i < n; i++)

if (r > prob_sum.at(i-1) && r <= prob_sum[i]) {

return nums[i];

int main()

// Input: vector of integers and their probabilities

// Goal: generate `nums[i]` with probability equal to `probability[i]`

vector<int> nums = {1, 2, 3, 4, 5};

vector<int> probability = {30, 10, 20, 15, 25};

srand(time(NULL));

// maintain a frequency map to validate the results

unordered_map<int, int> freq;

// make 1000000 calls to the `random()` function and

// store results in a map

for (int i = 0; i < 1000000; i++)

int val = random(nums, probability);

freq[val]++;

// print the results

for (int i = 0; i < nums.size(); i++) {

cout << nums[i] << " ~ " << freq[nums[i]]/10000.0 << "%" << endl;

return 0;

QUESTION 9

Matrix Chain Multiplication using Dynamic Programming

#include <vector>

#include <climits>

using namespace std;

// Function to find the most efficient way to multiply

// a given sequence of matrices

int matrixChainMultiplication(vector<int> const &dims, int i, int j)

// base case: one matrix

if (j <= i + 1) {

return 0;

// stores the minimum number of scalar multiplications (i.e., cost)

// needed to compute matrix `M[i+1] … M[j] = M[i…j]`

int min = INT_MAX;

// take the minimum over each possible position at which the

// sequence of matrices can be split

/*

(M[i+1]) × (M[i+2]………………M[j])

(M[i+1]M[i+2]) × (M[i+3…………M[j])
 …

(M[i+1]M[i+2]…………M[j-1]) × (M[j])

*/

for (int k = i + 1; k <= j - 1; k++)

// recur for `M[i+1]…M[k]` to get an `i × k` matrix

int cost = matrixChainMultiplication(dims, i, k);

// recur for `M[k+1]…M[j]` to get an `k × j` matrix

cost += matrixChainMultiplication(dims, k, j);

// cost to multiply two `i × k` and `k × j` matrix

cost += dims[i] * dims[k] * dims[j];

if (cost < min) {

min = cost;

// return the minimum cost to multiply `M[j+1]…M[j]`

return min;

}
// Matrix Chain Multiplication Problem

int main()

// Matrix `M[i]` has dimension `dims[i-1] × dims[i]` for `i=1…n`

// input is 10 × 30 matrix, 30 × 5 matrix, 5 × 60 matrix

vector<int> dims = { 10, 30, 5, 60 };

int n = dims.size();

cout << "The minimum cost is " << matrixChainMultiplication(dims, 0, n - 1);

return 0;

QUESTION 10

Iterative Merge Sort Algorithm (Bottom-up Merge Sort)

#include <stdio.h>

#include <time.h>

#include <stdlib.h>

#define N 10

// Utility function to find a minimum of two numbers

int min(int x, int y) {

return (x < y) ? x : y;
}

// Merge two sorted subarrays `A[from…mid]` and `A[mid+1…to]`

void merge(int A[], int temp[], int from, int mid, int to)

int k = from, i = from, j = mid + 1;

// loop till no elements are left in the left and right runs

while (i <= mid && j <= to)

if (A[i] < A[j]) {

temp[k++] = A[i++];

else {

temp[k++] = A[j++];

// copy remaining elements

while (i < N && i <= mid) {

temp[k++] = A[i++];

/* no need to copy the second half (since the remaining items

are already in their correct position in the temporary array) */

for (int i = from; i <= to; i++) {

A[i] = temp[i];

// Iteratively sort subarray `A[low…high]` using a temporary array

void mergesort(int A[], int temp[], int low, int high)

// divide the array into blocks of size `m`

// m = [1, 2, 4, 8, 16…]

for (int m = 1; m <= high - low; m = 2*m)

// for m = 1, i = 0, 2, 4, 6, 8…

// for m = 2, i = 0, 4, 8…

// for m = 4, i = 0, 8…

// …

for (int i = low; i < high; i += 2*m)

int from = i;

int mid = i + m - 1;

int to = min(i + 2*m - 1, high);

merge(A, temp, from, mid, to);

// Utility function to print a given array

int printArray(int A[])

for (int i = 0; i < N; i++) {

printf("%d ", A[i]);

printf("\n");

// Iterative implementation of merge sort

int main()

int A[N], temp[N];

srand(time(NULL));

// generate random input of integers

for (int i = 0; i < N; i++) {

temp[i] = A[i] = (rand() % 50);

}
 printf("Original array: ");

printArray(A);

// sort array `A[0…N-1]` using a temporary array temp

mergesort(A, temp, 0, N - 1);

printf("Modified array: ");

printArray(A);

return 0;