Bit Manipulation — Find the Difference
↗ LeetCode: Find the Difference · Easy · pattern chapter →
Asked atGoogleAmazonMeta
t is s shuffled with one extra letter. Return that letter.
Example 1 — s="abcd", t="abcde" → 'e'Example 2 — s="", t="y" → 'y'
Constraints — 0 ≤ |s| ≤ 1000. Brute HashMap of counts is O(n) + O(n) space. XOR-fold s+t is O(n) time + O(1) space — ~10⁶ ops on 1000-char input, no allocations.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Sort both, walk
O(n log n). Baseline.
Approach 2 — Frequency map
O(n) time O(σ) space.
Approach 3 — XOR fold (canonical)
Insight. XOR all chars of s and t; duplicates cancel; only the added char survives.
java
char findTheDifference(String s, String t) {
int x = 0;
for (char c : s.toCharArray()) x ^= c;
for (char c : t.toCharArray()) x ^= c;
return (char) x;
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Sort | O(n log n) | O(n) | baseline |
| Frequency | O(n) | O(σ) | works |
| XOR fold | O(n) | O(1) | canonical |
When to use which
- Any "find the odd one out" → XOR fold.
- "Multiple extra chars" → count map.
- "Which position was added" → walk both with two pointers.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems