. Day 7 - Challenge 3 - Finding Duplicate Numbers in Array Skip to main content

Day 7 - Challenge 3 - Finding Duplicate Numbers in Array

Solving the Duplicate Number Dilemma: Unearthing Hidden Duplicates in JavaScript

Introduction: 

Have you ever been faced with a perplexing puzzle involving an array of numbers, where one number seems to have duplicated itself? Fear not, for today we embark on a journey to decipher this mystery using the power of JavaScript! In this blog post, we'll unravel the enigma of finding a duplicate number in an array, utilizing a simple yet effective approach that leverages the characteristics of the given integers.

The Problem: 

Imagine you're presented with an array of n+1 integers, where each integer falls between the range of 1 and n. Hidden within this array is a single duplicate number, and your task is to unveil its identity.

The Solution: 

Fear not, for the solution is closer than you think. We'll use a technique known as the "tortoise and hare" algorithm, which is based on Floyd's cycle-finding algorithm. This approach is highly efficient with a time complexity of O(n) and a space complexity of O(1), making it a powerful tool in our arsenal.

function findDuplicate(nums) {
    let tortoise = nums[0];
    let hare = nums[0];
    
    // Phase 1: Detect the point of intersection within the cycle
    do {
        tortoise = nums[tortoise];
        hare = nums[nums[hare]];
    } while (tortoise !== hare);
    
    // Phase 2: Find the entrance to the cycle (duplicate number)
    tortoise = nums[0];
    while (tortoise !== hare) {
        tortoise = nums[tortoise];
        hare = nums[hare];
    }
    return hare;
}

// Example usage
const nums = [1, 3, 4, 2, 2];
const duplicate = findDuplicate(nums);
console.log(`The duplicate number is: ${duplicate}`);

Explanation:

  1. Phase 1: In this phase, we move the tortoise one step at a time and the hare two steps at a time. This way, they will eventually meet inside the cycle formed by the duplicate number and the indices it points to.

  2. Phase 2: After identifying the point of intersection in the cycle, we reset the tortoise to the beginning while keeping the hare at the intersection point. Moving both the tortoise and hare one step at a time will inevitably lead them to the entrance of the cycle, which is the duplicate number.

Demo:

Duplicate Number Finder

Enter an array of numbers separated by commas:

Conclusion: 

The journey to uncovering the duplicate number concealed within an array has come to an end. With the power of the "tortoise and hare" algorithm, we've navigated through the intricacies of cycle detection and emerged victorious in our quest. Armed with JavaScript, we've turned a complex problem into an elegant solution with an optimal runtime complexity.

Remember, the next time you encounter an array of numbers shrouded in mystery, you can confidently apply this algorithm to unearth the hidden duplicate and conquer the challenge! Happy coding!

Now write the same program in your favorite language in comment section. 

Other Challenges:

  1. Day 5 Challenges
  2. Day 6 Challenges 
  3. Day 7 Challenges

 

Labels:

Comments

Post a Comment

Popular posts from this blog

Day 9 - Challenge 1 - Product of Array Except Self

Solving the "Product of Array Except Self" Problem in JavaScript Are you ready to dive into a common coding challenge that not only tests your programming skills but also sharpens your problem-solving mindset? If you're up for the challenge, let's tackle the "Product of Array Except Self" problem together using JavaScript. This problem requires us to return an array where each element at index i is the product of all the elements in the original array except the one at index i . Understanding the Problem:   Imagine you're given an array of integers, let's call it nums . Your task is to create a new array where the value at index i in this new array is the product of all the elements in nums , except the one at index i . In other words, you're calculating the product of all the elements to the left of nums[i] and the product of all the elements to the right of nums[i] , and then multiplying these two products to get the final value at index i ...
Post a Comment
Read more

Day 9 - Challenge 2 - Reverse Linked List

Reversing a Singly Linked List in JavaScript: An In-Place Approach Introduction:   Singly linked lists are fundamental data structures in computer science that consist of a sequence of nodes, each containing data and a reference to the next node in the list. Reversing a singly linked list is a classic problem that challenges programmers to manipulate pointers effectively to achieve the desired outcome. In this blog post, we'll explore the problem of reversing a singly linked list using an in-place approach and provide a step-by-step solution in JavaScript. Problem Statement:   Given the head of a singly linked list, our task is to reverse the list in-place and return its new head. In other words, we need to modify the pointers of the nodes in such a way that the direction of the linked list is reversed. Solution Approach:   To solve this problem, we will iterate through the linked list while maintaining three pointers: previous , current , and next . The previous pointer...
Post a Comment
Read more

Day 8 - Challenge 2 - Move Zeroes to the End

Moving Zeroes to the End: A JavaScript Solution Introduction:   When working with arrays, there are often times when we need to manipulate their elements to achieve a specific goal. One common problem is moving all zeroes to the end of an array while keeping the order of non-zero elements unchanged. In this blog post, we will explore an elegant solution to this problem using JavaScript. We'll discuss the problem statement, the approach we'll take, and provide a step-by-step guide to implementing the solution. The Problem:   Given an array of integers, the task is to move all zeroes to the end of the array while maintaining the relative order of the non-zero elements. This means that after rearranging the array, all the zeroes should be at the end, and the order of the non-zero elements should remain the same. The Approach:   To solve this problem, we can utilize a two-pointer approach. We'll maintain two pointers, one for iterating through the array and another for keepin...
Post a Comment
Read more