C Program
#include <stdio.h>
int findDuplicate(int arr[], int n) {
int slow = arr[0], fast = arr[0];
do {
slow = arr[slow];
fast = arr[arr[fast]];
} while (slow != fast);
slow = arr[0];
while (slow != fast) {
slow = arr[slow];
fast = arr[fast];
}
return slow;
}
int main() {
int arr[] = {1, 3, 4, 2, 2};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Duplicate number is: %d\n", findDuplicate(arr, n));
return 0;
}C Output
Duplicate number is: 2
C++ Program
#include <iostream>
using namespace std;
int findDuplicate(int arr[], int n) {
int slow = arr[0], fast = arr[0];
do {
slow = arr[slow];
fast = arr[arr[fast]];
} while (slow != fast);
slow = arr[0];
while (slow != fast) {
slow = arr[slow];
fast = arr[fast];
}
return slow;
}
int main() {
int arr[] = {3, 1, 3, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Duplicate number is: " << findDuplicate(arr, n) << endl;
}C++ Output
Duplicate number is: 3
JAVA Program
public class Main {
static int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
public static void main(String[] args) {
int[] arr = {1, 4, 6, 3, 2, 6, 5};
System.out.println("Duplicate number is: " + findDuplicate(arr));
}
}JAVA Output
Duplicate number is: 6
Python Program
def find_duplicate(nums):
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
arr = [2, 5, 9, 6, 9, 3, 8, 9, 7, 1]
print(f"Duplicate number is: {find_duplicate(arr)}")Python Output
Duplicate number is: 9
Explanation
Example
Consider that you have an array of integers between 1 and n such that one of the numbers is repeated twice, but you cannot alter the array and should utilize constant extra space. For instance:
[1, 3, 4, 2, 2]
If you examine closely, every index of the array points to the subsequent number (similar to linked list where arr[i] is the "next pointer"). The fact that there's a duplicate implies there's a cycle in this "linked list" of numbers. The problem is then reduced to locating the entry point of such a cycle.
Real-Life Analogy
Think of a race track with multiple checkpoints numbered in sequence. A runner follows a path where each checkpoint tells them where to go next. If a checkpoint number is repeated, it means two different paths lead to the same checkpoint, forming a loop. Once you’re in that loop, you’ll keep running in circles. Finding the duplicate is like figuring out the first checkpoint where the loop starts.
Why It Matters
This is a valuable problem since it combines mathematics, graph theory, and algorithmic thinking. It is a hidden use of Floyd's Cycle Detection Algorithm, which has numerous applications in finding cycles in linked lists, graphs, and even in cryptographic sequence generation. In interviews, it checks whether you are able to identify a disguised linked-list structure within an array problem and solve it without changing data or taking additional space.
Step-by-Step Logic
We have two pointers:
Slow pointer advances one step at a time.
Fast pointer advances two steps at a time.
If there's a loop (which there is, due to the duplicate), these two pointers will catch up within the loop. When they catch up, re-setting one pointer to the beginning and moving them both one position at a time will get them to catch up at exactly the same position where the cycle starts — which is the duplicate number.
This is because the distance from the beginning to the cycle begin is the same as the distance from the meeting point to the cycle begin when both the pointers travel equally fast following the meeting.
Common Beginner Mistakes
Newbies attempt to do this by sorting the array or having a hash set of visited numbers. Although these can be done, they either change the array or need O(n) additional space, violating the problem stipulations. Another error is confusion that the array values are not sorted and cannot be used for a direct binary search without alteration.
Complexity and Optimization
The algorithm takes O(n) time because each of the pointers moves at most n steps. The space complexity is O(1) as we are using only two variables to keep track of movement. This is optimal — there's no better way to do this without violating the constraints.
Real-World Applications
Cycle detection is not merely theoretical. It's applied in:
Networking: Identifying routing loops where data packets become stuck in a cycle.
Data structures: Avoiding infinite loops in linked list traversal.
Security: Finding looping states in cryptographic pseudorandom number generators.
Distributed systems: Finding deadlocks with processes waiting on one another in a loop.
Interview Insights
When being asked this in an interview, the most important thing is to realize immediately that the values of the array are pointers to indices, creating a working graph with precisely one loop. To call Floyd's algorithm by name indicates familiarity, but to describe the rationale for how it works indicates expertise. Interviewers also appreciate asking follow-ups like "What if the numbers were not in range 1.n?
" or "What if the duplicate happened more than twice?
" These are variations that demand different approaches such as frequency counting or bit manipulation.
Learning Insights
This problem shows you that occasionally the best thing to do is rephrase the problem in another context. What appears to be a number array problem turns out to be a graph cycle problem in disguise. It's also a good reminder that constraints such as "O(1) space" are cues from the interviewer indicating specialized algorithms such as this one.
SEO-Friendly Closing Finding a duplicate number in an array without using O(1) space and without altering the array is a prime example of using Floyd's Cycle Detection Algorithm in a problem that at first glance has no connection to it.
Using this method is crucial for learning space-efficient algorithms in data structures and algorithms, competitive programming, and coding interviews. Appreciating this method not only enables you to answer duplicate number issues, but it also prepares you to address linked list cycle detection, network loop discovery, and optimization problems in high-speed systems where memory consumption has to be kept constant.
Social Plugin