Find the Duplicate in a Read-Only Array
Updated
Problem statement
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
numsas 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[]) → intExamples
Example 1
nums = [4,2,5,1,4,3]return = 4The 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 = 2The 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 = 1With 2 values, n = 1, so both values must be 1. The repeated value is 1.
Constraints
1 <= n <= 3 * 10^4nums.length == n + 11 <= 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