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 5.0k 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 Arjun commented Oct 12, 2014 reply Follow Share final step is else j--; rt? 1 votes 1 votes ankitrokdeonsns commented Oct 12, 2014 reply Follow Share yes, my mistake 1 votes 1 votes vermamayank564 commented Jul 14, 2017 reply Follow Share Suppose the value of 'M' is the first element of an array. Then your program will exit from while loop without giving right answer. Correct me if i am wrong. 1 votes 1 votes junk_mayavi commented Aug 29, 2017 i edited by junk_mayavi Nov 24, 2017 reply Follow Share If such an i and j does not exist for a given array, Instead of iterating till half the array elements, We can simply do a check at the beginning of code like, $if\ A[n-1]+A[n] < M$ $then\ return\ FAILURE$ So that this will save time. 0 votes 0 votes thepeeyoosh commented Nov 24, 2017 reply Follow Share Mr. arjun, Kindly look this, Sorry to say but I think this is right code because If (A[i]+A[j] <M) then i++; because of the sum of first and last no. is smaller than the given value so you need to increase the sum to reach the value "M" That why we need to increase the index i to i+1. 0 votes 0 votes MiNiPanda commented Mar 5, 2018 reply Follow Share If there are more than one such (i,j) pair will the program give correct result? Like suppose the given array is <1,1,2,3,4,4> and M=5 then there are 4 such (i,j) pairs. In the question it's just mentioned that there exists i,j . 1 votes 1 votes Prashant. commented Mar 5, 2018 reply Follow Share Then this algorithm may not be linear time algorithm. The algorithm they ask will stop when they found one such pair ( can be done in O(n) time). 1 votes 1 votes MiNiPanda commented Mar 5, 2018 reply Follow Share Okay I got it @Prashant . Thank you 0 votes 0 votes 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.