Definition
- Cyclic Sort – a pattern where each value
vis placed at indexv, exploiting the range0..nover an array of lengthn. - Skip rule – values equal to
nare skipped during placement because there is no indexn. - Detection scan – after placement, the first index where
nums[i] != ireveals the missing number. - Fallback – if all positions 0 through n-1 are correct, the missing number is
n. - Complexity – O(n) time (each element swapped at most once) and O(1) space (in-place).
The National Bank of India issues cheque-book booklet slots numbered 0 to n, and one booklet never arrived. A clerk walks each booklet to its matching slot. At the end, the one slot holding the wrong booklet points to the booklet number that was never delivered.
Understanding the Concepts
What is the Cyclic Sort approach for finding a missing number?
Because the array of length n contains distinct values from 0 to n with exactly one missing, each value v should sit at index v. The Cyclic Sort pass swaps each value to its correct position, and a follow-up scan finds the index where the value does not match.
package com.bank.service;
public class MissingNumberCyclicSort {
public int findMissing(int[] nums) {
int n = nums.length;
// Placement pass
int i = 0;
while (i < n) {
if (nums[i] < n && nums[i] != nums[nums[i]]) {
int temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
} else {
i++;
}
}
// Detection scan
for (i = 0; i < n; i++) {
if (nums[i] != i) return i;
}
return n; // missing is n itself
}
}
Why skip values equal to n?
The array has length n, so valid indices are 0 through n-1. A value equal to n has no home index. During the placement pass, we simply skip it. After placement, if n is the missing number, every index 0 through n-1 will have its correct value, and the detection scan reaches the end without finding a mismatch.
package com.bank.service;
public class SkipNDemo {
public static void main(String[] args) {
int[] slots = {3, 0, 1}; // n=3, range 0..3, missing=2
// Value 3 == n, skip it during placement
// After sort: [0, 1, 3] -> index 2 holds 3 != 2 -> missing is 2
MissingNumberCyclicSort solver = new MissingNumberCyclicSort();
System.out.println("Missing: " + solver.findMissing(slots)); // 2
}
}
Missing: 2
How does the placement pass work step by step?
The placement pass uses a while loop. At each position, if the value is less than n and not already at its correct index, we swap it to its home. Otherwise, we move to the next position. Each element is swapped at most once, giving O(n) total swaps.
package com.bank.service;
public class PlacementTrace {
public static void main(String[] args) {
int[] nums = {4, 0, 3, 1}; // n=4, missing=2
int n = nums.length;
int i = 0;
int step = 0;
while (i < n) {
if (nums[i] < n && nums[i] != nums[nums[i]]) {
int target = nums[i];
int temp = nums[target];
nums[target] = nums[i];
nums[i] = temp;
step++;
System.out.println("Step " + step + ": swapped, array="
+ java.util.Arrays.toString(nums));
} else {
i++;
}
}
// Final: [0, 1, 3, 3] or similar
for (i = 0; i < n; i++) {
if (nums[i] != i) {
System.out.println("Missing: " + i);
return;
}
}
System.out.println("Missing: " + n);
}
}
How is this different from the sum and XOR methods?
All three methods solve the problem in O(n) time and O(1) space, but Cyclic Sort has the advantage of generalizing to harder variants like finding all missing numbers or detecting duplicates.
| Aspect | Cyclic Sort | Sum Formula | XOR |
|---|---|---|---|
| Overflow risk | None | Yes (use long) | None |
| Generalization | All missing, duplicates | Two missing (with sum-of-squares) | Limited |
| Modifies input | Yes | No | No |
| Readability | Moderate | Very simple | Requires XOR knowledge |
// Sum: simple but risks overflow
long expected = (long) n * (n + 1) / 2;
// XOR: no overflow but limited generalization
int xor = 0;
for (int j = 0; j <= n; j++) xor ^= j;
for (int val : nums) xor ^= val;
// Cyclic Sort: generalizes to find-all-missing and find-duplicates
while (i < n) { /* swap to home index */ }
What are the edge cases?
Edge cases include a single-element array where the missing number is 0 or 1, and the case where n itself is the missing number.
package com.bank.service;
public class CyclicSortEdgeCases {
public static void main(String[] args) {
MissingNumberCyclicSort solver = new MissingNumberCyclicSort();
// Missing is 0
System.out.println(solver.findMissing(new int[]{1})); // 0
// Missing is n
System.out.println(solver.findMissing(new int[]{0})); // 1
// Larger array, missing in middle
System.out.println(solver.findMissing(new int[]{0,1,3})); // 2
// Missing is n (all 0..n-1 present)
System.out.println(solver.findMissing(new int[]{0,1,2})); // 3
}
}
0
1
2
3
What are common mistakes?
The most common mistake is not handling the value-equals-n case, causing an ArrayIndexOutOfBoundsException. Another mistake is using nums[i] != i as the swap guard instead of nums[i] != nums[nums[i]], which fails to detect when the destination already holds the correct value.
// WRONG: no bounds check for value == n
while (i < n) {
if (nums[i] != i) { // tries to access nums[n] -> AIOOBE!
swap(nums, i, nums[i]);
} else { i++; }
}
// CORRECT: check nums[i] < n before accessing
while (i < n) {
if (nums[i] < n && nums[i] != nums[nums[i]]) {
swap(nums, i, nums[i]);
} else { i++; }
}
How would you apply this in a banking system?
At the National Bank of India, returned cheque booklets carry leaf numbers in a known range. One leaf is missing from a booklet. The audit clerk places each leaf at its own slot number and reports the mismatched slot, finding the missing leaf in linear time with no extra memory.
package com.bank.service;
public class BookletAuditService {
public int findMissingLeaf(int[] returnedLeaves) {
int n = returnedLeaves.length;
int i = 0;
while (i < n) {
if (returnedLeaves[i] < n
&& returnedLeaves[i] != returnedLeaves[returnedLeaves[i]]) {
int target = returnedLeaves[i];
int temp = returnedLeaves[target];
returnedLeaves[target] = returnedLeaves[i];
returnedLeaves[i] = temp;
} else {
i++;
}
}
for (i = 0; i < n; i++) {
if (returnedLeaves[i] != i) return i;
}
return n;
}
}
What should a senior engineer know?
A senior engineer should recognise that Cyclic Sort is a family of patterns, not just one trick. The same placement loop solves find-one-missing, find-all-missing, find-one-duplicate, and find-all-duplicates. Learning the pattern once covers the whole family. They should also know that the in-place swap modifies the input, which may not be acceptable in all contexts.
// Pattern family:
// 1. Find one missing: place v at index v, scan for mismatch
// 2. Find all missing: same placement, collect all mismatches
// 3. Find one duplicate: placement stops when home already occupied
// 4. Find all duplicates: same placement, collect all occupied-home cases
Visual Overview
Input: [4, 0, 3, 1] n=4, range 0..4, missing=2
Placement Pass:
i=0: nums[0]=4, 4 >= n=4 → skip, i=1
i=1: nums[1]=0, swap nums[1] and nums[0] → [0, 4, 3, 1]
nums[1]=4, 4 >= n=4 → skip, i=2
i=2: nums[2]=3, swap nums[2] and nums[3] → [0, 4, 1, 3]
nums[2]=1, swap nums[2] and nums[1] → [0, 1, 4, 3]
nums[2]=4, 4 >= n=4 → skip, i=3
i=3: nums[3]=3 == i=3 → skip, i=4 → done
After placement: [0, 1, 4, 3]
Detection Scan:
Index 0: nums[0]=0 ✓
Index 1: nums[1]=1 ✓
Index 2: nums[2]=4 ≠ 2 → Missing = 2
┌─────┬─────┬─────┬─────┐
│ 0 │ 1 │ 4 │ 3 │ ← values after placement
├─────┼─────┼─────┼─────┤
│ 0 │ 1 │ 2 │ 3 │ ← expected (indices)
└─────┴─────┴─────┴─────┘
▲
mismatch → missing = 2
Key Takeaway
Finding the one missing number from the range 0 to n is a clean application of the Cyclic Sort pattern. Because the values are distinct and span 0 to n over an array of length n, each value belongs at the index equal to itself. I run one placement pass that swaps every value to its home index, skipping any value equal to n since there is no index n, and then I scan once for the first position where the index and stored value disagree.
I prefer Cyclic Sort over the sum-formula trick because the sum approach can overflow on very large inputs, and I prefer it over XOR because XOR does not extend to the harder variants. The same placement loop generalizes directly to finding all missing numbers and to detecting duplicates, so learning the pattern once covers a whole family of problems.
Edge cases include the missing number being 0 (the first position is mismatched), the missing number being n (all positions 0 through n-1 are correct), and single-element arrays. The key implementation detail is the swap guard: check nums[i] < n before accessing nums[nums[i]] to avoid an out-of-bounds error.
At the National Bank of India, I used this to audit returned cheque booklets. Each booklet leaf carries a number in a known range, one leaf is missing, and the audit needed to name the missing leaf without sorting or allocating a second array.
Remember one sentence: place each value at its own index, and the first mismatch reveals the missing number.
---