Find the duplicate number-coding question asked by Meta, JPMC

Problem statement:

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.

Input Format:

Array nums

Output Format:

Repeated number in the array

Sample Input 1:

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

Sample Output 1:

2

Sample Input 2:

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

Sample Output 2:

3

Constraint:

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n

Approach:

We need to insert elements into a data structure and look them up in constant time, so as to improve the complexity of sorting approach. A set can be used to satisfy these conditions. So, we iterate over the array and insert each element into a set. Before inserting we check whether the element is already present in the set or not. If it is found, we get the repeated element and hence return it.

Time complexity: O(n)

Space complexity: O(n)

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.