Four Sum

Given an array of integers, find all combination of four elements in the array whose sum is equal to a given value X.

Idea :
    1) Find all pair sum, requires O(n^2) space
    2) Sort the pair sum.
    3) Find the 4 elements(2 pairs) using the approach in two pair sum solution in O(n^2) time.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

#include <iostream> using namespace std; struct pairSum{ int sum, first, second; }; void findPairSum(int *arr, struct pairSum *temp, int n){ int k = 0; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ temp[k].sum = arr[i] + arr[j]; temp[k].first = arr[i]; temp[k].second = arr[j]; k++; } } } void merger(struct pairSum *arr, struct pairSum *temp, int low, int mid, int high){ int i = low, j = mid + 1, k = low; while(i <= mid && j <= high){ if(arr[i].sum <= arr[j].sum){ temp[k].sum = arr[i].sum; temp[k].first = arr[i].first; temp[k].second = arr[i].second; k++; i++; } else{ temp[k].sum = arr[j].sum; temp[k].first = arr[j].first; temp[k].second = arr[j].second; k++; j++; } } while(i <= mid){ temp[k].sum = arr[i].sum; temp[k].first = arr[i].first; temp[k].second = arr[i].second; k++; i++; } while(j <= high){ temp[k].sum = arr[j].sum; temp[k].first = arr[j].first; temp[k].second = arr[j].second; k++; j++; } for(int i = low; i<= high; i++){ arr[i].sum = temp[i].sum; arr[i].first = temp[i].first; arr[i].second = temp[i].second; } } void mergeSort(struct pairSum *arr, struct pairSum *temp, int low, int high){ if(low < high){ int mid = (low + high) / 2; mergeSort(arr, temp, low, mid); mergeSort(arr, temp, mid + 1, high); merger(arr, temp, low, mid, high); } } void find4Numbers(struct pairSum *arr, int sz, int x){ struct pairSum *sorted = new pairSum[sz]; int l = 0, r = sz - 1, sum; mergeSort(arr, sorted, 0, sz - 1); while(l < r){ sum = sorted[l].sum + sorted[r].sum; if(sum == x && (sorted[l].first != sorted[r].first && sorted[l].first != sorted[r].second && sorted[l].second != sorted[r].first && sorted[l].second != sorted[r].second)){ cout << "Four elements : " << sorted[l].first << ", " << sorted[l].second << ", " << sorted[r].first << ", " << sorted[r].second << endl; return; } else if(sum > x){ r--; } else{ l++; } } cout << "No 4 elements found!" << endl; return; } int main(){ int arr[] = {1, 4, 45, 6, 10, 12}; int x = 56; int n = sizeof(arr)/sizeof(arr[0]); int sz = n * (n - 1) / 2; struct pairSum *pairSums = new struct pairSum[sz]; findPairSum(arr, pairSums, n); find4Numbers(pairSums, sz, x); return 0; }

Read More

Largest Number

Given a list of non-negative integers, return the largest number that can be formed by their arrangement.

Eg. For the list [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Approach: We need sorting but in the modified way since if we have the number 9, 80 in the list then the largest number can be 980 but sorting will give 809. So, we modify sorting such that the for the pair(X, Y) in the list X comes first after sorting if XY > YX where XY represents concatenation of X and Y. Thus, for 9, 80, we will have the sorting result as 980 since 980 > 809.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

int myCompare(int a, int b){ string X = to_string(a); string Y = to_string(b); string XY = X.append(Y); string YX = Y.append(X); return XY.compare(YX) > 0 ? 1 : 0; } string Solution::largestNumber(const vector<int> &A) { vector<int> temp(A); string result = ""; int count = 0; for(int i = 0 ; i < A.size(); i++){ if(A[i] == 0){ count++; } } //handling all 0 vector if(count == A.size()){ result = "0"; return result; } //sort as per modified compare function sort(temp.begin(), temp.end(), myCompare); string out = ""; //make a string for the result for(int i = 0; i < A.size(); ++i){ result.append(to_string(temp[i])); } return result; }

Read More

3Sum Closest

Given an array A of n integers, find three integers in A such that the sum is closest to a given value. Return the sum of the three integers. You may assume that each input would have exactly one solution.
It is a modified version of the problem 3 Sum

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: int threeSumClosest(vector<int>& nums, int target) { //sort the vector sort(nums.begin(), nums.end()); int temp = 0, j, k, diff = INT_MAX, out = 0; for(int i = 0; i < nums.size(); i++){ j = i + 1; k = nums.size() - 1; while(j < k){ temp = nums[i] + nums[j] + nums[k]; //update the minimum diff till now and store the output if(abs(temp - target) < diff){ diff = abs(temp - target); out = temp; } //if diff is 0, return the output else increment or decrement based on the current (temp - target) value if(diff == 0){ return out; }else if(temp - target < 0){ j++; }else{ k--; } } } return out; } };

Read More

3Sum II

Given an array A of n integers, find all unique triplets in the array which gives the sum of zero.

The problem is a modification of the problem 3 Sum 

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> result; if(nums.size() < 3) return result; for(int i = 0; i < nums.size() - 2; i++){ if(i == 0 || nums[i] != nums[i - 1]){ int j = i + 1, k = nums.size() - 1; while(j < k){ //use the approach as for 2 Sum if(nums[i] + nums[j] + nums[k] == 0){ vector<int> three; three.push_back(nums[i]); three.push_back(nums[j]); three.push_back(nums[k]); result.push_back(three); j++; k--; // skip duplicates while(j < k && nums[j - 1] == nums[j]){ j++; } // skip duplicates while(j < k && nums[k + 1] == nums[k]){ k--; } } else if(nums[i] + nums[j] + nums[k] < 0){ j++; }else{ k--; } } } } return result; } };

Read More

3 Sum

Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false.

Approach:

    1) Sort the input array.

    2) Fix the first element as A[i] where i is from 0 to array size - 2. After fixing the first element of triplet, find the other two elements using the technique used in 2 Sum problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

#include <iostream> using namespace std; void merger(int *arr, int *temp, int low, int mid, int high){ int i, j, k; i = low; j = mid + 1; k = low; while(i <= mid && j <= high){ if(arr[i] <= arr[j]){ temp[k++] = arr[i++]; } else{ temp[k++] = arr[j++]; } } while(i <= mid){ temp[k++] = arr[i++]; } while(j <= high){ temp[k++] = arr[j++]; } for(int i = low; i <=high; i++){ arr[i] = temp[i]; } } void mergeSort(int *arr, int *temp, int low, int high){ if(low < high){ int mid = (low + high) / 2; mergeSort(arr, temp, low, mid); mergeSort(arr, temp, mid + 1, high); merger(arr, temp, low, mid, high); } } int find3Numbers(int *arr, int n, int sum){ int *temp = new int[n]; mergeSort(arr, temp, 0, n - 1); int curSum, left, right; for(int i = 0; i < n - 2; i++){ left = i + 1; right = n - 1; while(left < right){ curSum = arr[i] + arr[left] + arr[right]; if(curSum == sum){ cout << "Triplet : " << arr[i] << " " << arr[left] << " " << arr[right] << " " << endl; return 1; } else if(curSum < sum){ left++; } else{ right--; } } } return 0; } int main(){ int arr[] = {1, 4, 45, 6, 10, 8}; int sum = 51; int n = sizeof(arr)/sizeof(arr[0]); if(find3Numbers(arr, n, sum)){ ; } else{ cout << "No such triplet exists!" << endl; } return 0; }

Read More

Sort an array of 0s, 1s and 2s

Given an array A consisting 0s, 1s and 2s, write a function that sorts A. The functions should put all 0s first, then all 1s and all 2s in last.

Example:
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

Approach : Use the Dutch's flag algorithm given here. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <iostream> #include <cmath> using namespace std; void segregate(int *arr, int n){ int temp, low = 0, mid = 0, high = n - 1; while(mid <= high){ if(arr[mid] == 0){ temp = arr[low]; arr[low] = arr[mid]; arr[mid] = temp; mid++; low++; } else if(arr[mid] == 2){ temp = arr[high]; arr[high] = arr[mid]; arr[mid] = temp; mid; high--; } else { mid++; } } } int main(){ int arr[] = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}; int n = sizeof(arr)/sizeof(arr[0]); segregate(arr, n); for(int i = 0; i < n; i++){ cout << arr[i] << " "; } cout << endl; return 0; }

Read More

Two elements sum to x

Given an array of n numbers and another number x, determines whether or not there exist two elements in the array whose sum is exactly x.

Approach: Sort the array and use two pointers one at the start and the other at the end. Increment the start pointer if the sum is less than the target, decrement if the sum is greater else break out of the loop.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

/* To find the pair of elements in an array if the sum is equal to the given number */ #include<iostream> #include<algorithm> using namespace std; int main(){ int arr[6] = {1, 4, 45, 6, 10, -8}; int n = sizeof(arr) / sizeof(arr[0]); sort(arr, arr + n); int i = 0, j = n - 1, k = 16; int flag = 0; while(i < j){ if(arr[i] + arr[j] == k){ flag = 1; break; } else if(arr[i] + arr[j] > k){ j--; } else{ i++; } } if(flag){ cout << arr[i] << " + " << arr[j] << " add upto " << k << endl; } else{ cout << "No such pair exists" << endl; } return 0; }

Read More