Remix.run Logo
repiret 2 days ago

The code in the article is written in Python, whose only for loop is for-each. It is 2N XOR operations, regardless of whether you use one or two loops.

I probably would have written it with a single loop, using the `enumerate` iterator adapter. But in Python, two loops is almost certainly more efficient.

Dylan16807 2 days ago | parent | next [-]

You can loop over the range and then do result ^= i ^ A[i]. If adapters are slow you don't need them here.

Having only one loop gives you a better memory access pattern, because it's 2 XOR operations in between each memory access. Two loops is the same number of instructions, but it spends one loop ignoring memory and then another loop doing rapid-fire memory accesses. In python there's enough overhead that it's unlikely to matter. But in a faster language running on a busy machine that could make a real difference.

sfn42 2 days ago | parent | prev [-]

for i in range(n - 1):

Is pretty much a standard for loop. Between that and

for n in numbers:

You can do pretty much the same things as a more conventional language.

You could also solve it pretty simply like this:

expected_sum = (n * (n + 1)) / 2

missing_num = expected_sum - sum(numbers)

This only iterates the list once. This would probably be my solution if I was given this task in an interview.