Single Number (Find the One Element That Appears Once)

Single Number is the foundational Bitwise XOR problem. Because XOR of a number with itself is zero and XOR with zero leaves the number unchanged, XOR-ing every element together cancels each pair and leaves only the unpaired number. This runs in O(n) time and O(1) space, beating a hash-set approach on memory.

What is the problem?

Single Number (Find the One Element That Appears Once). In an array where every number appears exactly twice except for one number that appears once, find that single number using constant extra space. Explain why XOR of all elements gives the answer.

How does the approach work?

XOR has three properties we rely on: a number XOR itself is zero, a number XOR zero is itself, and XOR is commutative and associative so order does not matter. We start a running result at zero and XOR every element into it: int result = 0; for (int n : nums) result ^= n;. Because each paired value appears an even number of times, those values XOR to zero, and only the odd-one-out remains in result.

This is strictly better than the obvious approaches. Sorting then scanning is O(n log n); a hash set counting occurrences is O(n) time but O(n) space. The XOR method is O(n) time and O(1) space, which is the senior-level answer the interviewer is looking for.

A senior nuance is that XOR works here precisely because every other element is perfectly paired; if elements could appear three times or some other odd count, this simple XOR would not isolate the single number and we would need bit-counting across positions instead. Complexity is O(n) time and O(1) space.

What is the banking use case?

The code defines a ReconService exposing findOrphan(codes) returning the unmatched code. A Demo runs it over a batch with one orphan and logs the orphan code.

How do you implement this in Java?

// ─── File: src/main/java/com/bank/recon/service/ReconService.java ───
package com.bank.recon.service;

import java.util.logging.Logger;

// Finds the single unmatched reconciliation code via XOR.
public class ReconService {
    private static final Logger log = Logger.getLogger(ReconService.class.getName());

    public int findOrphan(int[] codes) {
        int result = 0;
        for (int code : codes) result ^= code; // pairs cancel to zero
        final int orphan = result;
        log.info(() -> "Unmatched reconciliation code = " + orphan);
        return result;
    }
}

// ─── File: src/main/java/com/bank/recon/ReconOrphanApplication.java ───
package com.bank.recon;

import com.bank.recon.service.ReconService;
import java.util.logging.Logger;

public class ReconOrphanApplication {
    private static final Logger log = Logger.getLogger(ReconOrphanApplication.class.getName());

    public static void main(String[] args) {
        ReconService service = new ReconService();
        int[] codes = {7012, 7045, 7012, 7099, 7045}; // 7099 is the orphan
        log.info("Orphan code: " + service.findOrphan(codes));
    }
}

What is the project structure?

recon-orphan-service/
├── pom.xml
├── src/
│   ├── main/
│   │   ├── java/com/bank/recon/
│   │   │   ├── ReconOrphanApplication.java       (main class)
│   │   │   └── service/
│   │   │       └── ReconService.java
│   │   └── resources/
│   │       └── application.yml
│   └── test/
│       └── java/com/bank/recon/
│           └── ReconServiceTest.java

How do you build and run?

# Build
mvn clean package -DskipTests

# Run
java -jar target/recon-orphan-service-1.0.0.jar

# Verbose
java -Djava.util.logging.ConsoleHandler.level=FINE \
  -jar target/recon-orphan-service-1.0.0.jar

What is the step-by-step walkthrough?

Input: codes 7012, 7045, 7012, 7099, 7045.

Oct 27, 2026 10:52:41 PM com.bank.recon.service.ReconService findOrphan
INFO: Unmatched reconciliation code = 7099
INFO: Orphan code: 7099

What is the high-level design?

  ═══ HLD — Reconciliation Orphan Finder (Banking) ═══

  ┌────────────┐ HTTPS ┌──────────────┐ REST ┌─────────────────────┐
  │ Recon Batch│──────→│ API Gateway  │─────→│ Recon Svc ×2        │
  └────────────┘       │ (JWT, rate)  │      │ (Spring Boot)       │
                       └──────────────┘      └─────────┬───────────┘
                                                      │ stream codes
                                                      ▼
                                           ┌─────────────────────┐
                                           │ Ledger entries store │
                                           └─────────────────────┘

What is the low-level design?

  ═══ LLD — Single Number ═══

  ┌─ Design Patterns Used ──────────────────────────────────┐
  │  XOR fold (self-inverse cancels pairs)                   │
  │     WHY: O(1) space, no lookup structure                 │
  └──────────────────────────────────────────────────────────┘

  ┌─ SOLID Principles Applied ──────────────────────────────┐
  │  S: service only isolates the orphan                     │
  │  O: any paired-with-one-odd input works                  │
  │  D: depends only on primitive int array                  │
  └──────────────────────────────────────────────────────────┘

  ── Class Diagram ──────────────────────────────────────────
  ┌──────────────────────────────────────┐
  │ ReconService                          │
  │ ───────────────────────────────────── │
  │ + findOrphan(codes): int              │
  └──────────────────────────────────────┘

  ── State: single running XOR accumulator ─────────────────
  result ^= each code; pairs vanish

  Contract for findOrphan(codes):
    Pre:  every code paired except exactly one
    Post: the single unpaired code

What is the time and space complexity?

Analyze the solution based on the algorithm used. Consider both the time to process input and the space required for any data structures.

What are common mistakes?

Common mistakes include off-by-one errors, not handling edge cases like empty input, and not considering the constraints of the problem.

What are the edge cases?

Edge cases include empty input, single element input, all identical elements, and boundary values.

What should a senior engineer know?

A senior engineer should understand the time-space tradeoffs, be able to explain the algorithm clearly, and know when this technique applies versus alternatives.