# Logic Interview Questions

interview questions shared by candidates

## Logic Interview Questions

### Linux Kernel Engineering at Google was asked...

You have 25 horses, what is the minimum number of races you can find the top 3. In one race you can race 5 horses, and you don't have a timer. 28 AnswersI don't know, but Google it, you'll find the answer. Once you know it, it's obvious. 12 Probably 8. First answer: at least 5 (you have to look at every horse). Second answer: 11. You can race five horses, replace 4th and 5th place horse by two horses from pool of horses that haven't raced, and continue doing this until all horses have raced. Since there are 25 horses, you need 1 race for the first five horses and 10 to go through the remaining 20. Third answer: 8. Round 1 (5 heats) : Race horses in heats of five. Eliminate all 4th and 5th place horses. (15 horses left) Round 2 (1 heat): Race winning horses from every heat. Eliminate 2nd and third place horses that lost to horses in round 2 that came third or worse. (7 horses left). Round 3 (1 heat): Pick any five horses. Race them. Eliminate bottom two and replace with remaining two horses. (5 horses left) Round 4 (1 heat): Eliminate bottom two. Note: after round 2 it may be possible to use some interesting decision tree mechanism to determine the three fastest horses using fewer horses per heat but you still need two heats to do that. This problem assumes horses don't get tired, no ties are possible and a horse's speed is deterministic race after race after race. Good assumptions for brain teasers, but not for real life. Show More Responses Actually, should be 7. Forgot that after round 2 you can eliminate one more horse leaving you with 6 horses, one of which (the winner of the second round), is the fastest horse of them all. One more race with the five horses not No.1 and you pick the top two. 6. First round consists of 5 races of 5 horses. Pull aside the winner of each race in the first round for the final heat and eliminate the bottom 2. 8. Run 5 races of 5 horses. (5) Put all the 3rd place horses in a race, winner is 3rd fastest. (6) Put all the 2nd place horses in a race, winner is 2nd fastest. (7) Put all the first place horses in a race, winner is fastest. (8) The third place horse was beaten by one of the 2nd place horses. So third stays in third. Same for the second place horse. chzwiz, r u sure u r not high? B, what happened in round 2? why 8 horses suddenly get eliminated by 1 race? again, do u know what you are smoking? oh, forget J,..... just speachless 7. chzwiz, your answer is incorrect. One of the first or second place horses could be 2nd fastest and/or 3rd fastest. I drew a grid to visualize the problem. First, run five races to establish 5 groups of internally ranked horses, and you can of course immediately eliminate 4 & 5 of each race. 1 2 3 x x 1 2 3 x x 1 2 3 x x 1 2 3 x x Then race 1st place horses, eliminate 4 & 5, and those they beat earlier. You can also eliminate the horses #3 beat, and the 3rd place horse from #2's first race. 1 ? ? X X 2 ? X X X 3 X X X X X X X X X X X X X X You know #1 is fastest. Race the remaining horses (2, 3 and ?'s), and the top two are 2nd and 3rd. After reading the above answers, this is the same as B's revised answer, but I found it easier to explain/visualize with the grid. @brad ... but isnt dat v dont have timer to know d ranking ... or my assumption is wrong?? I thought v know only 1 result of every race .. i.e. top 1 Spawn, it's true that you don't know timings, but you do know RANKINGS. I don't see errors in logic with each answer above. They may claim to discover the answer with fewer races, but they have too many assumptions or errors to be correct. To do this optimally and without any potential error, you must eliminate as many correctly placed horses as possible and eliminate the maximum number of non-win/place/show horses each round. Round 1: (Races 1-5) You must start with 5 heats @ 5 horses apiece. The non-Win/Place/Show horses of each round have been eliminated, leaving 15 horses. Round 2: (Race 6) You then race the top finishing horses against one another, leaving you with your overall fastest horse. We now have the Win horse, leaving only Place and Show as unknowns. This also eliminates the bottom two horses, leaving 2 horses from this race. There are also only two more unknown horses. Race 7) You may race the Place horses against one another. Only two survive this race, since we know that each of these horses can place 2nd at best. This leaves 2 horses from this race. (Race 8) You may also race the show horses of each round. Since they each have been beaten by two other horses in Round 1, only the 1st place horse of this round survives as the potentially 3rd best horse. This will leave 1 horse in this race to battle for the 2 remaining spots. Round 2 leaves 2 Horses (Race 6) + 2 Horses (Race 7) + 1 Horse (Race 8) = 5 Horses, for 2 unknown spots. Round 3: (Race 9) We can now have the final 5 horses race for the remaining two spots leaving us with the undisputed 2nd and 3rd places. Here is a more complex scenario below in which the top 2 horses come from the same original race and the later races are full of lame horses. Many of the solutions above do not address those problems. Each # is a horse, named by it's inherent ranking. X signifies 'eliminated horse' Race1 R2 R3 R4 R5 1-->R6 3-->R6 11-->R6 16-->R6 21-->R6 2-->R7 7-->R7 12-->R7 17-->R7 22-->R7 4-->R8 8-->R8 13-->R8 18-->R8 23-->R8 5X 9X 14X 19X 24X 6X 10X 15X 20X 25X Round 2: Race 6 (Winners) Race 7 (Places) Race 8 1 -->1st Place 2-->Race 9 4-->Race 9 3 -->Race 9 7-->Race 9 8X 11-->Race 9 12X 13X 16X 17X 18X 21X 22X 23X Round 3: Race 9 2P 3S 4X 7X 11X First Place = 1 Horse -- Race 6 Winner Second Place = 2 Horse -- Race 9 Winner Third Place = 3 Horse -- Race 9 2nd place To fix the formatting issues that appeared as spaces are eliminated above-- Race1________R2___________R3___________R4___________R5____ _1-->R6_______3-->R6_______11-->R6_______16-->R6_______21-->R6 _2-->R7_______7-->R7_______12-->R7_______17-->R7_______22-->R7 _4-->R8_______8-->R8_______13-->R8_______18-->R8_______23-->R8 _5X__________9X___________14X__________19X___________24X _6X__________10X__________15X__________20X___________25X Round 2: Race 6 (Winners)__________Race 7 (Places)__________ Race 8 1 -->1st Place_____________2-->Race 9______________4-->Race 9 3 -->Race 9_______________7-->Race 9 _____________ 8X 11-->Race 9______________12X____________________13X 16X_____________________17X____________________18X 21X_____________________22X____________________23X Round 3: Race 9 2P 3S 4X 7X 11X Less ascetically pleasing than the original, but it will suffice. Show More Responses This problem can be reduced to (viewed as) multiway mergesort: 1) split the horses into groups of five as if we had five files to sort 2) do a multiway mergesort but instead of sorting all horses, stop as soon as you get the top 3 We need one race per group to sort them (5 races total). And 3 more races to get the top 3. We will need 8 races. The interviewer might have been looking whether an applicant was able to spot this relation to algorithms or not. But if this was a brain teaser instead, maybe the answer is less than 8. The answer is definitely 7, here is a fantastic explanation: http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/ Randomly race the horses 5 times and keep a winner's bracket. The 6th race will determine the fastest horse. This is trivial. The 2nd and 3rd fastest could be in the winner's bracket or they could be the 2nd or even 3rd fastest in one of the losing brackets. Then we have to race 2nd and 3rd place from the winners bracket as well as from each original bracket, which had 5. This means we have 12 horses to try. Randomly keep 2 horses out and race 5v5. Keep the top two horses from both. We have 6 horses now. Race 3v3 and keep the top two, leaving 4 horses. Then race these. I count 11? Brute force divide and conquer solution = 18 races. Just be aware of the brute force solution in case there's restriction where we can't use the memory to save the first 3 places. Those who want a system that averages that fastest solving time, the answer will be 7 races.. Those gamblers who want an algorithm that gives the fastest possible solving time (all though sometimes it WILL take longer) the answer is 6. Race 1-5: First 5 races of five.. We randomly seed with no overlaps.. we use this to eliminate the bottom two from each race. I am going to use a two digit number labeling system where the first digit is which race in heat one they competed in and the second digit is which place they obtained in that heat.. These are the horses we have left: 11 12 13 21 22 23 31 32 33 41 42 43 51 52 53 Race 6: We have the winners from each heat compete, and for ease of explanation lets say that they ranked 11, 21, 31, 41, 51.. Now we know that 41, 51 and all the horses slower than them (their heats) are out.. also, we know that any horse slower than 31 is out (ie. 32 & 33), and we know that any horse that is at least two horses slower than 21 is out (ie 23). This leaves 11, 12, 13, 21, 22, 31.. 6 horses. Possible rankings: 11 12 13 21 22 23 31 32 33 Race 7 Rank 1 is already known.. and we just need to know how to organize 12, 13, 21, 22, and 31.. And look at that!! that's 5 horses! We race those 5 and the top two receive the overall rank of 2nd and 3rd. 5 races in round one, 1 race in round 2, 1 race in round 3.. it took us 7 races.. Option two: 6 Races Now, an alternate answer.. when we read "What is the minimum number of races to find the top 3 horses" we can interpret that maybe they don't care about this method working every time.. instead they want to hit up the Vegas Casinos and test their luck, and maybe save some track time.. If i was a gambling man.. i would race the first group of those that i thought looked the strongest.. I would eliminate 2 in that race (we are now down to 23 horses).. and then race the 3rd fastest multiple times and hope that he gets first in the remaining races, thus eliminating 4 horses each time. This is going to be painful for the horse that placed 3rd in heat one. Race 1: Eliminate 2, 23 horses remaining Race 2.. Eliminate 4, 19 horses remaining Race 3.. 15 horses Race 4.. Eliminate 4, 11 horses Race 5.. Eliminate 4, 7 horses Race 6.. Eliminate 4, 3 horses.. The original top 3 from Race 1. So using method 2, we completed this race in 6 races instead of 7! I messed up the possible ranks after race 6.. That should have read.. 11 12 13 11 12 21 11 21 22 11 21 31 Please forgive me. Brad's explanation is the perfect one. All other explanations are junk and impossible to read and follow. Round1: (5 groups) remaining horse 15 Round: (1 groups). Topper from each heat Round: (1 gounds). Forget about the 4th and 5th Heat horses (becoz their toppers are at last place) go to the 3rd position 6 races as the 25 horses are divided into 5 groups each grouping 5 horses in each group , then the winner from each group would be 5 then there should be last n final race to find the first , second and third placed horse . in this way we can find our top 3 horses :) It should be 11. In each race you can only eliminate 4th and 5th place simply because there's a chance that the top 3 in that single heat are the 3 fastest of all the horses. So each race you can select 5 random horses each race or keep the top three in the following race, the outcome is the same. Show More Responses I get 8 races to guarantee you get the top three. 5 races of 5 to get the fastest horse from each group. 1 race to determine the fastest overall. The second fastest horse can be in the group (x) that produced the fastest, 1 race with the remaining 4 fastest from the other groups and the second fastest from group x. That race will produce the second fastest overall guaranteed. 1 more race with the 3 or 4 from the original winners and the replacement from the group that produced the second place horse. That makes 8 races. I dont get it.. It shoudl be five races right? U will know how long each horse takes to cover same distance. Pick the three that took shortest. Y need more rounds? If u down vote my answer, u have the obligation to explain why 😜 Answer is 6. You will have 5 races and 5 winners. Next race with 5 winners is the 6th race and you get top 3. You're welcome. It would be 7, mainly because since there only 5 racers each round, then it would be tournament style. As you can tell, tournament style never determines the rankings in the short term. (Imagine if a new tennis player played against Roger Federer and he loses. He's not bad, he's just really unlucky haha) So in order to determine the answer, you would have to use massive logic and reasoning. First step is obvious: you get 5 sets of horses to race through 5 races. So the number is already at 5. We get the top horse in each one and note them. However, one problem is that you have to consider if fastest horses could lie all in the first, second, third, fourth, or fifth group. But we can't determine that yet, so let's race one more time with the winners of each race. Second step: Race with each winner from their groups. That makes 6 total races so far. Ok, now we can get somewhere with this. So now, its a question of which horses we can eliminate to determine the next race. Who can we eliminate though? Well, we can get rid of: - All the horses in the group with the last race that were 4th and 5th place. This makes sense since if the winner of their groups only made 4th and 5th place in the tournament style race, then they are definitely not the fastest horses. 15 horses remaining. - Well, we can also get rid of the last two horses of each group since we are only looking for the top 3. 9 horses remaining. - We also can get rid of the first place winner since we already know he is definitely the best. 8 horses remaining. - Since we already determined who the fastest horse is, now we have to determine who the second and third fastest horse can be. In that case, the second place horse from the last round can get rid of the third horse of that group, since he definitely has no shot of being the first or second fastest horse of this new race. Also, in the third group, we can get rid of the second and third horse in the group due to the same reasoning above. 5 horses remaining. Oh wow! We now have 5 horses left! This means we can just have a clean race and find the second and third fastest horse. So overall, the answer is 7 races! 7 |

25 racehorses, no stopwatch. 5 tracks. Figure out the top three fastest horses in the fewest number of races. 9 AnswersWe can do it in seven races, we'll call them races A-F. For notation, we'll say that the Nth horse in race X is called X.N. Races A-E: Divide the horses into 5 groups of 5 each such that each horse races only once. We can eliminate the slowest 2 horses in each of the five races because there are definitely 3 horses faster in each case. As a result, we eliminate 5x2 = 10 horses: {A.4,A.5,B.4,B.5,C.4,C.5,D.4,D.5,E.4,E.5} Race F: Race the fastest horses in each race A-E: {A.1, B.1, C.1, D.1, E.1}. To simplify notation, we'll label F.1 as horse A.1, F.2 as horse B.1, and so forth. That means the winner of this race is A.1, and it is the fastest horse of all. We don't have to race A.1 anymore. We can eliminate D.1 and E.1 = 2 horses. Because they are not in the top 3. As a result, we know that all remaining horses from D and E are eliminated. This is D.2,D.3,E.2,E.3 = 4 horses. We know that A.1,B.1, and B.2 are all faster than B.3 (and similar for C.3) so they are not in the top 3.We can eliminate B.3 and C.3 = 2 horses. Finally, we know that A.1 is faster than B.1, which is faster than C.1, and thus C.2, so we can remove C.2 = 1 horse. Race G: We have removed 19 horses from competition and are sure that A.1 is the fastest horse of them all. This leaves just 5 horses: {A.2,A.3,B.1,B.2,C.1}. We race them and select the top 2 to join A.1 as the top 3 fastest horses. just run them all on the one track :) one race, and you get your 3 fastest horses in one go........or am I missing something! 6 races. Divide 25 horses into 5 groups. Each group races and the fastest is selected. The winner of each of the 5 races all race together. Pick Top 1,2 and 3. My only concern: Could the answer be this simple? Show More Responses B, you're mistaken. Imagine the top three fastest horses are Santa's Little Helper, Yojimbo, and I'm Number One. By random luck, in your first race, the five random horses you choose includes all three of those. I'm Number One wins and goes on to the final race; the other two do not. 8 5 top horses from each race of 5 races (25 / 5) 5 top contenders race; 1 wins--that's one top horse (5-1) 4 remaining top horses race, one wins; that's 2 top horses (4-1) 3 remaining top horses contend; winner is #3 That's 3 top horses from 8 races Race#1 Race#2 Race#3 Race#4 Race#5 A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Race#6 A1 B1 C1 D1 E1 Let's Say ranking 1st 2nd 3rd 4th 5th Eliminate D1 E1 D2 E2 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Left with B1 C1 A2 B2 C2 A3 B3 C3 Eliminate C3 as there are more than three faster horses C2, C1, B1, A1 Eliminate C2 as there are three faster horses C1, B1, A1 Eliminate B3 as there are three faster horses B2, B1, A1 Left with 5 horses for Race#7 B1 C1 A2 B2 A3 So 7 races 7 races. put 25 horses in 5 group. and we will have 5 sorted list of horses in each group. put 1st place horse in each group, and we will have a sorted list X. X_1 is the 1st place horse, and X_2 is 2nd place horse's candidate, X_3 is 3rd place's candidate. 2nd place horse in X_1's group is candidate for 2nd place, 3rd place one is candidate for 3rd place. and 2nd place horse in X_2's group is a candidate for 3rd place. that's 5 horses in total, 2 from X_1's group, 2 from X_2's group, X_3. race them, and 1st place is 2nd place, 2nd place is 3rd place horse. 8 the answer is one race as the question doesn't specify all the horses have to run in separate races. |

You are in a room with 3 switches which correspond to 3 bulbs in another room and you don't know which switch corresponds to which bulb. You can only enter the room with the bulbs once. You can NOT use any external equipment (power supplies, resistors, etc.). How do you find out which bulb corresponds to which switch? 6 AnswersTurn on 2 switches. Turn one switch off after a few minutes. Enter room with bulbs. The bulb that is on is the only switch that is on. The bulb that is off but hot, is the switch that has been turned off. The bulb that is off and cold is the third switch. Turn on switch A for 1 minute. Turn it off. Turn on switch B. Enter the room with the bulbs. The hot bulb is A The lit bulb is B The dark bulb is C Turn switch A leave it on for 1/2 minutes and turn it off then turn on switch B. Now goto the room, the one Hot is A, Cold(or not Hot) is C, the bulb thats on is B. Show More Responses The answers here all have two assumptions which are unwarranted. 1. Why do you think the light emits heat? 2. Why do you think you can touch the bulbs? (3. If you're never going to enter the room again what's the point of knowing which switch goes with which light?) The best you can do is reduce to guessing one of two bulbs. RE: Objection 1. I guess you've never touched the outside of a light bulb after it's been on for awhile. The filament gets hot-it glows, the light we see is that glowing-the heat from from the glowing filament transfers to the glass-the glass is hot. 2. Why not? This is an exercise to demonstrate problem-solving ability, not a "MacGyver" episode. Who's to say the candidates didn't ask about the room's dimensions or where the bulbs were located, or that assumptions could be made in order to formulate an answer? 3. I think you missed the point of the question. 4. Sheesh. 3. Yes, Objection, I did see that I entered "3." on here a second time. BTW, I'm not returning to this forum again, so any reply/retort/threat won't be seen by me. Good luck in your job hunting. |

### Senior Software Engineer at Microsoft was asked...

Given a set of people, one of them is a celebrity. You have a 2D array which describes which people know each other, that is [N, M] is true if N knows M. The celebrity will not know anyone (except them self) and everyone will know the celebrity. Find an order N algorithm to find the celebrity. 5 AnswersDon't think there is an O(n), but O(n*m) yes. The key here is that the celebrity knows nobody AND everybody knows the celebrity. So for each iteration, you can rule out 1 person. [Notation: A->B -- A knows B] If A->B then A is not the celebrity .. rule out A Next check would skip B->A since we don't care if B->A etc It is not so simple. You can construct a matrix of relationships to defeat this algorithm. For example, start with A knows B. Then check if B knows C, and say answer is false. Then check B -> D, answer is false. And so on. That's O(N) operations. B looks like a good candidate. But then you check B-> A, you get true, so after all that work B is ruled out. Need to examine C now. Same thing. You end up checking perhaps half of all possible pairs, that's O(N^2). Show More Responses How about constructing a graph with edges between who know each other.. and then checking if target is reachable.. http://courses.cs.vt.edu/~cs5114/spring2010/notes.pdf |

If you have a three gallon jug and a five gallon jug No marks on either one The goal is to fill the five gallon jug with four gallons of water How is this accomplished? 5 AnswersTake 5 gal. and pour into the 3 gal. The 5 now has 2 gal. Empty the 3 gal, and pour the remaining 2 gal into the 3 gal. Fill the 5 gallon and pour 1 gal. (which is the remainder of the space in the 3 gal.) This gives you 4 gal. that was from die hard 3. 1) fill up the 3 and pour it into the 5. 2) fill up the 3 and fill up the rest of the 5. that leaves 1 in the three. 3) dump out the 5. 4) pour the 1 that's left in the three into the 5. 5) fill up the 3 again and pour it into the 5. see - easy peasy. might be a bit rougher if solving it is necessary to stop a bomb from blowing up the city. mclain and samuel L got it done. 1) Fill up half of 5 gal (2.5 gal) from 3 gal jug 2) Fill up half of 3gals jug(1.5 gal) and pour into 5gal jug 2.5 + 1.5 = 4gal Show More Responses Die Hard 2 also has the solution to this question. there are actually 4 die hards, which is why you two are confused. 1. the classic big LA building he runs through glass 2. the airport based one 2*. the new york fed gold gets stolen (die hard with vengence) -- THIS is the one with the water puzzle. 3. the newest die hard where the stop lights get taken over etc, live free die hard i think |

### Senior Software Engineer at Oracle was asked...

Considering a 2-dimension matrix that can only be traversed by 1 adjacent position at a time and never diagonally. Create an algorithm to traverse that matrix from its upper-left corner to its lower-right corner using the shorter possible path in the most efficient way. 5 AnswersThis is a very interesting problem. Although I knew immediately that I had to use recursion to effectively traverse the matrix and eventually got a working algorithm, the catch to make the algorithm much more efficient is to traverse the matrix backwards. How back traverse make the algo efficient? Why not just go all the way down then all the way right? Without diagonal moves the path length is fixed. Unless they provide a different definition for 'shortest length' Show More Responses For a thinking outside the box answer.... assuming the set is closed for indexing, go up -1 and left -1. I guess it's the traversal of a graph's depth first search (DFS) using Adjascent matrix... |

Scenario: You have 8 golf balls and 1 is heavier than the 7 others. All you have is a balance used in chemistry classes. What is the shortest number of times you could measure the golf balls to find the heaviest ball? 5 AnswersYou have to keep in mind that you're dividing up the balls. They try to confuse you, but just ignore the people and stick to your intuition. The quickest way to discover the heaviest ball was in 2 steps. i would say three. you could put 4 balls on each side and then take the heavier side. split that group into two balls on each side. then lastly split that group to have one ball on each side. Show More Responses 2 steps. 1. Put 3 balls on each side of the scale measure( [123], [456] ) If each group of 3 is equal: 2. Place the remaining two balls on the scale - measure( [7], [8] ) If each group of 3 is not equal: assuming [123] is heavier than [456] 2. Take 2 balls from the heavier group from step 1 and place them on the scale. measure( [1], [2] ) If they are equal then [3] is the heaviest 3 v. 3 Case 1: Heavier ball lies within the first 3v3 weighing. Weigh 2 of the balls on the heavier side. Either one is heavier or they balance. If they balance, then it's the 3rd one we didn't weigh. Done. Case 2: 3v3 balances. Then the heavier ball lies within the other 3 not weighed. Weigh 1v1, either it balances or it doesn't. If it doesn't, we're done because we can see that one side is heavier. If it does, then it's the third one not being weighed. Minimum amount of weighings is 2. |

We have a pond containing a single bacterium. The number of bacteria double every 5 minutes, and the pond is full of them in 24 hours. If we started with the same pond but two bacteria, how long will it take to fill the pond? 4 AnswersI struggled with this a bit and got close. I believe answer is: 23:55 This is a clear case of Geometric progression. Find the nth term Tn1 = a*r^(n-1). where n = (24 * 60)/5,a = 1 and r=2. when the initial value (a) = 2, the values become n = ?, a = 2 and r = 2. Since Tn1 = Tn2, Equate the RHS of both the equation. Since the base are equal, equate the powers, doing so will give the n value. When n is convert into minutes one get 23 hrs 55 minutes. this is easy, you don't need all the math. The pond was half full five minutes before, so it's 23:55 Show More Responses The first pond started with 1 bacterium and doubled to 2 in five minutes. Therefore, the second pond will take 5 minutes less than the first to be full. ie: 23:55 |

There is a body of water that starts with 1 square unit, and doubles in size every day (2 units after 2 days, 4 units after 4 days). It takes 100 days to fill up. How many days would it take to fill if you started with 2 square units? 6 Answers100 - 1 = 99 days This question is phrased incorrectly. I think you meant "4 units after 3 days". Which makes your answer wrong as well. This is not helpful at all. if you start with 1sq unit - lets say you end up with 'x' amount to fill up - takes 100 days if you start with 2 sq unit - you will have to fill up '2x' amount thus it will take - 200 days. Show More Responses Starting with 2 square units at time t=0 is like 1 square unit at t = 1. [this logic is the key to answering the question]. Now let's do the first few cases. t = 0: size = 1+1 = 2 t = 1: size = 2(1+1) = 2+2 = 4 = f(2) in the 1 unit case. Pretty easy to see it only requires 1 time period less from here. The OP was right. 1 day less that is 99 days. It is still 100 days. Starting from 2^0, and going all the way to 2^100, the reservoir has a capacity of 2^101 - 1 units. Now in the second case, starting from 2^1, in 99 days there will be 2^101-2 units of water in the reservoir, which is one unit short of the capacity of the reservoir. So we need the 100th day to fill it up! |

Sequence of numbers in random order and 1 of them is missing how to find that out... 5 AnswersN(N+1)/2 - sum of the input = missing number It isn't stated that sequence starts from 1. The sequence could be 8,9,5,6! If the sequence is guaranteed to contain only positive integers, it can be done like so: Read in the sequence, noting the MIN and MAX numbers. The sum IF it started from 1 would be MAX(MAX-1)/2. The sum of the 'missing' numbers (from 1 up to where the sequence actually starts) is (MIN-1)*MIN/2. The missing number is given by taking the difference between the two: X = [MAX*(MAX-1) - (MIN-1)*MIN]/2. Show More Responses Oops, in addition to what I put above there is a final step to get the actual answer. The missing number is equal to X minus the sum of the numbers given. You can graph them similar to a convex hull question. If all nodes were there the sequence would be increasing on some percentile or relative like amount. The missing node will yield an abnormality in the changes in slopes between each node. The only assumption you would have to make, which in all honesty just has to be accepted is that its not the first or the last element that's missing. |