Home » leet code » Leet Code 287 Find the Duplicate Number (Medium)

# Leet Code 287 Find the Duplicate Number (Medium)

Find the Duplicate Number : Finding a sneaky duplicate number in an array can be a real brain-teaser, especially when you’re told not to mess with the array or use too much memory. But fear not! We’ve got a clever trick up our sleeves to crack this code conundrum.

`Understanding the Puzzle:Imagine this: You're handed an array of integers, and there's a twist. Only one number is repeated, and it's your mission to expose this copycat!`

## The Algorithm Unveiled:

Behold, the secret sauce lies in a legendary algorithm called “tortoise and hare.” 🐢🐇 Let’s break down this detective code:

Note : tortoise and hare Algorithm Also called Floyd’s Cycle Finding Algorithm

How to get 5✨ on Leet Code with my Own experience

### Step 1: The Setup

• Two counting pointers, “slow” and “fast,” start at the same spot – the first element of the array, `nums[0]`. 🎯

### Step 2: Phase 1 – Tracking the Meetup

• In this phase, “slow” moves forward one step, while “fast” moves two steps ahead.
• They keep going until they come to each other like a Hollywood showdown. 💥👊
• What’s the point? This is where the magic begins, and a cycle is born within the array.

Leet Code : Find the Duplicate Number / Element C++ ,Java , Python Solution:

### Step 3: Phase 2 – Hare Returns to the Scene

• After finding the epic meetup point, we rewind one of our heroes (either “slow” or “fast”) back to the array’s start, `nums[0]`.
• Now, both pointers move step by step, but guess what? They’ll meet again.
• When they meet together the second time, that’s our jackpot! 🎰 The value they meet at is the elusive duplicated number in the `nums` array.

### Step 4: The Big Reveal

• The secret is out! The number they uncover in Phase 2 is the duplicate you’ve been hunting.
• The best part? The original `nums` array remains unscathed, and we didn’t gobble up extra memory. 🧠💾

Also Read : Leetcode 135 Candy (Hard) Solution

here’s the code for finding the duplicate number in C++, Python, Java, and JavaScript.

## C++:

``````class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = nums[0];
int fast = nums[0];

// Phase 1: Find the meeting point
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) {
break;
}
}

// Phase 2: Find the start of the cycle
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

return slow;
}
};``````

Leet Code :Linked List Cycle II Java || Python || C++ solution

## Python:

``````def findDuplicate(nums):
slow = nums[0]
fast = nums[0]

# Phase 1: Find the meeting point
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break

# Phase 2: Find the start of the cycle
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]

return slow``````

Leet Code : Intersection of Two Linked ListsLeet Code – Java | Python | C++ | Dart | Easy Solution

## Java:

``````public class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[0];

// Phase 1: Find the meeting point
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) {
break;
}
}

// Phase 2: Find the start of the cycle
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

return slow;
}
}``````

## JavaScript:

``````function findDuplicate(nums) {
let slow = nums[0];
let fast = nums[0];

// Phase 1: Find the meeting point
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow === fast) {
break;
}
}

// Phase 2: Find the start of the cycle
slow = nums[0];
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}

return slow;
}``````

These code snippets in C++, Python, Java, and JavaScript all implement the same logic for finding the duplicate number using the “tortoise and hare” algorithm.

Leet Code : Three (3) Sum Java | CPP | Python Solution

## Conclusion:

By using the “tortoise and hare” trick, we’ve outsmarted the duplicate number puzzle without altering the array or going on a memory . This nifty algorithm showcases the brilliance of problem-solving through clever thinking.

So, next time you’re faced with a similar challenge, remember this elegant solution that keeps the array pristine and memory usage minimal. 🚀🧩

This article decodes the code and its intriguing logic for finding that tricky duplicate number. It showcases the elegance of the “tortoise and hare” algorithm for solving complex puzzles. 🔍🕵️‍♂️