FastPrepFind the Duplicate in a Read-Only Array
Problems/Find the Duplicate in a Read-Only Array

Find the Duplicate in a Read-Only Array

Nutanix logoNutanix● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was the coding question in the second of two back-to-back technical phone screens for a Nutanix software engineering intern role. You get n + 1 numbers that all lie between 1 and n, so one must repeat, and you find it. The candidate offered brute force, a hash set and sorting. Then the interviewer added three limits: no extra memory, the array cannot be changed, and faster than O(n^2). The hint was a binary search over the range of values.

The report does not say if the repeated number can show up more than twice, or how big n gets. Here exactly one number repeats, and it can show up any number of times. n is at most 3 * 10^4. You return that number. The tests only check the number you return, not the memory or no-change limits.

Our version is about 90% the same as the reported question.

You are given an integer array nums with n + 1 values. Every value is between 1 and n, inclusive. There are more values than possible numbers, so at least one number must repeat. In this problem exactly one number repeats, and it may appear two or more times. Every other number appears at most once.

Return the number that repeats.

Follow the interview's rules:

  • Treat nums as read-only. Do not change it, and do not sort it.
  • Use only O(1) extra space.
  • Run in less than O(n^2) time.

The judge checks only the returned number. It cannot check the space you use or whether you changed the array, so keeping those rules is up to you.

Function

findDuplicate(nums: int[]) → int

Examples

Example 1

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

The array has 6 values, so n = 5 and every value is between 1 and 5. The value 4 appears twice (at index 0 and index 4), and every other value appears once.

Example 2

nums = [2,6,2,1,2,5,2]return = 2

The array has 7 values, so n = 6. The value 2 appears four times, at indexes 0, 2, 4 and 6. Because one value takes four places, the values 3 and 4 do not appear at all. The answer is 2.

Example 3

nums = [1,1]return = 1

With 2 values, n = 1, so both values must be 1. The repeated value is 1.

Constraints

  • 1 <= n <= 3 * 10^4
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • Exactly one value appears more than once. It may appear two or more times.

More Nutanix Phone Screen questions

  • Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
  • Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
  • Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
  • Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
  • Kth Smallest Element in a BSTPHONE SCREEN · Seen Feb 2020
  • Outline of a Binary TreePHONE SCREEN · Seen Jan 2020
  • Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
  • Inorder Predecessor in a BSTPHONE SCREEN · Seen Jan 2019
  • K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019
  • Odd Numbers Up and BackPHONE SCREEN · Seen Jan 2019

Similar questions at other companies

  • Find K Closest Elements in a Sorted ArrayNavi · PHONE SCREEN
  • K Closest Elements in a Sorted ArrayAmazon · PHONE SCREEN
  • Count Winning Dice Face PairsGoogle · PHONE SCREEN
  • Count Centaur Friend RequestsMeta · PHONE SCREEN
  • Count Triples That Can Form a TriangleAdobe · PHONE SCREEN
  • Target Sum Across Two Sorted ArraysSquarepoint Capital · PHONE SCREEN
  • Target Sum Across Two Sorted ArraysBloomberg LP · PHONE SCREEN · ONSITE INTERVIEW
  • Search a Row- and Column-Sorted MatrixByteDance · ONSITE INTERVIEW
  • 3Sum SmallerSalesforce · ONSITE INTERVIEW
  • K Smallest Squares from a Sorted ArrayUber · ONSITE INTERVIEW
See Nutanix hiring insights
Saved
class Solution {
    public int findDuplicate(int[] nums) {
        // Write your code here.
    }
}
Checking account…