Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Find Two Numbers that Add up to "s"

Explore various strategies to solve the problem of finding two numbers in an array that add up to a given sum s. Learn to implement brute force, sorting-based two-pointer techniques, binary search, and efficient hashing. Understand the time complexities of each approach to choose the most suitable algorithm for coding interviews.

We'll cover the following...

Solution #1: Brute Force #

C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> findSum(int arr[], int arrSize, int s) {
  vector<int> elements;
  for (int i = 0; i < arrSize; i++) {
    for (int j = i + 1; j < arrSize; j++) {
      if (arr[i] + arr[j] == s) {
        elements.push_back(arr[i]);
        elements.push_back(arr[j]);
      }
    }
  }
  return elements;
}
int main() {
  int arr[] = {8,4,1,6,5,9};
  int sum = 14;
  vector<int> result = findSum(arr, 6, sum);
  if(!result.empty())
    cout << "Sum of " << sum << " found: " << result[0] << " " << result[1];
  else
    cout << "Results not found" << endl;
}

This is the most time-intensive but intuitive solution. It is a lot like a modified version of a linear search. The whole array is traversed for each element and checked for any two elements that add up to the given number s. If they are found, we print them out. To do all of the above, we use a nested for-loop and iterate over the entire array for each element

Time Complexity

Since we iterate over the entire array (size nn) nn times, the time complexity is O(n2)O(n^2) ...