Skip to main content

82. Find the Duplicate Number

mediumAsked at Workday

Find the duplicate number in an array of n+1 integers where each is in [1, n]. Workday uses this for Floyd's cycle detection in non-linked-list contexts — same shape as finding the duplicate employee record in a permission graph.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 onsite.

Problem

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space.

Constraints

  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

Examples

Example 1

Input
nums = [1,3,4,2,2]
Output
2

Example 2

Input
nums = [3,1,3,4,2]
Output
3

Approaches

1. Sort or hash set

Sort and find adjacent duplicates, or hash and check.

Time
O(n log n) or O(n)
Space
O(1) sort or O(n) set)
// sort mutates; set uses O(n) — both violate constraints

Tradeoff: Violates 'no modification' or 'constant space'.

2. Floyd's cycle detection

Treat array as a function from index to value. Use slow/fast pointers; cycle entry is the duplicate.

Time
O(n)
Space
O(1)
function findDuplicate(nums) {
  let slow = nums[0], fast = nums[0];
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);
  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

Tradeoff: O(1) space, no modification. The trick: treat index as node, value as 'next'. Duplicate creates a cycle.

Workday-specific tips

Workday wants Floyd's. The connection to Linked List Cycle (LC 142) is the framing they want — articulate it. The reset-and-walk phase finds the cycle entry, which is the duplicate.

Common mistakes

  • Using a hash set — O(n) space, violates the prompt.
  • Mutating the array — violates the prompt.
  • Doing only the first phase — finds where slow and fast meet, NOT the cycle entry.

Follow-up questions

An interviewer at Workday may pivot to one of these next:

  • Find Duplicate with multiple duplicates.
  • Find All Duplicates in an Array (LC 442) — mutates allowed.
  • Linked List Cycle II (LC 142) — same Floyd's pattern.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does array form a cycle?

Values in [1, n] are valid indices in nums (length n+1). The function f(i) = nums[i] maps {0..n} to {1..n}. With a duplicate, two indices map to the same next index — forming a cycle.

Why two phases?

Phase 1 finds A meeting point INSIDE the cycle. Phase 2 (slow restarted) walks at the same speed; they meet at the cycle ENTRY, which is the duplicate.

Practice these live with InterviewChamp.AI

Drill Find the Duplicate Number and other Workday interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →