Question

Consider the problem of finding if an array contains a pair of integers with a sum of 100. The array contains n integers.

a. Define the signature (header) of a C++ function that solves this problem (hint: inputs/outputs of function)

b. Write the pseudocode or C++ body of the function (extra credit: write the most efficient algorithm)

c. What is the asymptotic complexity of your algorithm?

d. What would be the complexity of the best algorithm for this problem if the array were sorted?

Answer 1

a) bool check_sum(int arr[],int n,int sum);

Return value = bool

True: if pair with sum 100 exists

False:: otherwise

Input: arr[] of integers

n: size of array

sum : sum = 100 value to be obtained

b)

Code:

#include<bits/stdc++.h>
using namespace std;

bool check_sum(int arr[],int n,int sum){
        map <int,int> mp; // use a map
        for(int i=0;i<n;i++){
                int complement = sum - arr[i];
                if(mp.find(complement)!=mp.end()){ 
                        return true; // sum exists so return true
                }
                mp[arr[i]] = 1; // put value to map
        }
        return false;
}

int main() {
        int n = 5; //size of array
        int arr[] = {80,10,20,10,5};
        
        bool res = check_sum(arr,n,100);
        if(res == true){
                cout<<"A pair with sum = 100 exists";
        } else{
                cout<<"Pair with Sum = 100 doesn't exist";
        }
        
        return 0;
}

Code Screenshot:

Code output:

========================

c) The algorithm traverses through array once and uses a map to find if pair exists.

Time: O(n)

Space: O(n)

=========================

d) If the array was sorted we can use a two pointer approach to find if the sum exists or not.

Time: O(n)

Space : O(1)

===========================