In: Computer Science
Design and analyze asymptotically an O(nlgn) transform-conquer algorithm for the following problem:
# 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.