29 votes 29 votes 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. DS gate1994 data-structures array normal descriptive + – Kathleen asked Oct 5, 2014 recategorized Apr 25, 2021 by Lakshman Bhaiya Kathleen 4.9k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Mizuki commented Nov 1, 2018 reply Follow Share What is Pascal like pseudo code? 0 votes 0 votes Shivamsingh43 commented Sep 10, 2020 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.
Best answer 46 votes 46 votes i = 1; j = n; while(i != j) { if(A[i] + A[j] == M) break; else if(A[i] + A[j] < M) i++; else j--; } ankitrokdeonsns answered Oct 11, 2014 edited Jun 13, 2018 by Milicevic3306 ankitrokdeonsns comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Prashant. commented Mar 5, 2018 reply Follow Share :) ... 1 votes 1 votes Mizuki commented Nov 1, 2018 reply Follow Share What is Pascal like pseudo code? 0 votes 0 votes Neelam_$ingh_222 commented Jul 23, 2020 reply Follow Share 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 ? 1 votes 1 votes Please log in or register to add a comment.
6 votes 6 votes 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 } vermamayank564 answered Jul 14, 2017 vermamayank564 comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes 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) Akash Kanase answered Dec 17, 2015 Akash Kanase comment Share Follow See all 3 Comments See all 3 3 Comments reply radha gogia commented Jan 3, 2016 reply Follow Share 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. 1 votes 1 votes Aspi R Osa commented Jan 10, 2016 reply Follow Share @Akash : n/2<=k<=n, Why this condition? I think it could be from 1 to n anywhere? 0 votes 0 votes raja11sep commented Jul 8, 2021 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.
3 votes 3 votes 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 Bhagirathi answered Oct 11, 2014 edited Dec 22, 2017 by Puja Mishra Bhagirathi comment Share Follow See all 2 Comments See all 2 2 Comments reply Arjun commented Oct 11, 2014 reply Follow Share But i and j need not be consecutive rt? if sum is > given element, we have to start with the next i rt? 1 votes 1 votes Bhagirathi commented Oct 16, 2014 reply Follow Share yes you have got a point let me rethink... 0 votes 0 votes Please log in or register to add a comment.