Find Duplicate Number Solution for Cognizant
Company: Cognizant · Difficulty: Easy · Topics: Array, Two Pointers, Binary Search
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.
Examples
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Approach
Use Floyd's Cycle Detection Algorithm (Tortoise and Hare) to find the duplicate in O(1) space.
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)