[algogeeks] Jumping Puzzle
Given an array, start from the first element and reach the last by
jumping. The jump length can be at most the value at the current
position in the array. Optimum result is when you reach the goal in
minimum number of jumps.
For ex:
Given array A = {2,3,1,1,4}
possible ways to reach the end (index list)
i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index
4)
ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)
Since second solution has only 2 jumps it is the optimum result.
My solution is for any index i loop from i to i + A[i]
find an index j where
(j + A[j]) is maximum for all j.
make i=j;
This solution in O(n) i suppose coz we are picking each element twice
in the worst case.
I have read a O(n^2) DP solution for this problem.Is there any
case where my approach will fail ?
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] C doubt
Suppose i create a block of 10 ints, p is a pointer pointing to this block. int (*p)[10]; How can i initialize these 10 integer blocks using pointer p. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Jumping Puzzle
Hi, probably you did'nt got my approach :
A={2,2,3,4,1,1,1,1,1}
first i=0 A[i] = 2
so candidates are A[1] ,A[2]
we choose max(A[1] +1 , 2 + A[2]) = A[2]
now we jump to A[2].
now candidates are A[3],A[4],A[5]
we choose max(A[3] + 3 , A[4] + 4, A[5] + 5)
= A[3]
so now we jump to A[3]
now candidates are A[4],A[5],A[6],A[7],
Clearly A[7] + 7 is maximum so we jump to A[7] and then we jump to
A[8]
so we went from 0-2-3-7-8.
Note i am not choosing max A[i] I am choosing max(i + A[i]).
Can anyone find a flaw in this approach ?
On Aug 11, 9:42 pm, Tharun Damera tharun1...@gmail.com wrote:
Yes, greedy algo doesn't work.. U shud hv DP.. plz post the soln which u
read..
A={2,2,3,4,1,1,1,1,1}
Ur algo gives 0,2,5,6,7,8(these are indices... index starts frm 0)
best soln is 0,1,3,7,8..
On Thu, Aug 11, 2011 at 2:37 PM, Arun Vishwanathan
aaron.nar...@gmail.comwrote:
I did not get the optimal solution part..how is that u jump 1 to index 1?
On Thu, Aug 11, 2011 at 10:07 AM, Algo Lover algolear...@gmail.comwrote:
Given an array, start from the first element and reach the last by
jumping. The jump length can be at most the value at the current
position in the array. Optimum result is when you reach the goal in
minimum number of jumps.
For ex:
Given array A = {2,3,1,1,4}
possible ways to reach the end (index list)
i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index
4)
ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)
Since second solution has only 2 jumps it is the optimum result.
My solution is for any index i loop from i to i + A[i]
find an index j where
(j + A[j]) is maximum for all j.
make i=j;
This solution in O(n) i suppose coz we are picking each element twice
in the worst case.
I have read a O(n^2) DP solution for this problem.Is there any
case where my approach will fail ?
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
People often say that motivation doesn't last. Well, neither does
bathing - that's why we recommend it daily.
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
D.Tharun| Computer Science and Engineering, IIT Bombay | tharu...@iitb.ac.in |
+918097345806
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Probability Puzzle
A bag contains 5 coins. Four of them are fair and one has heads on both sides. You randomly pulled one coin from the bag and tossed it 5 times, heads turned up all five times. What is the probability that you toss next time, heads turns up. (All this time you don't know you were tossing a fair coin or not). -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Probability Puzzle
Can anyone explain the approach how to solve this . I think all tosses are independent so it should be 3/5. why is this in- correct On Aug 7, 10:55 pm, saurabh chhabra saurabh131...@gmail.com wrote: sry...its wrong On Aug 7, 10:34 pm, Algo Lover algolear...@gmail.com wrote: A bag contains 5 coins. Four of them are fair and one has heads on both sides. You randomly pulled one coin from the bag and tossed it 5 times, heads turned up all five times. What is the probability that you toss next time, heads turns up. (All this time you don't know you were tossing a fair coin or not). -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Amazon Puzzle
Two people are travelling through flight. Both have parachute and jump anywhere randomly i.e none of them knows who has jumped where.(Assume there's a big desert and they jump at any random location). Now, both of them have a single piece of paper on which they can write instructions before jumping and that's the only way they can meet each other. What would they write on paper before jumping ? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Puzzle
What is so ridiculous in this. My doubt it do we have to assume that the left and right directions of both the people are same or can we do without that also ? On Aug 7, 11:31 pm, shady sinv...@gmail.com wrote: this is one ridiculous puzzle... this must have been asked to some philosophy student by amazon... On Sun, Aug 7, 2011 at 11:29 PM, Algo Lover algolear...@gmail.com wrote: Two people are travelling through flight. Both have parachute and jump anywhere randomly i.e none of them knows who has jumped where.(Assume there's a big desert and they jump at any random location). Now, both of them have a single piece of paper on which they can write instructions before jumping and that's the only way they can meet each other. What would they write on paper before jumping ? -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Maximum Difference among Adjacent elements on Number Line
given an UNSORTED real number array x1,x2,...,xn, how to find the max
distance of two neighbouring numbers in the number axis. Is there any
method with O(n) time complexity?
see an example
given x[]={2.0,1.0,9.0,-3.5}
then the answer is 7.0, because on the number axis, it is
-3.5,1.0,2.0,9.0 from left to right.
distance between two neighbouring numbers are 1-(-3.5),2-1,9-2.
so the answer is 9-2=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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Intersection of 2 rectangles
Given 2 rectangles not necessary parallel to co-ordinate axis. How would you find if the rectangles intersect and if they do find the intersection points -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Rotate a 2-D matrix by 90 degree inplace.
Can anyone solve this problem without using extra matrix -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
