Consider a situation, problem where you need to find a pair of numbers whose sum can give you a target number.
like, x+y = target
Here, you need to find x,y from array, list, vector or any other sequential data structure, where array is sorted.
Brute-force Approach
- Take one element and add it with another element.
- Do this until sum of these elements is equal to target. therefore, in worst case it will take
Time Complexity - O(n^2)
Two Pointer Method
- Take two variables
start
andend
. - Point
start
towards first element of array. - Point
end
towards last element of array. - Now let's put a while loop till we get desired result,
condition -
start + end == target
. - If
start + end > target
we will shiftend
leftwards. - If
start + end < target
we will shiftstart
rightwards.
Thus by using this technique we can solve this problem in
Time Complexity - O(n)
// Program to get two numbers from array whose sum is equal to target element.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a[10] = {1, 4, 6, 8, 9, 12, 14, 16, 17};
int target = 20, start = 0, end = 8;
while ((a[start] + a[end] != target) && (start < end))
{
if (a[start] + a[end] > target)
{
end--;
}
else
{
start++;
}
}
cout << "Two numbers are: " << a[start] << ", " << a[end] << endl;
return 0;
}
// Code contributed by Kunal Agrawal
Thanks for reading this article.
Have a great day! π
Top comments (0)