Last Car in the Garage
A small parking garage logs a ticket number at the gate twice for every car: once when it drives in and once when it drives out. The log is one long list of ticket numbers, in no useful order, because cars come and go all day.
At closing time exactly one car is still inside, so exactly one ticket number shows up only once. The attendant wants that number, and the gate computer is tiny: it can read the log once but has almost no spare memory.
Your task
Write carStillInside(log). Every ticket number in log appears exactly twice, except one that appears exactly once. Return that number.
Aim for one pass over the log and O(1) extra memory: no map, no set, no sorted copy.
carStillInside(log: int[]) → int
Examples
log = [512, 87, 340, 87, 512]
340
512 came in and went out. So did 87. 340 appears only once, so that car is still inside.
log = [9, 4, 4, 2, 9]
2
The two 4s sit next to each other, but the two 9s and the lone 2 do not. Do not assume partners are neighbours. The answer is 2.
Constraints
- 1 ≤ log.length ≤ 30,001, and log.length is odd
- 0 ≤ log[i] ≤ 1,000,000,000
- Exactly one number appears once. Every other number appears exactly twice.
Start with brute force
Count every ticket in a hash map and return the one with count 1. That is O(n) time, but it stores up to n / 2 numbers, which the gate computer cannot afford. Checking each ticket against every other one uses no memory but costs O(n²): with 30,001 entries that is about 900 million comparisons.
Sorting and then comparing neighbours in steps of two works with little memory, but it still costs O(n log n) and needs a sortable copy or permission to reorder the log.
Hints
0 of 4 shown- Hint 1
Forget memory limits for a moment. What is
x XOR xfor any numberx? And what isx XOR 0? - Hint 2
XOR of a number with itself is 0, and XOR with 0 changes nothing. Also, XOR does not care about order:
a ^ b ^ aequalsa ^ a ^ b. - Hint 3
So what happens if you XOR every ticket in the log together? Each pair cancels to 0, wherever its two halves sit. What is left?
- Hint 4
Start with
result = 0and XOR in every number of the log. The pairs cancel out, andresultends up holding the one ticket with no partner.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
XOR compares two numbers bit by bit and gives 1 where the bits differ. Two facts do all the work here: x ^ x = 0, and x ^ 0 = x. Order does not matter, so every pair in the log cancels out no matter how far apart its halves are.
Trace [9, 4, 4, 2, 9] in binary:
0 ^ 9=0000 ^ 1001=1001(9).9 ^ 4=1001 ^ 0100=1101(13).13 ^ 4=1101 ^ 0100=1001(9). The 4 is gone again.9 ^ 2=1001 ^ 0010=1011(11).11 ^ 9=1011 ^ 1001=0010(2). The 9 cancels too. Answer: 2.
The middle values (13, 11) look like nonsense, and that is fine. Only the final value matters.
function carStillInside(log) {
let result = 0;
for (const ticket of log) {
result ^= ticket; // pairs cancel: x ^ x = 0
}
return result;
}def car_still_inside(log):
result = 0
for ticket in log:
result ^= ticket # pairs cancel: x ^ x = 0
return resultRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.