FastPrepFind the Duplicate Number Without Modifying the Array

Find the Duplicate Number Without Modifying the Array

Google logoGoogle● MediumINTERNONSITE INTERVIEW
Learn

Problem statement

You are given an integer array nums of length n + 1. Every value is between 1 and n, inclusive, and exactly one distinct value appears more than once.

Return the duplicated value. The duplicated value may occur more than twice.

Do not modify nums. Use O(1) auxiliary space and strictly better than O(n^2) time.

Interview follow-up

Be prepared to explain which guarantees the constant-space algorithm relies on and how the available approaches change if several distinct values may repeat or if values are not restricted to 1 through n. These generalized variants are discussion-only; the judged function uses the primary contract above.

Function

findDuplicate(nums: int[]) → int

Examples

Example 1

nums = [1,3,4,2,2]return = 2

The value 2 appears twice, while every other value appears once.

Example 2

nums = [3,1,3,4,2]return = 3

The duplicated value is 3.

Example 3

nums = [1,1]return = 1

This is the smallest valid array, and 1 is duplicated.

Constraints

  • 1 <= n <= 100000.
  • nums.length == n + 1.
  • 1 <= nums[i] <= n.
  • Exactly one distinct value is duplicated, possibly more than twice.
  • The input array must not be modified.

More Google problems

See Google hiring insights
public int findDuplicate(int[] nums) {
  // Write your code here.
}
nums[1,3,4,2,2]
expected2
Checking account…