[algogeeks] Re: Online Job Directory
Report this profile as spam: http://groups.google.com/groups/abuse?url=http%3A%2F%2Fgroups.google.com%2Fgroups%2Fprofile%3Fenc_user%3DGblPpxBBT4-MvI5XR0ZYoR4i_V9C%26&_done=%2Fgroups%2Fprofile%3Fenc_user%3DGblPpxBBT4-MvI5XR0ZYoR4i_V9C%26&; On 11/3/07, maithili <[EMAIL PROTECTED]> wrote: > > Tired of joining program after program looking for a Real Home Based > Job? > Look no further! > Our Work at home job directory is loaded with over 1000 Work at Home > Employment Opportunities > Offered by Real Employers. > Visit us today for your free sample job guide > (http://www.typeinternational.com/affil/ti12247.htm) select work from > home employment > > > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Here we advertise you on in whole world through internet,its very easy way.........!
Report this profile as spam http://groups.google.com/groups/abuse?url=http%3A%2F%2Fgroups.google.com%2Fgroups%2Fprofile%3Fenc_user%3DuOf4yCUAAADmXReKED4Frhy2qK2vDZ5MsIwsO9grbROoym-hmFhCuvYd4t0poxpgCW19OZ2fvH0%26&_done=%2Fgroups%2Fprofile%3Fenc_user%3DuOf4yCUAAADmXReKED4Frhy2qK2vDZ5MsIwsO9grbROoym-hmFhCuvYd4t0poxpgCW19OZ2fvH0%26&; On 11/1/07, net expert <[EMAIL PROTECTED]> wrote: > Its true that today world is Internet world,every thing is > globelised,differences go away > WE gave you our service on your pay demand,if you want to advertise your > product,website,yourself profile or any thing you want,we advertise you in > whole world,just contact us and try our sevice > > its true that through our service you get be popular in world in few > minutes..we advertise any thing > contact us our advertiser 00923007530720 > or Email us,give your full detail otherwise your request may be > rejected. > [EMAIL PROTECTED] > > come first get first...this our policy > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Spiral number
Use the property that one of the diagonals has squares of odd numbers. So given a co-ordinate in that diagonal you know the number at that position. For positions not on that diagonal you can add/subtract appropriately and obtain the number you need. -Dhyanesh On 10/18/07, mukesh tiwari <[EMAIL PROTECTED]> wrote: > > Hello everybody , i am trying to solve this(http://online- > judge.uva.es/ p/v9/903.html) problem and input constrants are such > that it is not > possible to store the the numbers in the array and print those > numbers. So i use the algorithm > > 1)get the number and return its coordinate > 2) take the input all adjacent coordiantes and return the number > belonging to that coordinate . > > i am facing the problem in second part that is if i have given > coordiante how to get the number belonging to that coordinate, > > lets consider the spiral > > 21 22 23 24 25 26 > 20 7 8 9 10 > 19 6 1 2 11 > 18 5 4 3 12 > 17 16 15 14 13 > > let the coordinate of 1 is (0,0) ie origin then coordinate of 11 > will > be (2,0) and so on . > now my problem is if i give coordiante (2,-1) then my program should > return 12 . > > thnkx in advance > > > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Making money from google is hard
Go to google groups, go to "View Profile" for that person and then click "Report Profile". There you can report the person as Spam. If enough people do it then such people would be banned. -Dhyanesh On 9/17/07, Dhruva Sagar <[EMAIL PROTECTED]> wrote: > On 9/17/07, daizi sheng <[EMAIL PROTECTED]> wrote: > > anyone who can block such ad-guys? > > That would be good...anyone? please? > > > > > 2007/9/17, austin <[EMAIL PROTECTED]>: > > > > > > > > Making money from google is hard > > > http://www.goodtolove.com has solved this problem .They re sharing > > > their 60% adsense revenue with you.Just start sharing > > > videos,webpages,images and start making friends.Guaranteed you will be > > > making a lot of money from google using this website. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > Thanks & Regards, > Dhruva Sagar. > > > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding a single repeated element in an array
I am afraid this problem CANNOT be solved faster than O(n*log(n)) . If you can find a single repeated element in an array in O(n) then you can solve the element uniqueness problem. However this problem cannot be done in better than O(n * log(n) ). http://en.wikipedia.org/wiki/Element_uniqueness_problem -Dhyanesh On 8/25/07, L7 <[EMAIL PROTECTED]> wrote: > > > > > Your solution really parses terms on what it means to be performing > > asymptotic analysis... you cannot say that this storage is constant in > > 32 bits, when it is not said that you are using 32 bit numbers. If you > > are speaking asymptotically at all, saying that something is O(n) or > > O(log(n)) or anything else then _by definition_ you are talking about > > infinity... > > > > Oh, and one more thing, O(1/n) is 0, so your reductio ad absurdum > fails. > > > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find largest sum
If you think of your DP solution, it is almost the same as the previous O(n) solution you gave. That one is also DP in way that you store just one previous solution. -Dhyanesh On 8/24/07, Lego Haryanto <[EMAIL PROTECTED]> wrote: > > I should take my statement regarding the O(n) space for DP back ... > > If we don't care storing each intermediate result, ... then space is also > O(1). > > On 8/24/07, Lego Haryanto <[EMAIL PROTECTED]> wrote: > > > > For the DP recurrence, consider f(i) is the "best contiguous sum ending > > at this index i". > > > > f(i) = a[i], if i == 0 > > f(i) = max(a[i], f(i-1)+a[i]), on other cases > > > > Basically, for each index i, to end a subarray ending at i, it's obvious > > that we can either "extend" the best solution for previous index, or we can > > start our own. > > > > Now, the maximum subarray sum would be the max(f(i)), for i = 0 .. n-1. > > > > On 8/24/07, Lego Haryanto <[EMAIL PROTECTED] > wrote: > > > > > > I thought I already answered earlier even thought it's just words and > > > no code. > > > > > > sum = 0 > > > best = -INF > > > FOREACH val IN a DO > > > sum = sum + val > > > best = MAX(best, sum) > > > IF sum < 0 THEN sum = 0; > > > ENDFOR > > > > > > O(n) runtime, O(1) space. > > > > > > DP can be done as well in O(n), but due to the nature of DP, you'll > > > need O(n) space as well. > > > > > > > > > On 8/24/07, ilija <[EMAIL PROTECTED]> wrote: > > > > > > > > > > > > I would like to see your code for the first case. > > > > I really doubt that there exists an O(n) algo for this. > > > > > > > > On 23 kol, 16:11, "Lego Haryanto" < [EMAIL PROTECTED] > wrote: > > > > > Either case is O(n), in fact. > > > > > > > > > > On 8/23/07, ilija <[EMAIL PROTECTED] > wrote: > > > > > > > > > > > > > > > > > > > > > If the subarray needs to be continuous, then you can do it using > > > > DP. > > > > > > If it doesn't, you can do it using an O(n) algo - simply sum all > > > > the > > > > > > positive integers. > > > > > > > > > > > On 22 kol, 19:55, Ravi < [EMAIL PROTECTED] > wrote: > > > > > > > You're given an array containing both positive and negative > > > > integers > > > > > > > and required to find the subarray with the largest sum. > > > > > > > Write a routine in C for the above. > > > > > > > > > > -- > > > > > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > > > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > > > > > > > > > -- > > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > > > > -- > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem with conditional statement
It says " If there is more than one solution print the pair with smaller X value." Also I believe for a value of X only one of the 2 Y values might work, not sure though. -Dhyanesh On 6/18/07, mukesh tiwari <[EMAIL PROTECTED]> wrote: > Hi everybody i am trying to solve problem > http://acm.uva.es/p/v105/10512.html. > > my solution is > > (x+y)y=P(1) > (x-y)x=Q (2) > > (1+(y/x))xy=P (1)//taking x outside > (1-(y/x))x^2=Q (2) > > dividing 1 and 2 and let (y/x)=k > > (1+k)k/(1-k)=P/Q; > > solving for k > k=-(P+Q) +-sqrt((P+Q)^2+4PQ)/2Q; > since x>=y so we can not take -ve sign as it will make |k|>1 which is not > possible so i take only +ve sign ; > solution is possible only when > (P+Q)^2+4PQ is perfect square . >after determining k we can find out x and y > so my values are > > x=+-sqrt(Q/(1-k)); > and y=+-sqrt(Pk/(1+k)); > > now my problem is based on for each value of x we have two values of y so > we have 4 pair of values .So which value to output . > > thnkx in advance . > > > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: A cycle with minimum length
Hi You can solve this by dynamic programming/memoization. Start off from the left and maintain two lists of points, one for forward traversal and one for reverse traversal. Each point would be in any one of the lists. When you encounter a point try putting it in each of the lists turn by turn and call the function recursively. You just need to maintain the heads of each of the lists. Once you memoize, the complexity would be O(n^3). The signature of the function would be: int least_path( int current_position, int head_of_list1, int head_of_list2) -Dhyanesh On 3/30/07, Mahdi <[EMAIL PROTECTED]> wrote: > > Hello everyone! > We have n points in a chart that none of them have the same length(I > mean their 'x' parameter). We want to find a cycle with MINIMUM length > with these assumptions : > We start from the point with minimum length, meeting all of the points > and finally return to the starting point. We are allowed to change our > direction of moving only one time. I mean we go through more positive > points seeing some of them, and when we arrive to the rightest point, > we change our direction to the left, and seeing reminding points, > return to the starting point. > Let me give an example: > We have 3 points a,b,c : > a : x=2y=0 > b: x=10 y=8 > c: x=17 y=0 > one possible cycle is : a-->b-->c-->a > another : a-->c-->b-->a > One of them is shorter than the another. > > thanks. > > > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem 4.2 from "Introduction to algorithms"
1) Scan through the array counting number of 0s and 1s in MSB, as well as separating the 0s into an array arr0 and 1s into an array arr1 (if you do not want to use extra space you can use splitting around pivot pass of quicksort). 2) You would know how many 0s and 1s should be present in MSB for the number 1 ... n (this would be n/2 and n/2 if n is a power of 2). 3) Either the 0s or 1s would be less, so the missing number has that digit as MSB. 4) Take that bucket i.e. arr0 or arr1 and repeat steps 1 to 3. The complexity of this is n + n/2 + n/4 ... = 2n = O(n). -Dhyanesh > On 11/17/06, Arun <[EMAIL PROTECTED]> wrote: > > > > the original problem if the array is unsorted, u can do it, by counting > the > > number of 1's (and hence 0's), in each bit position. (i.e vertically > scan > > thru all the numbers once for each bit position). given any n, u know > how > > many 1's shud be present in msb,2nd msb and so-on. based on this u can > find > > the missing number > > but this is O(n . (number of bit positions - which is atmost lg(n)) ) > still too slow. There is an O(n) solution :) > > > > to make the problem easier I have made the assumption that array is > sorted > > :-) > > since the array is sorted , u know that there will be 2 ^(n-1) 0's > followed > > by 2 ^(n-1) 1's in the MSB(most significatn bit) and > > 2 ^(n-2) 0's and followed by 2^(n-1) 1's repeated twice. > > So in general, u have for ith significant bit (i=1 means msb), 2^(n-i) > 0s > > then 2^(n-i) 1s repeated i times. > > Now just do a binary search. Starting with the msb, extract(i,n/2) . if > its > > 1(supposed to be 0), the missing number is in first half(and msb of > missing > > number is 0). do the same for second msb and so on... > > comlpexity = O(lg n) , for n=2^k. > > > > > > > > > > On 11/17/06, Norbert < [EMAIL PROTECTED]> wrote: > > > > > > extract(i, n) - i'th bit from position n in an array A - i'th bit of > A[n] > > > > > > On 11/17/06, Idris <[EMAIL PROTECTED]> wrote: > > > > > > > > > > > > Is this extracting i'th bit from a[X] or just extracting Integer > from i > > > > th index of an array??? > > > > > > > > if its the later, then get the number and sum up by using OR > > > > operation not sure:-) > > > > > > > > then subtract it from n(n+1)/2="missing Number" > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Proving Waring hypothesis...
I have a slight improvement O ( n^2 log (n ) )Say you have a^2 + b^2 + c^2 = d.Keep a sorted list of all possible a^2 + b ^ 2 ... this would take n^2 time to generate and n^2 log n to sort. Now loop over all possible 'd' and 'c' and compute d - c ^ 2. Use binary search to determine whether that number is in the list ... if it is then 'd' is a number which CAN be represented otherwise try for the next 'c'. There might be a better solution ... still thinking-DhyaneshOn 10/31/06, Karthik Rathinavelu < [EMAIL PROTECTED]> wrote:Question: Given n, find the numbers in the range of 0...n which CAN'T be represented in the form of sum of squares of 3 non-negative numbers. If anyone could possibly give a solution better than O(n^3), it will be good. Thanks,R.Karthik --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
I just submitted a solution which uses BFS and passes the judge cases. So it is indeed a shortest path problem. Using Djistra's would be fine too, but as it is here the edge weights are just 1 so BFS works.-Dhyanesh On 10/30/06, Karthik Singaram L <[EMAIL PROTECTED]> wrote: I am not sure If I got the question right140 3 1 2 31 1 02 2 0 33 2 0 21 2Isn't the answer that camarade 1 talks to camarade 0 who inturn talksto 2. Isnt this shortest path algorithm? isnt Djikstra O(VlogV) which seems feasible for the problem rite?On 10/30/06, Pradeep Muthukrishnan <[EMAIL PROTECTED]> wrote:> I dont see how Djikstra can be used here? >>> On 10/30/06, Dhyanesh (ધયાનેશ) <[EMAIL PROTECTED]> wrote:> > Djikstra's or any other single-source shortest path algorithm should be good enough I guess. > >> > -Dhyanesh> >> >> >> > On 10/30/06, vijay < [EMAIL PROTECTED]> wrote:> > >> > > Anyone know how to solve this problem... > > > http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3502> > > ...> > > I thk its a toughie... > > >> > >> > >> > >> > >> >>>> >> --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
Why not .. it is a graph with edge weights = 1. In fact we can even just use BFS to solve this problem. I will try and submit a solution and see if what I am thinking is right.-Dhyanesh On 10/30/06, Pradeep Muthukrishnan <[EMAIL PROTECTED]> wrote: I dont see how Djikstra can be used here?On 10/30/06, Dhyanesh (ધયાનેશ) < [EMAIL PROTECTED]> wrote: Djikstra's or any other single-source shortest path algorithm should be good enough I guess. -DhyaneshOn 10/30/06, vijay < [EMAIL PROTECTED]> wrote:Anyone know how to solve this problem... http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3502 ...I thk its a toughie... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
Djikstra's or any other single-source shortest path algorithm should be good enough I guess.-DhyaneshOn 10/30/06, vijay < [EMAIL PROTECTED]> wrote:Anyone know how to solve this problem... http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3502...I thk its a toughie... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: iarcs basic division (problem 1 and 2)
I would agree with problem 2.However, in problem 1, they have given you the different operations right ? I do not think you can choose your own operation. From the problem statement - "Thisis followed by M lines each containing K integers describing the M different operation". So if you have a restricted set to choose from then it might not be always possible. -DhyaneshOn 9/18/06, Terry <[EMAIL PROTECTED]> wrote: Please ignore . my mistake.Terry wrote:> What about problem 1 ? i am really puzzled .>>> Problem 1: The Hunpur Visa>> Hunpur lies to the north of Siruseri and flights from Siruseri to many > parts of the world go through Samosa Airport, the busiest airport in> Hunpur. Hunpur demands that residents of Siruseri obtain "transit> visas" in order to fly through Samosa.>> Recently, the authorities of Hunpur have enforced some strange rules > regarding photographs to be submitted for obtaining visas. The size of> the face in the photograph is measured along K different directions to> get the numbers (m1,m2, ...,mK). The consulate has specified a lower > bound and upper bound (li and ui respectively) along each of the K> directions. So, a photograph with measurements (m1, m2, ...,mK) is> accepted if and only if li = mi = ui for 1 = i = K. Otherwise, > it is rejected.>> For example, if K =2 with l1 = 32, u1 = 36, l2 = 20 and u2 = 24, a> photograph with measurements (33,20) would be accepted, but photographs> with measurements (31,20) or (36,25) would be rejected. >> Many studios in Siruseri have come up with a partial solution to this> problem. They digitally alter the image. They have a fixed collection> of M "operations". Each operation is a tuple (d1, d2, ...,dK), where > each di is a (positive or negative) integer. The effect of this> operation on a image with dimensions (m1,m2, ...,mK) is to change the> dimensions to (m1+d1, m2+d2, ..., mK+dK). The studio cannot apply more > than two operations on a photograph as it damages the quality of the> image. Moreover, no operation can be applied more than once.>> For example, using the operations (-2,3) and (3,-1) we can transform an > image of size (31,20) to one of size (32,22) which would be accepted by> the Hunpur consulate. On the other hand, using these operations we> cannot alter an image of size (36,25) to an acceptable one. >> Your task is to determine whether the photograph whose dimensions are> given can be altered using at most two operations to an acceptable> photograph.>> Input format> > The first line contains two integers K and M. The second line contains> K integers giving the lower bounds for the K directions. The third line> contains K integers giving the upper bounds for the K directions. This > is followed by M lines each containing K integers describing the M> different operations. This is followed by the last line containing K> integers specifying measurements of the photograph.> > Output format>> If it is not possible to alter the image using at the most 2 operations> then print a single line with the word NO. Otherwise, the first line of> the output must have the single word YES, the second line must contain > an integer i, indicating the number of operations (0 = i = 2) that> may be used to transform the image into an acceptable one, and this> should be followed by i lines describing the i operations. There may be > more than one way to transform the image into an acceptable one, it> suffices to print any one.>> Note: In this task, test inputs will be arranged in groups and marks> will be assigned for groups of test inputs rather than to each > individual test input. For example, one mark may be assigned for a> group of three test inputs. This means that to score that one mark your> program must run correctly on all three test inputs in the group. Thus, > blindly printing NO is not likely to score many marks.>> Test data>> You may assume that K = 100 and M = 100.>> Example>> Here is a sample input and output corresponding to the example > discussed above.>> Sample input>> 2 2> 32 20> 36 24> -2 3> 3 -1> 31 20>> Sample output>> YES> 2> 3 -1> -2 3 > **> Solution;> I think the answer will always be YES.>> we have numbers like (l1,u1) ,(l2,u2),(l3,u3)...(ln,un) and numbers m1 > ,m2,m3,...mn.>> now to map mi to (li,ui) , it is always possible (forgetting overflow).> Is something wrong with my understanding of the problem. So i can> always find a vector d1,d2,d3..,dn which maps m1,m2,m3...,mn between > (l1,u1),(l2,u2)...(ln,un) in a single operation or 0 operations (if> they already are in the range ). If a point is on x axis, then to move> them between 2 points on x axis requires 1 displacement.similarly for> other>> Comments please. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsub
[algogeeks] Re: find the sum
Bruce Yang has the right O(n)N algorithm. Basically it is:
1. Have two pointers ptr1 = arr[0] and ptr2 = arr[ n - 1].
2. While (!found && ptr1 < ptr2)
a. sum = ptr1 + ptr2
b. if (sum == req_sum)
found the numbers .. ptr1 and ptr2
c. if (sum < req_sum)
Increment ptr1
d. if (sum > req_sum)
Decrement ptr2
-Dhyanesh
On 8/7/06, Lego Haryanto <[EMAIL PROTECTED]> wrote:
>
> I'm not sure if we can find an O(n) algorithm for this, but there is an
> improvement to your O(n lg n) algorithm, which basically limits your binary
> search scope each time we scan each number.
>
> For instance, in the set of 1, 3, 7, 9, 16, 28, 49 and x=16, ... we start
> with a scope of the whole S except for the first one [3,7,9,16,28,49]
> subject to binary search.
>
> When we see the first number (1), we know for sure we're looking for 15
> (which is 16-1), so when we binary search and we can't find 15, we should
> narrow down the search scope to the upper limit of 9 for the next number
> (there is no reason to include 16, 28, and 49 for the next search since the
> next number we scan will definitely be greater than 1). So, we set 9 as our
> upper limit.
>
> When the next number (3) comes, we don't even need to binary search because
> our search range is only [7, 9], and 13 is definitely out of range.
>
> Note that the lower limit for the binary search set can always be set to the
> next-neighbor of the number being evaluated.
>
> Eventually, the algorithm will find the desired pair, or the algorithm
> terminates because lower-limit is greater than upper-limit, which means
> there's no such pair.
>
> Please confirm.
>
>
> On 8/7/06, ravi <[EMAIL PROTECTED]> wrote:
> >
> > The input is an array S containing n real numbers, and a real number
> > x, Design an algorithm to determine whether there are 2 elements of S
> > whose sum is exactly x. and onemore thing is that S is in sorted
> > order.
> >
> > I got the solution with the complexity of O(n logn) but I am searching
> > for an algo. on O(n) complexity.
> >
> > My solution is like this,
> >
> > for each element k in S // There are n element so iterates n
> > times
> > {
> > k = k - x;
> > if( BinarySearch(k,S) ) // complexity is O ( log n )
> > {
> > found an elemnt
> > break;
> > }
> > }
> >
> > So overall complexity is O ( n logn).
> >
> >
> >
> >
> >
>
>
>
> --
> Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
>
> >
>
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
