What is the brute force approach and complexity for Decode XORed Array?

For each position, try candidate values until arr[i] ^ candidate equals encoded[i] with time complexity O(N · 2^B) and space complexity O(1).

What is the optimal approach and complexity for Decode XORed Array?

arr[i + 1] = arr[i] ^ encoded[i], one step per position with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Decode XORed Array?

Look for key signals in the prompt: "encoded[i] = arr[i] ^ arr[i + 1]" indicates An XOR of two neighbours. XOR undoes itself, so one neighbour gives the other.; "first is given" indicates There is a starting value, so we can walk forward from it one step at a time.; "return the original array" indicates The output has n = encoded.length + 1 values, one more than the input..

Decode XORed Array

Easy·LeetCode #1720 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

A hidden array arr has n non-negative numbers. It was turned into a shorter array encoded, where each entry is the XOR of two neighbours in arr: encoded[i] = arr[i] ^ arr[i + 1].

You get encoded and the first value of the hidden array, first (which is arr[0]). Rebuild and return the whole array arr. The answer is always unique.

Input

encoded, an array of length n − 1, and first, which is arr[0].

Output

The hidden array arr, which has length n.

Example 1

Input: encoded = [1, 2, 3], first = 1

Output: [1, 0, 2, 1]

1 ^ 0 = 1, 0 ^ 2 = 2 and 2 ^ 1 = 3. These match encoded, and arr starts with first = 1.

Example 2

Input: encoded = [6, 2, 7, 3], first = 4

Output: [4, 2, 0, 7, 4]

Every neighbour pair XORs to the matching encoded value: 4 ^ 2 = 6, 2 ^ 0 = 2, 0 ^ 7 = 7 and 7 ^ 4 = 3.

Constraints

• 2 ≤ n ≤ 10^4
• encoded.length = n − 1
• 0 ≤ encoded[i] ≤ 10^5
• 0 ≤ first ≤ 10^5

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“encoded[i] = arr[i] ^ arr[i + 1]”

→ An XOR of two neighbours. XOR undoes itself, so one neighbour gives the other.

“first is given”

→ There is a starting value, so we can walk forward from it one step at a time.

“return the original array”

→ The output has n = encoded.length + 1 values, one more than the input.

Approach Complexity Ladder

Brute Force — try every value for the next slotO(N · 2^B)O(1)

For each position, try candidate values until arr[i] ^ candidate equals encoded[i]

Optimal — XOR undoes itselfO(N)O(1)

arr[i + 1] = arr[i] ^ encoded[i], one step per position

Brute Force Intuition

We do not know arr[i + 1], but we know its range. Every value in arr is below 2^B, where 2^B is larger than every input number. For each position, try the candidates v = 0, 1, 2, … until arr[i] ^ v equals encoded[i], then keep v as arr[i + 1].

Recognition rule for this sub-pattern:

x ^ x = 0 and x ^ 0 = x, so XOR-ing everything cancels the pairs.

Remember this · Bit Manipulation

Trigger

"Every element appears twice except…", power of two, counting set bits, subsets as bitmasks, O(1) space tricks.

Think

What happens to this problem if I look at each bit separately?

Key question

Which bit operation (XOR, AND, OR, shift) cancels or isolates what I need?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Bit Manipulation translate into production architectures and low-level memory mechanics.

LLD Architecture