DSA-147 · Fixed-width XOR cancellation under an exact multiplicity promise
Single Number
Starter · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 14580 deterministic checks. Learner drafts are not executed.
Understand the problem
A nonempty array has exactly one value occurring once and every other distinct value occurring exactly twice. Return the single value without modifying the array.
- nums is a non-null int[] of odd length 1..100001. Null throws NullPointerException; empty, even-length, or oversized input throws IllegalArgumentException. Every signed int value, including MIN_VALUE, MAX_VALUE, negative values, and zero, is supported.
- The exact multiplicity condition is a caller precondition: one value occurs once and all others occur twice. The constant-space XOR reference checks shape but does not certify frequencies. On an odd-length array violating that promise, its returned XOR has no singleton guarantee and need not occur in the input.
- Return the singleton value and preserve every occurrence and its order. Do not sort caller input. The frequency-map baseline has the same promised-input scope; outside the promise it may return a frequency-one value or throw, rather than serving as a complete validator.
Examples
Input:
nums=[2,2,1]
Output:1The equal pair cancels, leaving the singleton.
Input:
nums=[4,1,2,1,2]
Output:4Pairs need not be adjacent or sorted.
Input:
nums=[-2147483648,7,7]
Output:-2147483648The sign bit participates in XOR just like every other bit.
Before you start
- Java int as a signed 32-bit two’s-complement bit pattern
- Frequency promises versus input validation
Recognize the structure
The frequency promise is unusually strong: every nuisance value contributes exactly two identical bit patterns. XOR is associative and commutative, has zero as its identity, and makes a value cancel itself. This permits a fixed-size parity summary of the entire multiset. It is a cancellation algorithm whose correctness depends on the promise, not a general-purpose way to find a rare value or validate frequency constraints.
Try before revealing
Hint 1
What binary operation makes a value cancel itself?
Hint 2
Can associativity and commutativity group nonadjacent equal occurrences conceptually?
Hint 3
Fold from zero with XOR, and explain why only the complete promised multiset has a singleton interpretation.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Count occurrences in a private frequency map
Insert every value into a HashMap<Integer,Integer>, then locate an entry with frequency one. Under the promise it is unique. This is expected O(n) time with O(d) entries for d distinct values; a strict malformed-frequency validator could also inspect every count and number of singleton entries. The shipped baseline intentionally shares the promised-input scope. Tests construct or filter valid multisets and use frequency counts plus independent per-bit parity checks as oracles.
Improve the baseline
Read XOR as independent bit parity
For each of the 32 positions, XOR outputs one exactly when an odd number of inputs have that bit set. Java’s ^ acts on int bit patterns; it is not exponentiation and does not perform arithmetic addition. Signed interpretation happens only when reading the resulting 32-bit value.
Cancel every promised pair
For any value a, a^a=0. Reordering the conceptual expression can group all equal pairs even though the implementation reads original order. Every pair disappears and the unique unpaired pattern remains unchanged because 0^s=s.
Keep a prefix aggregate
Initialize answer=0. After each occurrence, answer is the XOR of the processed prefix. A prefix need not have a meaningful singleton; its bits may combine several unmatched values. Only the complete promised multiset guarantees that the final aggregate is the desired existing value.
Avoid numeric overflow assumptions
No sums or magnitudes are computed. MIN_VALUE has one high bit, and negative values have valid two’s-complement patterns. The operation stays in 32 bits without an arithmetic-overflow hazard; widening or taking absolute values is unnecessary and can confuse the proof.
Separate a promise from an expensive validation
Odd length is necessary but not sufficient. [1,2,3] has odd length and XOR zero, yet no singleton satisfying the stated promise. Checking all frequencies requires another representation or extra work; silently claiming that XOR proves the input valid would be incorrect.
Why it is correct
Prefix invariant
Before processing any value, zero is the XOR of the empty prefix. If answer is the XOR of the processed occurrences, applying answer^=value extends exactly that prefix by one occurrence. Induction proves the invariant after every iteration.
Full-input cancellation
By associativity and commutativity, group the final expression into one singleton and equal pairs. Each pair has zero XOR, and zero is an identity, so the final answer equals the singleton bit pattern. The proof includes its sign bit and is independent of occurrence order.
Termination and limits
The loop consumes each occurrence once and preserves input. The fixed-width accumulator is enough under the exact promise. Without the promise, prefix aggregation still works but the cancellation conclusion does not; the API deliberately makes no frequency-validity claim.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public final class Solution {
private Solution() {}
private static void validate(int[] nums) {
Objects.requireNonNull(nums, "nums");
if (nums.length == 0 || nums.length > 100_001 || (nums.length & 1) == 0) {
throw new IllegalArgumentException("odd length in 1..100001 required");
}
}
// Caller promise: exactly one value occurs once; every other value occurs twice.
public static int singleNumber(int[] nums) {
validate(nums);
int answer = 0;
for (int value : nums) answer ^= value;
return answer;
}
// Frequency baseline under the same caller promise.
public static int baseline(int[] nums) {
validate(nums);
Map<Integer, Integer> counts = new HashMap<>();
for (int value : nums) counts.merge(value, 1, Integer::sum);
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (entry.getValue() == 1) return entry.getKey();
}
throw new IllegalArgumentException("singleton promise violated");
}
}
Read the meaningful blocks
Check shape, not hidden frequencies
Reject null, empty/even length, and sizes beyond the explicit cap. Do not suggest these checks establish the full promise. Valid singleton arrays return their only value, including zero or MIN_VALUE.
Fold all occurrences with XOR
The enhanced for loop reads every physical occurrence and overwrites only the accumulator. Do not deduplicate first: the second copy is exactly what cancels the first.
Return a signed int pattern
No conversion or unsigned formatting is required for the result. Teaching bit cards may use an unsigned 32-character representation while the numeric answer remains a Java int.
Complexity
The reference takes O(n) time and O(1) auxiliary space for fixed-width Java ints. It performs one 32-bit XOR per occurrence and returns one int. The bit width is fixed at 32; for arbitrary-width bit strings, their width would also enter the cost.
The frequency baseline uses expected O(n) time and O(d) auxiliary entries. Hashing is a baseline comparison, not needed by the optimized method. Teaching prefix histories and 32-bit strings are visualization allocations excluded from reference space.
Exact-state walkthroughs
Reveal normal and boundary traces
Nonadjacent pairs disappear only after all occurrences
Input: [4,1,2,1,2] · Singleton under the pair promise: 4
Step 1 of 8: Seed the empty-prefix XOR with zero.
Each of 32 bits tracks occurrence parity. Only the complete promised input has a singleton interpretation.
Phase: initial.
Read-only original occurrences:
- 0: 4unprocessed occurrence
- 1: 1unprocessed occurrence
- 2: 2unprocessed occurrence
- 3: 1unprocessed occurrence
- 4: 2unprocessed occurrence
Live prefix XOR: 0 — grouped unsigned display of a signed int
00000000bits 31..2400000000bits 23..1600000000bits 15..800000000bits 7..0
Prefix XOR history — teaching data
- 0 occurrences: 0
At each position, equal bits cancel in pairs. Negative values use all 32 two’s-complement bits; the leftmost displayed bit is the sign bit. Prefix aggregates may combine several unmatched values.
The final singleton conclusion requires exactly one value once and every other value twice. XOR does not validate that promise.
| Variable | Value |
|---|---|
| input | [4,1,2,1,2] |
| phase | "initial" |
| answer | 0 |
| answerBits | "00000000000000000000000000000000" |
| history | [0] |
| processed | 0 |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Objects; 4 5 public final class Solution { 6 private Solution() {} 7 private static void validate(int[] nums) { 8 Objects.requireNonNull(nums, "nums"); 9 if (nums.length == 0 || nums.length > 100_001 || (nums.length & 1) == 0) { 10 throw new IllegalArgumentException("odd length in 1..100001 required"); 11 } 12 } 13 // Caller promise: exactly one value occurs once; every other value occurs twice. 14 public static int singleNumber(int[] nums) { 15 validate(nums); 16 int answer = 0; 17 for (int value : nums) answer ^= value; 18 return answer; 19 } 20 // Frequency baseline under the same caller promise. 21 public static int baseline(int[] nums) { 22 validate(nums); 23 Map<Integer, Integer> counts = new HashMap<>(); 24 for (int value : nums) counts.merge(value, 1, Integer::sum); 25 for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { 26 if (entry.getValue() == 1) return entry.getKey(); 27 } 28 throw new IllegalArgumentException("singleton promise violated"); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the empty-prefix XOR with zero.
Each of 32 bits tracks occurrence parity. Only the complete promised input has a singleton interpretation.
- input
[4,1,2,1,2]- phase
"initial"- answer
0- answerBits
"00000000000000000000000000000000"- history
[0]- processed
0
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[4,1,2,1,2]- phase
"fold"- answer
4- answerBits
"00000000000000000000000000000100"- history
[0,4]- index
0- processed
1- before
0- beforeBits
"00000000000000000000000000000000"- value
4- valueBits
"00000000000000000000000000000100"
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[4,1,2,1,2]- phase
"fold"- answer
5- answerBits
"00000000000000000000000000000101"- history
[0,4,5]- index
1- processed
2- before
4- beforeBits
"00000000000000000000000000000100"- value
1- valueBits
"00000000000000000000000000000001"
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[4,1,2,1,2]- phase
"fold"- answer
7- answerBits
"00000000000000000000000000000111"- history
[0,4,5,7]- index
2- processed
3- before
5- beforeBits
"00000000000000000000000000000101"- value
2- valueBits
"00000000000000000000000000000010"
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[4,1,2,1,2]- phase
"fold"- answer
6- answerBits
"00000000000000000000000000000110"- history
[0,4,5,7,6]- index
3- processed
4- before
7- beforeBits
"00000000000000000000000000000111"- value
1- valueBits
"00000000000000000000000000000001"
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[4,1,2,1,2]- phase
"fold"- answer
4- answerBits
"00000000000000000000000000000100"- history
[0,4,5,7,6,4]- index
4- processed
5- before
6- beforeBits
"00000000000000000000000000000110"- value
2- valueBits
"00000000000000000000000000000010"
- Read the surviving singleton under the caller promise.
Associativity and commutativity group every promised pair to zero. Caller values and order remain unchanged.
- input
[4,1,2,1,2]- phase
"complete"- answer
4- answerBits
"00000000000000000000000000000100"- history
[0,4,5,7,6,4]- processed
5
- Return the documented outcome.
Input promises, output ownership, numeric domain, and rounding policy remain separate. Visualization histories and bit strings are excluded from reference workspace.
- result
4
Negative bit patterns and a zero singleton
Input: [-1,0,-1] · Singleton under the pair promise: 0
Step 1 of 6: Seed the empty-prefix XOR with zero.
Each of 32 bits tracks occurrence parity. Only the complete promised input has a singleton interpretation.
Phase: initial.
Read-only original occurrences:
- 0: -1unprocessed occurrence
- 1: 0unprocessed occurrence
- 2: -1unprocessed occurrence
Live prefix XOR: 0 — grouped unsigned display of a signed int
00000000bits 31..2400000000bits 23..1600000000bits 15..800000000bits 7..0
Prefix XOR history — teaching data
- 0 occurrences: 0
At each position, equal bits cancel in pairs. Negative values use all 32 two’s-complement bits; the leftmost displayed bit is the sign bit. Prefix aggregates may combine several unmatched values.
The final singleton conclusion requires exactly one value once and every other value twice. XOR does not validate that promise.
| Variable | Value |
|---|---|
| input | [-1,0,-1] |
| phase | "initial" |
| answer | 0 |
| answerBits | "00000000000000000000000000000000" |
| history | [0] |
| processed | 0 |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Objects; 4 5 public final class Solution { 6 private Solution() {} 7 private static void validate(int[] nums) { 8 Objects.requireNonNull(nums, "nums"); 9 if (nums.length == 0 || nums.length > 100_001 || (nums.length & 1) == 0) { 10 throw new IllegalArgumentException("odd length in 1..100001 required"); 11 } 12 } 13 // Caller promise: exactly one value occurs once; every other value occurs twice. 14 public static int singleNumber(int[] nums) { 15 validate(nums); 16 int answer = 0; 17 for (int value : nums) answer ^= value; 18 return answer; 19 } 20 // Frequency baseline under the same caller promise. 21 public static int baseline(int[] nums) { 22 validate(nums); 23 Map<Integer, Integer> counts = new HashMap<>(); 24 for (int value : nums) counts.merge(value, 1, Integer::sum); 25 for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { 26 if (entry.getValue() == 1) return entry.getKey(); 27 } 28 throw new IllegalArgumentException("singleton promise violated"); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the empty-prefix XOR with zero.
Each of 32 bits tracks occurrence parity. Only the complete promised input has a singleton interpretation.
- input
[-1,0,-1]- phase
"initial"- answer
0- answerBits
"00000000000000000000000000000000"- history
[0]- processed
0
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[-1,0,-1]- phase
"fold"- answer
-1- answerBits
"11111111111111111111111111111111"- history
[0,-1]- index
0- processed
1- before
0- beforeBits
"00000000000000000000000000000000"- value
-1- valueBits
"11111111111111111111111111111111"
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[-1,0,-1]- phase
"fold"- answer
-1- answerBits
"11111111111111111111111111111111"- history
[0,-1,-1]- index
1- processed
2- before
-1- beforeBits
"11111111111111111111111111111111"- value
0- valueBits
"00000000000000000000000000000000"
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[-1,0,-1]- phase
"fold"- answer
0- answerBits
"00000000000000000000000000000000"- history
[0,-1,-1,0]- index
2- processed
3- before
-1- beforeBits
"11111111111111111111111111111111"- value
-1- valueBits
"11111111111111111111111111111111"
- Read the surviving singleton under the caller promise.
Associativity and commutativity group every promised pair to zero. Caller values and order remain unchanged.
- input
[-1,0,-1]- phase
"complete"- answer
0- answerBits
"00000000000000000000000000000000"- history
[0,-1,-1,0]- processed
3
- Return the documented outcome.
Input promises, output ownership, numeric domain, and rounding policy remain separate. Visualization histories and bit strings are excluded from reference workspace.
- result
0
The sign-bit singleton survives
Input: [-2147483648,7,7] · Singleton under the pair promise: -2147483648
Step 1 of 6: Seed the empty-prefix XOR with zero.
Each of 32 bits tracks occurrence parity. Only the complete promised input has a singleton interpretation.
Phase: initial.
Read-only original occurrences:
- 0: -2147483648unprocessed occurrence
- 1: 7unprocessed occurrence
- 2: 7unprocessed occurrence
Live prefix XOR: 0 — grouped unsigned display of a signed int
00000000bits 31..2400000000bits 23..1600000000bits 15..800000000bits 7..0
Prefix XOR history — teaching data
- 0 occurrences: 0
At each position, equal bits cancel in pairs. Negative values use all 32 two’s-complement bits; the leftmost displayed bit is the sign bit. Prefix aggregates may combine several unmatched values.
The final singleton conclusion requires exactly one value once and every other value twice. XOR does not validate that promise.
| Variable | Value |
|---|---|
| input | [-2147483648,7,7] |
| phase | "initial" |
| answer | 0 |
| answerBits | "00000000000000000000000000000000" |
| history | [0] |
| processed | 0 |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Objects; 4 5 public final class Solution { 6 private Solution() {} 7 private static void validate(int[] nums) { 8 Objects.requireNonNull(nums, "nums"); 9 if (nums.length == 0 || nums.length > 100_001 || (nums.length & 1) == 0) { 10 throw new IllegalArgumentException("odd length in 1..100001 required"); 11 } 12 } 13 // Caller promise: exactly one value occurs once; every other value occurs twice. 14 public static int singleNumber(int[] nums) { 15 validate(nums); 16 int answer = 0; 17 for (int value : nums) answer ^= value; 18 return answer; 19 } 20 // Frequency baseline under the same caller promise. 21 public static int baseline(int[] nums) { 22 validate(nums); 23 Map<Integer, Integer> counts = new HashMap<>(); 24 for (int value : nums) counts.merge(value, 1, Integer::sum); 25 for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { 26 if (entry.getValue() == 1) return entry.getKey(); 27 } 28 throw new IllegalArgumentException("singleton promise violated"); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the empty-prefix XOR with zero.
Each of 32 bits tracks occurrence parity. Only the complete promised input has a singleton interpretation.
- input
[-2147483648,7,7]- phase
"initial"- answer
0- answerBits
"00000000000000000000000000000000"- history
[0]- processed
0
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[-2147483648,7,7]- phase
"fold"- answer
-2147483648- answerBits
"10000000000000000000000000000000"- history
[0,-2147483648]- index
0- processed
1- before
0- beforeBits
"00000000000000000000000000000000"- value
-2147483648- valueBits
"10000000000000000000000000000000"
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[-2147483648,7,7]- phase
"fold"- answer
-2147483641- answerBits
"10000000000000000000000000000111"- history
[0,-2147483648,-2147483641]- index
1- processed
2- before
-2147483648- beforeBits
"10000000000000000000000000000000"- value
7- valueBits
"00000000000000000000000000000111"
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[-2147483648,7,7]- phase
"fold"- answer
-2147483648- answerBits
"10000000000000000000000000000000"- history
[0,-2147483648,-2147483641,-2147483648]- index
2- processed
3- before
-2147483641- beforeBits
"10000000000000000000000000000111"- value
7- valueBits
"00000000000000000000000000000111"
- Read the surviving singleton under the caller promise.
Associativity and commutativity group every promised pair to zero. Caller values and order remain unchanged.
- input
[-2147483648,7,7]- phase
"complete"- answer
-2147483648- answerBits
"10000000000000000000000000000000"- history
[0,-2147483648,-2147483641,-2147483648]- processed
3
- Return the documented outcome.
Input promises, output ownership, numeric domain, and rounding policy remain separate. Visualization histories and bit strings are excluded from reference workspace.
- result
-2147483648
Already a singleton
Input: [0] · Singleton under the pair promise: 0
Step 1 of 4: Seed the empty-prefix XOR with zero.
Each of 32 bits tracks occurrence parity. Only the complete promised input has a singleton interpretation.
Phase: initial.
Read-only original occurrences:
- 0: 0unprocessed occurrence
Live prefix XOR: 0 — grouped unsigned display of a signed int
00000000bits 31..2400000000bits 23..1600000000bits 15..800000000bits 7..0
Prefix XOR history — teaching data
- 0 occurrences: 0
At each position, equal bits cancel in pairs. Negative values use all 32 two’s-complement bits; the leftmost displayed bit is the sign bit. Prefix aggregates may combine several unmatched values.
The final singleton conclusion requires exactly one value once and every other value twice. XOR does not validate that promise.
| Variable | Value |
|---|---|
| input | [0] |
| phase | "initial" |
| answer | 0 |
| answerBits | "00000000000000000000000000000000" |
| history | [0] |
| processed | 0 |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Objects; 4 5 public final class Solution { 6 private Solution() {} 7 private static void validate(int[] nums) { 8 Objects.requireNonNull(nums, "nums"); 9 if (nums.length == 0 || nums.length > 100_001 || (nums.length & 1) == 0) { 10 throw new IllegalArgumentException("odd length in 1..100001 required"); 11 } 12 } 13 // Caller promise: exactly one value occurs once; every other value occurs twice. 14 public static int singleNumber(int[] nums) { 15 validate(nums); 16 int answer = 0; 17 for (int value : nums) answer ^= value; 18 return answer; 19 } 20 // Frequency baseline under the same caller promise. 21 public static int baseline(int[] nums) { 22 validate(nums); 23 Map<Integer, Integer> counts = new HashMap<>(); 24 for (int value : nums) counts.merge(value, 1, Integer::sum); 25 for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { 26 if (entry.getValue() == 1) return entry.getKey(); 27 } 28 throw new IllegalArgumentException("singleton promise violated"); 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the empty-prefix XOR with zero.
Each of 32 bits tracks occurrence parity. Only the complete promised input has a singleton interpretation.
- input
[0]- phase
"initial"- answer
0- answerBits
"00000000000000000000000000000000"- history
[0]- processed
0
- XOR this physical occurrence into the prefix aggregate.
Equal patterns cancel even when separated. The signed decimal answer and its unsigned display bits encode the same Java int. The multiplicity promise is not being validated by this fold.
- input
[0]- phase
"fold"- answer
0- answerBits
"00000000000000000000000000000000"- history
[0,0]- index
0- processed
1- before
0- beforeBits
"00000000000000000000000000000000"- value
0- valueBits
"00000000000000000000000000000000"
- Read the surviving singleton under the caller promise.
Associativity and commutativity group every promised pair to zero. Caller values and order remain unchanged.
- input
[0]- phase
"complete"- answer
0- answerBits
"00000000000000000000000000000000"- history
[0,0]- processed
1
- Return the documented outcome.
Input promises, output ownership, numeric domain, and rounding policy remain separate. Visualization histories and bit strings are excluded from reference workspace.
- result
0
Test the contract
Input:
nums=[0]
Output:0A zero singleton is valid.
Input:
nums=[-1,0,-1]
Output:0Negative pairs cancel.
Input:
nums=[2147483647,-2147483648,-2147483648]
Output:2147483647Both integer extremes are supported.
Input:
nums=[]
Output:IllegalArgumentExceptionNo singleton can satisfy the promise.
Input:
nums=[1,1]
Output:IllegalArgumentExceptionEven length is rejected as a shape error.
Common mistakes and counterexamples
Use ^ as arithmetic exponentiation
Counterexample: In Java, 2^3 equals one, not eight.
Treat ^ as bitwise parity and use a separate exponentiation algorithm for powers.
Discard duplicate values before folding
Counterexample: [2,2,1] becomes [2,1], destroying pair cancellation.
Consume every occurrence exactly as provided.
Claim every odd-length input has a valid singleton
Counterexample: [1,2,3] folds to zero, which is absent.
State and preserve the exact caller multiplicity promise.
Use sum or absolute-value shortcuts on full ints
Counterexample: MIN_VALUE cannot be made positive in int; sums of valid pairs can overflow.
Use XOR on the original bit patterns.
Follow-ups
Validate arbitrary frequencies as well.
Count all values and require exactly one count of one and every other count equal to two. A map gives expected linear time and linear distinct-value storage. This is additional behavior beyond the constant-space promised-input reference.
Find two singletons among pairs.
Their XOR is a^b, which is nonzero. Pick a set bit to split occurrences into two groups, XOR each group, and prove the singletons separate while pairs remain together. Define the ordering of the two outputs.
Make every repeated value occur three times.
Pair cancellation no longer applies. Count each bit modulo three or derive finite-state bit counters. Handle the sign bit explicitly and prove the changed multiplicity model instead of reusing the XOR-pair proof.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 115/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.