Source: IITM Friend (who did not want his name to be disclosed). Also read it once in CLR (Introduction to Algorithms)
Given an array of n numbers. Finding minimum takes n1 comparisons. Finding maximum takes n1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n2 comparisons?
Update (11/12/09): Solution by Ameya and Me in comments !!
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Subscribe to:
Post Comments (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this art...

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tos...

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...
yes
ReplyDeletefirst find minimum in n1 comparision,then find maximum out of n number using n2 comparision,total of 2n3 comparision :P
ReplyDelete@jaadu...
ReplyDeleteitne bure din aa gaye tere.. aisa solution dega tu? your good days are gone man!! you dont rock now!! :P
@rohit..
dude... solution??
ya.. u can..
ReplyDeleteuse recursion logic...
and for base case,
when array has length = 2,
u need 1 comparion and not 2 to get min and max. so,
calc(2) = 1,
calc(2^k) = 2* calc(2^(k1)) + 2
it will solve as
calc(2^k) = 2^(k+1)  2  2^(k1)
like calc(4) = 4 not 6
calc(8) = 10 not 14
Not if u have array and random length... just apply this logic on first 2^k numbers in it (for max k)... for remaining, use normal approach...
it will definitely have solution < 2n2
@ameya.. fundoo solution
ReplyDeleteYour solution requires approximately 1.5n comparisons instead of 2n comparisons.
An iterative approach (which is essentially the same) is probably easier to understand:
Break n numbers into pairs of 2.
So, that is n/2 pairs. Find maximum and minimum in each pair. Cost = n/2.
Now given n/2 maximums, find the maximum. Cost = n/2. Given n/2 minimums, find the minimum. Cost = n/2
So, overall cost 3n/2 comparisons. :)
One obvious reasoning can be this.
ReplyDeleteLet say you have parsed till L elements out of N (say, L < N). You have stored a Max and a Min over L elements till now. Now you encounter the (L+1)th. You compare it with Max, If it is greater than or equal to Max, then you don't need to compare it with the Min. So, if you follow this rule throughout the algorithm, you will save at least a computation in (n1/n) fraction of times you solve this problem. You will have 2n  2 computations when the first element is actually the maximum in the array, Else you will save. :)
@pratik at first, I also thought about it the same way as jaadu has written :D
Ameya's solution is more efficient. if N is a power of 2 Ameya's solution uses only N+2 comparisons much less than than 2N2 or 3/2 N if N is large. If N is not a power of 2. Let k is the largest power such that 2^k <N. write N = 2^k + 2^(k1) + p . Here p is definitely less than N/4. Now from the first 2^k numbers we get maximum and minimum in 2^k + 2 comparisons. similarly in 2^(k1) + 2 comparisons we get maximum and minimum of next 2^k1 numbers and using normal approach we get maximum and minimum of remaining p elements in 2p2 comparisons. total number of comparisons so far is 2^k +2^(k1) + 2p +2 = N+p+2. We require 4 more comparisons to get maximum and minimum of whole array. Hence the total number of comparisons is N+p+6 < N+N/4+6 < 3N/2 if N is large.
ReplyDelete