Abstract / Summary

Given a list of integers, compute the xor of each number with its neighbor and return the list of results.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 80% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method that determines whether a binary array can be reconstructed from a given “derived” array. The algorithm explores the two possible values for the last element of the original array (0 or 1) and checks if a consistent reconstruction exists for each case.

Core Logic

The method begins by iterating over the two candidate values for the final element of the original array. For each candidate, it initializes a variable x with that value. It then processes every element d in the derived list, updating x with the XOR of the current x and d. After the loop, the method compares the resulting x with the initial candidate. If they match, a valid original array exists and the method returns True. If neither candidate yields a match, the method returns False.

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        # try 0 and 1 as values for derived[-1]
        for start in (0, 1):
            x = start
            for d in derived:
                x ^= d
            if x == start:
                return True
        return False

Step-by-Step Walkthrough

The outer for loop selects the two possible values for the unknown last element of the original array. The inner for loop accumulates the XOR of all elements in derived starting from the selected candidate. The final if statement checks whether the accumulated XOR brings the value back to the original candidate, which indicates that the XOR relationships encoded in derived are internally consistent for that starting value.

Edge Cases Handled

When derived is empty, the inner loop does not execute, leaving x equal to the initial candidate. The subsequent comparison x == start therefore succeeds for the first candidate, and the method returns True. This correctly reflects that an empty derived array corresponds to a trivially valid original array.

If derived contains values other than 0 or 1, the XOR operation still produces a deterministic result, and the algorithm will correctly determine whether a consistent reconstruction exists for the two possible starting values. The method does not assume any particular range for the elements of derived, making it robust to unexpected inputs.

Performance Optimizations

The algorithm processes the derived list at most twice-once for each possible starting value. It uses a single integer variable x to hold the intermediate XOR result, avoiding the allocation of auxiliary data structures. The early return statement ensures that the method exits as soon as a valid reconstruction is found, preventing unnecessary work when the first candidate succeeds. This in-place accumulation and immediate exit strategy keep the runtime minimal while maintaining clear and concise code.

Imagine you are playing with a row of light switches. Each switch has a special buddy next to it, and they decide if the next switch should be flipped on or off based on a secret rule. You have a list that tells you every time the switches flipped or stayed the same, but the original positions of the switches are hidden.

This code acts like a detective trying to figure out if that secret arrangement of switches is actually possible. It starts by making a guess about the very first switch. It says, what if this one started as a zero? Then it follows the trail of clues in the list to see where the last switch ends up. If the last switch lands back on a zero, then the guess was perfect and the arrangement works. If that guess does not work, it tries starting with a one instead to see if that leads to a matching finish. If either guess ends up matching the start, the puzzle is solved.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java			Python		C++			TS
	WalkCCC		Java			Python		C++
	leetcode.ca	JS	Java	Rust		Python		C++	C#	Go	TS
	Progiez		Java			Python		C++
github	charles-wangkai		Java
	everthis	JS
	fartem				Ruby
	fsq			Rust
	JoshCrozier	JS
	lkwq007					Python
	Shamik07						Dart
	varunu28		Java
	withaarzoo							C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	Rust
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
varunu28	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality