02/11/2020 Sum of Three Values - Coderust: Hacking the Coding Interview
Sum of Three Values
Given an array of integers and a value, determine if there are any three integers in the
array whose sum equals the given value.
We'll cover the following
• Description
• Hints
• Try it yourself
• Solution 1
• Runtime complexity
• Memory complexity
• Solution 2
• Runtime complexity
• Memory complexity
• Solution 3
• Runtime complexity
• Memory complexity
Description #
Given an array of integers and a value, determine if there are any three
integers in the array whose sum equals the given value.
Consider this array and the target sums:
3 7 1 2 8 4 5
https://www.educative.io/courses/coderust-hacking-the-coding-interview/k6Xx 1/7
02/11/2020 Sum of Three Values - Coderust: Hacking the Coding Interview
Target Sum 20 5 + 7 + 8 = 20
Target Sum 21 No 3 values sum upto 21
Hints #
Sort data
Iterate from both ends
Try it yourself #
C++ Java Python JS Ruby
bool find_sum_of_three(vector<int> arr,
int required_sum) {
// TODO: Write - Your - Code
return false;
}
Solution 1 #
Runtime complexity #
The runtime complexity of this solution is cubic, O(n3 ).
Memory complexity #
The memory complexity of this solution is constant, O(1).
The simple and naive solution is to have three nested loops iterate over all
unordered triples to see if their sum is equal to the given integer or not.
Although this works, it is not efficient. The second and third solutions
have much better time complexities.
https://www.educative.io/courses/coderust-hacking-the-coding-interview/k6Xx 2/7
02/11/2020 Sum of Three Values - Coderust: Hacking the Coding Interview
C++ Java Python JS Ruby
bool find_sum_of_three(vector<int> arr, int required_sum) {
for (int i = 0; i < arr.size() - 2; ++i) {
for (int j = i+1; j < arr.size() - 1; ++j) {
for (int k = j+1; k < arr.size(); ++k) {
//i,j and k are indices to cater the scenario in which same array element
if ((i != j) && (j != k) && (k != i)) {
int sum = arr[i] + arr[j] + arr[k];
if (sum == required_sum) {
return true;
}
}
}
}
}
return false;
}
int main(){
vector<int> arr = {3, 7, 1, 2, 8, 4, 5};
cout << "Original array: ";
for (auto i:arr)
cout << i << " ";
cout << "\nSum 20 exists " << find_sum_of_three(arr, 20) << endl;
cout << "Sum 10 exists " << find_sum_of_three(arr, 10) << endl;
cout << "Sum 21 exists " << find_sum_of_three(arr, 21) << endl;
}
Solution 2 #
Runtime complexity #
The runtime complexity of this solution is O(n2 logn).
Memory complexity #
The memory complexity of this solution is constant, O(1).
This solution is also simple. We first sort the input array in O(nlogn)
time.
https://www.educative.io/courses/coderust-hacking-the-coding-interview/k6Xx 3/7
02/11/2020 Sum of Three Values - Coderust: Hacking the Coding Interview
Then we iterate over each pair (a, b) in the array in a nested loop and
calculate the remaining sum (sum - (a + b)) . We try to find the
remaining sum in the array using binary search. If we find it, we have
found the solution, with the three numbers being (a, b) and (sum -
(a+b)) .
C++ Java Python JS Ruby
vector<int>::iterator find_fast(vector<int>& v, int key) {
vector<int>::iterator low = std::lower_bound (v.begin(), v.end(), key);
if (low == v.end() || *low != key) {
return v.end();
}
return low;
}
bool find_sum_of_three(vector<int> arr, int required_sum) {
std::sort(arr.begin(), arr.end());
for (int i = 0; i < arr.size()-2; ++i) {
for (int j = i+1; j < arr.size()-1; ++j) {
// Looking for required_sum = arr[i] + arr[j] + arr[k]
int remaining_sum = required_sum - arr[i] - arr[j];
auto iter = find_fast(arr, remaining_sum);
if (iter != arr.end()) {
int k = std::distance(arr.begin(), iter);
if (k != i && k != j) {
return true;
}
}
}
}
return false;
}
int main(){
vector<int> arr = {3, 7, 1, 2, 8, 4, 5};
cout << "Original array: ";
for (auto i:arr)
cout << i << " ";
cout << "\nSum 20 exists " << find_sum_of_three(arr, 20) << endl;
cout << "Sum 10 exists " << find_sum_of_three(arr, 10) << endl;
cout << "Sum 21 exists " << find_sum_of_three(arr, 21) << endl;
}
Solution 3 #
https://www.educative.io/courses/coderust-hacking-the-coding-interview/k6Xx 4/7
02/11/2020 Sum of Three Values - Coderust: Hacking the Coding Interview
Runtime complexity #
The runtime complexity of this solution is quadratic, O(n2 ).
Memory complexity #
The memory complexity of this solution is constant, O(1).
To understand this solution better, we recommend taking a look at “Sum
of Two Values”.
In this solution, we first sort the array. Then we fix one element e , and try
to find a pair (a, b) in the remaining array such that required_sum - e =
a + b.
We start with the first element e in the array (at index i = 0) and try to
find such a pair (a, b) in the remaining array (i.e., A[i + 1] to A[n - 1] )
that satisfies the condition: a+b = required_sum - e . We can find such a
pair in linear time. If we find such a pair, we have found the solution: a, b
and e and thus, we can stop the iteration. Otherwise, we repeat the above
steps for all elements e at index i = 1 to n - 3 , until we find a pair that
meets the condition.
Let’s see how this algorithm works for the above example:
Initial State
3 7 1 2 8 4 5
Value 20
Remaining Sum
1 of 8
Additional Thoughts:
https://www.educative.io/courses/coderust-hacking-the-coding-interview/k6Xx 5/7
02/11/2020 Sum of Three Values - Coderust: Hacking the Coding Interview
By sorting the array, we have to change the input array itself. If we are not
allowed to modify the input array, then we can use a hash table to achieve
the same time complexity (see the first solution of Sum of Two Values
problem). However, this will require O(n) of extra memory.
Another alternative approach is to create a copy of the input array and
sort that rather than sorting the original.
C++ Java Python JS Ruby
bool find_sum_of_two(vector<int>& A, int val, size_t start_index) {
for (int i = start_index, j = A.size() - 1; i < j;) {
int sum = A[i] + A[j];
if (sum == val) {
return true;
}
if (sum < val) {
++i;
} else {
--j;
}
}
return false;
}
bool find_sum_of_three(vector<int> arr, int required_sum) {
std::sort(arr.begin(), arr.end());
for (int i = 0; i < arr.size() - 2; ++i) {
int remaining_sum = required_sum - arr[i];
if (find_sum_of_two(arr, remaining_sum, i + 1)) {
return true;
}
}
return false;
}
int main(){
vector<int> arr = {3, 7, 1, 2, 8, 4, 5};
cout << "Original array: ";
for (auto i:arr)
cout << i << " ";
cout << "\nSum 20 exists " << find_sum_of_three(arr, 20) << endl;
cout << "Sum 10 exists " << find_sum_of_three(arr, 10) << endl;
cout << "Sum 21 exists " << find_sum_of_three(arr, 21) << endl;
}
https://www.educative.io/courses/coderust-hacking-the-coding-interview/k6Xx 6/7
02/11/2020 Sum of Three Values - Coderust: Hacking the Coding Interview
Back Next
Levenshtein Distance Make Columns and Rows Zeros
Mark as Completed
23% completed, meet the criteria and claim your course certi cate!
Buy Certificate
Ask a Question
Report an
(https://discuss.educative.io/tag/sum-of-three-values__miscellaneous__coderust-
Issue
hacking-the-coding-interview)
https://www.educative.io/courses/coderust-hacking-the-coding-interview/k6Xx 7/7
