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 <= 105nums.length == n + 11 <= 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.