Question

In: Computer Science

Design and analyze asymptotically an O(nlgn) transform-conquer algorithm for the following problem: input: an array A[lo..hi]...

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

    • 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.

Solutions

Expert Solution

# 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.


Related Solutions

Divide and conquer approach to find the minimum absolute difference in array A[lo..hi] Input an array...
Divide and conquer approach to find the minimum absolute difference in array A[lo..hi] Input an array A[lo..hi] of n real numbers. Requirement: Shouldn't use a sorting algorithm. Complexity O(nlgn)
5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, ....
5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, . . . , n] of positive integers, an integer K. Decide: Are there integers in A such that their sum is K. (Return T RUE or F ALSE) Example: The answer is TRUE for the array A = [1, 2, 3] and 5, since 2 + 3 = 5. The answer is FALSE for A = [2, 3, 4] and 8. Note that you...
Design and analyze a divide-and-conquer algorithm for finding the maximum element in a list: L[0: n – 1].
The following submission rules apply:·    For those questions requiring programs, the solutions must be implemented using JavaScript or Java.o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices.o Solutions must be provided in plain text so that formatting is not lost.·    All answers must be provided in this document.·    Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.Design and analyze a divide-and-conquer algorithm for finding the maximum...
(a) Implement the following algorithm, which is given a duplicate-free array array as input, in C++....
(a) Implement the following algorithm, which is given a duplicate-free array array as input, in C++. whatDoIDo (array): 1) Build a heap from array (using buildHeap as explained in class), where the heap starts at position array[0]. 2) Starting from j = size of array - 1, as long as j>0: i. Swap the entries array[0] and array[j]. ii. Percolate down array[0], but only within the subarray array[0..j-1]. iii. Decrement j by 1. Provide three input/output examples for duplicate-free arrays...
Given an array of positive integers except one negative integer. Develop a divide-conquer algorithm to find...
Given an array of positive integers except one negative integer. Develop a divide-conquer algorithm to find the index of the negative integer, and compute its average complexity.
give an algorithm where given as input an array A[1...n] withthe following property. There exists...
give an algorithm where given as input an array A[1...n] with the following property. There exists an index I such that if we append A[1...i−1] after A[i...n], we get an array in sorted increasing order. For simplicity you can assume that n is a power of 2.Give an efficient algorithm that returns the smallest element in A. Analyze the time complexity of your algorithm.Hint: you may want to compare A[1] and A[n/2].
please write in c++ Algorithm Design problem: Counting inversions: given an array of n integers, find...
please write in c++ Algorithm Design problem: Counting inversions: given an array of n integers, find out the total number of inversions in the given sequence. For example, for the sequence of 2, 4, 1, 3, 5, there are three inversions (2,1), (4,1), and (4,3). Give a brute-force algorithm with running time of O(n^2). Using the technique of divide-and-conquer, design an algorithm with running time of O(nlog n).
The following divide-and-conquer algorithm is designed to return TRUE if and only if all elements of...
The following divide-and-conquer algorithm is designed to return TRUE if and only if all elements of the array have equal values. For simplicity, suppose the array size is n=2k for some integer k. Input S is the starting index, and n is the number of elements starting at S. The initial call is SAME(A, 0, n). Boolean SAME (int A[ ], int S, int n) { Boolean T1, T2, T3; if (n == 1) return TRUE; T1 = SAME (A,...
In Liinear-time selection algorithm where the input array of numbers are cut into groups of size...
In Liinear-time selection algorithm where the input array of numbers are cut into groups of size 5. Show that, when the group size is 7, the algorithm still runs in linear time.
Problem 3 (4+2+2 marks). (a) Implement the following algorithm, which is given a duplicate-free array array...
Problem 3 (4+2+2 marks). (a) Implement the following algorithm, which is given a duplicate-free array array as input, in C++. whatDoIDo (array): 1) Build a heap from array (using buildHeap as explained in class), where the heap starts at position array[0]. 2) Starting from j = size of array - 1, as long as j>0: i. Swap the entries array[0] and array[j]. ii. Percolate down array[0], but only within the subarray array[0..j-1]. iii. Decrement j by 1. Provide three input/output...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT