Question

Design and analyze asymptotically an O(nlgn) transform-conquer algorithm for the following problem:

1. • input: an array A[lo..hi] of n real values;
   • output: true iff the array contains two elements (at different indices) whose sum is 2020.

Answer 1

# This is a simple C++ solution to the following Problem.

Algorithm:

step1: for each element in array

         push occurance of each element in the dictionay

step2: Again for each element in array:

         if dictionay[2020-arrary_element] is in the dictionay

                  print index of the array element

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

int main() {
        unordered_map<int, int> m; // creating a dictionary
        
        int n; // array size
        cin>>n;
        vector<int> arr(n);
        
        // taking array input
        for(int i=0; i<n; i++)
        {
            cin>>arr[i];
        }
        
        // storing the occurrence of each element of array in dictionary
        for(int i=0; i<n; i++){
            m[arr[i]]++;
        }
        
        for(int i=0; i<n; i++){
            if (m[2020-arr[i]]){
                cout<<arr[i]<<" "<<2020-arr[i]<<"\n";
                // I an priring the array pairs whose sum is 2020 but according to your requirement
                // you can print True/False or index of pairs
            }
        }
        return 0;
}

# Analysis:

The Time complexity of the above program will be O(n), best time complexity

We are traversing the whole array only once

We can use Brout force method for solving the above problem but time complexity will be O(n^2)

But in the above program First we transform whole array in the form of dictionary ( In C++ dictionary refers as map) and then we solve the next subproblem of this problem.