LeetCode 1720 | Decode XORed Array | Bit Manipulation & Array Reconstruction Explained | Pen & Paper

LeetCode 1720 | Decode XORed Array | Bit Manipulation & Array Reconstruction Explained | Pen & Paper

In this video we solve LeetCode 1720 — Decode XORed Array.
You are given an encoded integer array (of length n−1) and an integer first which is the first element of the hidden original array arr. The encoding rule is:

encoded[i] = arr[i] XOR arr[i + 1]


Your task: reconstruct the full original array arr of length n.

What you’ll learn in this video:
• The key XOR property: if a XOR b = c then a XOR c = b and b XOR c = a. This is what allows decoding.
AlgoMonster
+2
goodtecher.com
+2

• How to initialize: set arr[0] = first.
• For each i from 0 to encoded.length−1, compute

arr[i+1] = arr[i] XOR encoded[i]


This yields each next element in O(1) time.
WalkCCC

• Explanation with a worked example:

Example: encoded = [1,2,3], first = 1 → arr = [1, 0, 2, 1] because:
1 XOR 0 = 1; 0 XOR 2 = 2; 2 XOR 1 = 3.
• Time complexity: O(n) (single pass), space complexity: O(n) (output array).
Leetcode
+1

• Why this pattern is important for tech interviews: it demonstrates array manipulation and fundamental bit-wise reasoning.
• Bonus: How to explain this solution clearly during coding rounds (how you derive arr[i+1] = arr[i] XOR encoded[i], why XOR is its own inverse).

If you want to strengthen your bit-manipulation toolkit, this is a must-know pattern.
📘 Visit penpaperpreparation.com for full handwritten notes, downloadable examples, and problem sets.