Let A[1..n] be an array of positive integers (A is not sorted). Pinocchio claims

Question

Let A[1..n] be an array of positive integers (A is not sorted). Pinocchio claims that there exists an O(n)-time algorithm that decides if there are two integers in A whose sum is 1000. Is Pinocchio right, or will his nose grow? If you say Pinocchio is right, explain how it can be done in O(n) time; otherwise, argue why it is impossible.

Remarks:

If needed, you may assume that sorting n numbers can be done in time O(n lg n) (e.g., using Heap Sort). If you need to sort, you can directly apply such a sorting algorithm (without writing the pseudocode), and claim that it runs in O(n lg n) time, where n is the number of elements/numbers being sorted. When asked to give an algorithm that meets a certain time bound, you need to give the algorithm (pseudocode/description) and analyze its running time to show that it meets the required bound.

Explanation / Answer

YES Pinocchio is right

Explanation :

We will require an extra Array . Let us Assume we have a Array of size 100000 initialised to false
1) First thing we will do is iterate our original array and mark all the numbers the are available with us in the second array

Example : arr[] = {5, 10, 20, 100};

then Our ExtraArray will mark extra[5] = 1 , extra[100] = 1, extra[20] = 1, extra[10] = 1

2) Once the marking is complete . We will iterate the Array again to check if the sum exists
=> This is How we will check
=> remaining_sum = 1000 - array[i]
=> if remaining_sum exists in the extra array that means there exist two numbers whose sum is equal to target



3) We required an extra space which takes O(n) space complexity and we iterate dthe array twice by both with n i.e O(n) time complexity. So hence the time complexoty is O(n).

Hence Pinocchio is right

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.