Find the Duplicate Number - C Solution

1. Introduction

This blog post delves into an intriguing problem in array manipulation using C programming: finding a duplicate number in an array. The challenge lies in efficiently detecting a repeated number in a given array of integers where each element appears only once or twice.

Problem

Given an array of integers where each integer appears once or twice, the task is to find and return the number that appears twice. This problem tests our ability to manipulate arrays and search for duplicates in an optimized way.

2. Solution Steps

1. Use a two-pointer approach, similar to cycle detection in a linked list.

2. Treat the array as a linked list, where each element's value is the next node's index.

3. Find the intersection point in the cycle (if it exists).

4. Find the entrance to the cycle, which is the duplicate number.

5. Return the duplicate number.

3. Code Program

#include <stdio.h>

// Function to find the duplicate number
int findDuplicate(int* nums, int numsSize) {
    if (numsSize > 1) {
        int slow = nums[0];
        int fast = nums[nums[0]];

        // Finding the intersection point
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        // Finding the entrance to the cycle
        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
    return -1;
}

// Main function to demonstrate findDuplicate function
int main() {
    int nums[] = {1, 3, 4, 2, 2}; // Example input
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int duplicate = findDuplicate(nums, numsSize); // Call the function
    printf("Output: %d\n", duplicate); // Print the result
    return 0;
}

Output:

2

Explanation:

The program implements an efficient method to find the duplicate number in an array [1, 3, 4, 2, 2]. 

It uses the two-pointer approach, treating the array as a linked list where each element points to the index specified by its value. The slow and fast pointers help in detecting a cycle (the duplicate number). Once the cycle is detected, the slow pointer is reset, and both pointers move at the same speed to find the cycle's entrance, which is the duplicate number. In this example, the number 2 is the duplicate, so the output is 2. 

This approach ensures O(n) time complexity and O(1) space complexity, making it an efficient solution.