4 ms·
Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x. Solution to problem 2: let x be th
by lllbean 14y ago
Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x.
Solution to problem 2: let x be the deleted number and let y be the duplicated number. Summing the numbers and subtracting the sum from 1 + 2 + 3 + ... + n gives x - y.
Xor-ing the numbers and xor-ing the result with (1 xor 2 xor 3 xor ... xor n) gives x xor y. Now x xor y (expressed as a binary string) must contain at least one 1. So there is some digit where the binary representation of x differs from the binary representation of y. Let this digit be the ith digit.
Let's say that a number is good if the ith digit of its binary representation is a 1. Let's call numbers that aren't good bad. Observe that exactly one of x, y is good, and the other one is bad.
Let S be the number that we get by doing this:
S = 0
for j in 1..n:
if j is good: S = S + j
if j is bad: S = S - j
Let T be the number that we get by doing this:
T = 0
for j in our_list_of_numbers:
if j is good: T = T + j
if j is bad: T = T - j
We find that S - T = x + y or -(x + y). Since x + y is positive, we can find x + y in either case.
We have x + y and x - y, so we can find x and y.
Solution to problem 3: imagine that we have a car, car 1, that has a really big tank with a bunch of gas in it. Put car 1 somewhere on the track and have it drive one complete revolution. The amount of gas G in the tank of car 1 varies over time, but at some point P on the track, G reaches its minimum value. P has to be at a gas station. (Otherwise G would be lower at a point right in front of P.)
If we take our regular car and start it (with an empty tank) at point P, it's pretty easy to see that it'll make it all the way around the loop.
Because if it didn't, then at some point Q it would run out of gas. Q wouldn't be a gas station, otherwise our car would refuel; so there's some point Q' in between Q and the next gas station from Q. Then driving a car from P to Q' results in a net loss of gas. Then when car 1 drove around the track, it should have had less gas at Q' than it had at P. (That's not 100% obvious in the case where car 1 drove past point Q' before it drove past point P, but it follows from the fact that car 1 had the same amount of gas when it finished as when it started.) Contradiction.
Fuck yeah, I'm a badass.
- cncool 14y agoFor question 3, it clearly states two things: "the total amount of gas available at the stations and in the car is exactly enough for the car to drive around the road once" and "the car completes a full circle without running out of gas" Given the first condition, in your solution, at the exact moment the car completes the drive around the track, it runs out of gas. Therefore, it is impossible to complete it without running out of gas.
- deleted 14y ago[deleted]
- cheald 14y ago1) Momentum! 2) The implication of the question is not "can you complete the trip with gas left over", but rather "can you complete the trip". If the requirement is that you must have gas left over, then barring a trick answer, the problem is trivially answerable as "false".
- deleted 14y ago[deleted]
- deleted 14y ago[deleted]
- pantaloons 14y ago1. Not constant space. Not linear time. 2. Not constant space. Not linear time. 3. Looks correct.
- cncool 14y ago1. How is this not linear time?
- drostie 14y agoBecause as the numbers increase, their storage requirement also increases. Suppose you have the array [1, 2, 3, ..., n]. How does storage of that array scale? You need log(n) bits to store the largest element and you need about n elements of that size (at the very least the last n/2 will have the last bit set) -- so you are operating on a data source which has size O(n log n). At least, if n is the above number. Given this, any algorithm which only uses O(n) instructions cannot asymptotically read the whole array, and this presents a fundamental limitation on the problem. Technically, there cannot be a solution better than O(n log n) for this reason -- unless you get lucky and find the duplicated element in the very first O(n) of the array, you will miss it in the last O(n log n) of the array. The larger problem is that there is a fundamental confusion here. Really you should say that the array is some permutation of [1, 2, 3, ... m] and that n = m log m is the input size, and then ask whether algorithms run in linear time relative to n, not relative to m. This allows you to read in the array. You still have the problem that you have storage which grows like 1 + log m, though.
- pantaloons 14y agoThe larger problem is the cult of "Big O" and its use as a form of signalling in interviews. If I wanted to test whether a candidate understood Big O, I'd ask them if there was a difference between O(1) and O(0). What these companies want is to see if the candidate understands program performance in general. Big O is the vogue (in my view misguided) way to do that.
- alexchamberlain 14y agoI disagree. The array is stored outside of your algorithm. The algorithm is constant space.
- panic 14y agoHere's a direct proof for problem 3 that doesn't use any contradiction (perhaps someone will find it clearer). Say you have N gas stations. For any n between 1 and N, say: * f_n is the amount of fuel in the nth station, and * d_n is the distance from the nth station to the (n+1)th. You want to make sure that at each step along your path, you have more fuel than the distance you need to travel. Using our notation, for each step along the path, we want the sum of the f_n so far to be larger than the sum of the d_n. That's the same as saying the sum of (f_n - d_n) should never dip below zero. So how do we show that we can visit all the gas stations while keeping the sum of (f_n - d_n) non-negative? Well, since we have just enough gas to get around the track, we know that the sum of (f_n - d_n) along the entire path is zero. In other words, if we write out the partial sums: S_1 = f_1 - d_1 S_2 = f_1 - d_1 + f_2 - d_2 ... S_N = f_1 - d_1 + ... + f_N - d_N then S_N is zero, since the distances and the fuel amounts cancel each other out. Now look through this list and find the smallest partial sum. Call it S_m. If we change our path to visit gas station 'm' last (and start at station 'm+1'), we get these updated partial sums as we move along our new path (call them U_n): U_1 = f_{m+1} - d_{m+1} U_2 = f_{m+1} - d_{m+1} + f_{m+2} - d_{m+2} ... U_{N-m} = f_{m+1} - d_{m+1} + ... + f_N - d_N U_{N-m+1} = f_{m+1} - d_{m+1} + ... + f_N - d_N + f_1 - d_1 ... U_{N-1} = f_{m+1} - d_{m+1} + ... + f_N - d_N + f_1 - d_1 + ... + f_{m-1} - d_{m-1} U_N = f_{m+1} - d_{m+1} + ... + f_N - d_N + f_1 - d_1 + ... + f_m - d_m Now note that: U_1 = S_{m+1} - S_m U_2 = S_{m+2} - S_m ... U_{N-m} = S_N - S_m U_{N-m+1} = S_N - S_m + S_1 ... U_{N-1} = S_N - S_m + S_{m-1} U_N = S_N - S_m + S_m Since S_N is zero, all the U_n are of the form S_i - S_m (for various i). And S_m is the least partial sum -- that means S_i >= S_m for all the S_i in the list. So each U_n is greater than or equal to zero, just like we wanted. Therefore our last stop should be the gas station with the biggest fuel deficit compared to its distance from the next station (and we should begin our trip at that next station to guarantee we never run out of gas).
- hristov 14y agoAll of your solutions work. I am curious however, are you new to HN or did you start a new ID just so you can brag about how much of a badass you are?