Queue To Do
Created: Oct 24, 2026
Last modified: Oct 24, 2026
TL, DR.
Queue To Do
===========
You're almost ready to make your move to destroy the LAMBCHOP doomsday device, but the security checkpoints that guard the underlying systems of the LAMBCHOP are going to be a problem. You were able to take one down without tripping any alarms, which is great! Except that as Commander Lambda's assistant, you've learned that the checkpoints are about to come under automated review, which means that your sabotage will be discovered and your cover blown -- unless you can trick the automated review system.
To trick the system, you'll need to write a program to return the same security checksum that the bunny trainers would have after they would have checked all the workers through. Fortunately, Commander Lambda's desire for efficiency won't allow for hours-long lines, so the trainers at the checkpoint have found ways to quicken the pass-through rate. Instead of checking each and every worker coming through, the bunny trainers instead go over everyone in line while noting their worker IDs, then allow the line to fill back up. Once they've done that they go over the line again, this time leaving off the last worker. They continue doing this, leaving off one more worker from the line each time but recording the worker IDs of those they do check, until they skip the entire line, at which point they XOR the IDs of all the workers they noted into a checksum and then take off for lunch. Fortunately, the workers' orderly nature causes them to always line up in numerical order without any gaps.
For example, if the first worker in line has ID 0 and the security checkpoint line holds three workers, the process would look like this:
0 1 2 /
3 4 / 5
6 / 7 8
where the trainers' XOR (^) checksum is 0^1^2^3^4^6 == 2.
Likewise, if the first worker has ID 17 and the checkpoint holds four workers, the process would look like:
17 18 19 20 /
21 22 23 / 24
25 26 / 27 28
29 / 30 31 32
which produces the checksum 17^18^19^20^21^22^23^25^26^29 == 14.
All worker IDs (including the first worker) are between 0 and 2000000000 inclusive, and the checkpoint line will always be at least 1 worker long.
With this information, write a function solution(start, length) that will cover for the missing security checkpoint by outputting the same checksum the trainers would normally submit before lunch. You have just enough time to find out the ID of the first worker to be checked (start) and the length of the line (length) before the automatic review occurs, so your program must generate the proper checksum with just those two values.
Languages
=========
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Java cases --
Input:
Solution.solution(0, 3)
Output:
2
Input:
Solution.solution(17, 4)
Output:
14
-- Python cases --
Input:
solution.solution(0, 3)
Output:
2
Input:
solution.solution(17, 4)
Output:
14
We took down a security checkpoint, and now we have to fake the checksum it would have reported. Here's how the bunny trainers work:
workers line up in order of their IDs, with no gaps, and the line holds length workers. The trainers write down every ID
in the line, let it fill up again, then write it down once more leaving off the last worker. Then they leave off two,
then three, until they'd skip the whole line. At that point they XOR every ID they wrote down, and that's the checksum.
# A grid with a triangle inside
length does two jobs at once. It's how many workers fit in the line, so each round is a row of length
consecutive IDs. And since each round leaves off one more worker, there are exactly length rounds before nobody's left.
Picture a length × length grid filled with IDs starting at start: row i (counting from 0)
keeps its first length − i workers. What gets XORed is a triangle.
# The obvious idea
Walk through the triangle and XOR every ID. That's exactly how I solved it at first:
def solution(start, length):
res = 0
for i in range(length):
for j in range(start + (length * i), start + (length * i) + (length - i)):
res ^= j
return res
It works, but the triangle is about half the grid: $\frac{length \cdot (length + 1)}{2}$ XORs.
IDs go up to 2,000,000,000, so with start at 0 the line can be as long as 44,721 (the last ID would be 1,999,967,840).
That's around a billion XORs, which takes Python about half a minute. Way too long for a function that only gets two numbers.
# Pairs that are worth 1
Look at an even number and the one right after it: 6 is 110 in binary and 7 is 111. They only differ in the
last bit, so 6 ^ 7 = 1. That works for any pair that starts on an even number. And since 1 ^ 1 = 0,
two of those pairs cancel each other out.
So to XOR a whole row from a to b, there's no need to go number by number. If a is even, the row splits into pairs, and all that matters is how many numbers there are, which comes down to $(b - a) \bmod 4$: maybe a loose b at the end, maybe a pair left over, maybe both, maybe everything cancels.
If a is odd, set it aside: the rest of the row starts on an even number and fits the table above. XOR a back in and
you get four more cases. For example, the row 21, 22, 23: 21 goes aside, 22 ^ 23 = 1, and 21 ^ 1 = 20,
which is a − 1.
Every row now costs a handful of operations, no matter how long it is. With a 44,721-worker line, that's 44,721 rows instead of a billion XORs, and the answer comes back in a couple hundredths of a second.
# Line them up
Change the first ID and the length of the line. The checked workers are solid, and the ones left off sit after the slash. Pink underlines mark the pairs worth 1, and the loose cells at the edges are an odd start or an even end. Each row shows the value the table gives it, and the checksum is the XOR of those values. Start with the statement's examples, 0 and 3, then 17 and 4, and then try big IDs. The demo caps the line at 8 so it fits on screen.
Checksum: 14
# The code
This was my second version:
xor(a, b) picks the table that matches the parity of a, as a list of four values, and indexes it with
(b - a) % 4.
solution walks the rows: row i starts at start + length * i and ends length - i
IDs later. It XORs what xor returns for each row into the result.
def xor(a, b):
if (a % 2 == 0):
xor_rotation = [b, 1, b + 1, 0]
else:
xor_rotation = [a, a ^ b, a - 1, (a - 1) ^ b]
value = xor_rotation[(b - a) % 4]
return value
def solution(start, length):
res = 0
for i in range(0, length):
res ^= xor(
start + (length * i),
start + (length * i) + (length - i) - 1
)
return res
# Variant: one table instead of two
There's a more common way to write the same idea. Start by XORing everything from 0: call it $f(n) = 0 \oplus 1 \oplus \dots \oplus n$. Starting from 0, the pairs always begin on an even number, so f only needs one table:
To get a row from a to b, combine f(b) ^ f(a - 1). Everything from 0 to a − 1 shows up in both,
and since x ^ x = 0, it cancels out and leaves exactly a through b. It's the same trick as getting
the sum of a range by subtracting two running totals, except here the "subtraction" is XOR too. For the row 21, 22, 23:
f(23) = 0 and f(20) = 20, so the row is worth 0 ^ 20 = 20, just like before.
def f(n):
"""0 ^ 1 ^ ... ^ n"""
return [n, 1, n + 1, 0][n % 4]
def xor_range(a, b):
# 0..a-1 appears in both and cancels out
return f(b) ^ f(a - 1)
def solution(start, length):
res = 0
for i in range(length):
a = start + length * i
res ^= xor_range(a, a + (length - i) - 1)
return res
One detail: when a is 0, it calls f(-1). In Python, -1 % 4 is 3, so the list returns
0, which is exactly what it should be. In Java or C#, where % of a negative number stays negative, you'd have
to handle that case separately.
# Wrapping up
The statement makes it sound like you have to simulate the checkpoint, and simulating it is exactly what doesn't scale. The trick is that XOR over consecutive numbers repeats every four, thanks to those even-odd pairs. When a calculation over a range of numbers looks expensive, it's worth checking whether it follows a pattern you can jump straight to.