GATE CSE 1994 | Question: 25

Question

An array $A$ contains $n$ integers in non-decreasing order, $A[1] \leq A[2] \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $i, j,$ such that $A[i]+A[j]=a$ given integer $M$, if such $i, j$ exist.

Comments

What is Pascal like pseudo code?

---

As an alternative to compilers generating machine code or assembly language, a more portable alternative is to generate a pseudo machine language that can then be transported to various machines and converted to their native code. This code is called Pascal like pseudo code.

---

• Two-pointer technique:

  • Start with two pointers: one at the beginning (left) and one at the end (right) of the array.
  • Calculate the sum A[left]+A[right]
    • If the sum is equal to M, you've found the solution.
    • If the sum is less than M, move the left pointer to the right to increase the sum.
    • If the sum is greater than M, move the right pointer to the left to decrease the sum.
  • Continue until the pointers meet or a solution is found.

•  

---

User Two Pointer Approach: Start ------ End

Answer 1

i = 1;
j = n;
while(i != j) {
   if(A[i] + A[j] == M) break;
   else if(A[i] + A[j] < M) i++;
   else j--;
}

Comments

:) ...

---

What is Pascal like pseudo code?

---

Sir why can't it be in  linear time as we can store indexes i,j or can print them and continue with our loop  to find more such pairs in array ?

Answer 2

i=1;
j=n;
if((a[1]+a[2]>M) OR (A[n]+a[n-1]<M))
  print Element not found
else
   {
    while(a[i]+a[j]!=M)
        { 
        if(a[i]+[J]<M) i++;
        else j--;
        }
   print i ,j
   }
   

Answer 3

This algorithm can be written easily with help of hash data structure. (Here they have not said whetehr we can use other DS or not , So I will use it )

1. First use hash table, to has first half no of this array. You can do it using O(1) time.

2. Then check for a-A[k], where n/2<=k<=n, by lookup using Hash table. You can do this is O(1) each lookup( Ideal Time compexity).

TIme compexity => O(N)

Comments

can u explain ur logic once again ,its really hard for me to understand.

what is the meaning of this line:

First use hash table, to has first half no of this array.

---

@Akash :

n/2<=k<=n,

Why this condition?

I think it could be from 1 to n anywhere?

---

First use hash table, to has first half no of this array. You can do it using O(1) time.
 

There is a typo. We can’t hash half of the elements of an array in O(1) time it will take O(n) time.

Then check for a-A[k], where n/2<=k<=n, by lookup using Hash table. You can do this is O(1) each lookup( Ideal Time compexity).

Suppose there are 10 elements in an array and only by adding A[1] and A[2] we are getting a.

Your code will output there is no such pair exist.

Sir, I think both of your points are wrong. But the time complexity will be O(n). I tried to explain with code. 

 

Answer 4

our works become simpler when we read the word its in increasing order...keep on adding the 2 consecutive  numbers

case 1:the sum is less than given element then continue

case 2:the sum is greater than given element then terminate and return -1

case 3:the sum is equal to given element then terminate and return the position of i and j

Comments

But i and j need not be consecutive rt? if sum is > given element, we have to start with the next i rt?

---

yes you have got a point let me rethink...

Answer 5

1. Two pointer Technique: Two Pointers Technique - GeeksforGeeks .  Time complexity: O(n) means Linear and Space Complexity is O(1) means constant. It will only work for sorted arrays.

2. Hashing: We can use an extra array to solve this problem in linear time. It will also work for unsorted arrays. Time complexity: O(n)  and Space Complexity: O(n).

Using Map in C++ STL :

void Find_Pair(int arr[], int n, int a)

{

    // create an empty map

    unordered_map<int, int> map;

    // do for each element

    for (int i = 0; i < n; i++)

    {

        // check if pair `(arr[i], a - arr[i])` exists

        // if the difference is seen before, print the pair

        if (map.find(a - arr[i]) != map.end())

        {

            cout << "Pair found (" << arr[map[a - arr[i]]] << ", " << arr[i] << ")";

            return;

        }

  // store index of the current element in the map

        map[arr[i]] = i;

    }

 // we reach here if the pair is not found

    cout << "Pair not found";

}

Answer 6

Array A is in non-decreasing order (2 or more same elements can be present).
∴ A[1] ≼ A[2] ≼ A[3] ≼ ... ≼ A[n]

Pascal-like pseudo-code:
begin
        i:= 1, j:= n;
        while (i != j) do
        begin
                 if (A[i] + A[j] == M) then break;
                 else if begin 
                                    (A[i] + A[j] < M) then i:= i + 1;
                                    else begin
                                                    j:= j - 1;

                                    end
                 end
       end
end