6. Find the duplicate in an array of N+1 integers

Source: Find the duplicate in an array of N+1 integers

Problem Statement

Example 1:
Input: arr = [1, 3, 4, 2, 2]
Output: 2
Explanation: Since 2 is the duplicate number, the answer will be 2.

Example 2:
Input: arr = [3, 1, 3, 4, 2]
Output: 3
Explanation: Since 3 is the duplicate number, the answer will be 3.

Disclaimer: It's highly recommend trying to solve it before looki""ng at the solution.

Approach 1: Better Approach

• Sort the array in ascending order. This ensures that any duplicate numbers are adjacent to each other.

  • Iterate through the sorted array and check if the current element is equal to the next element (i.e., arr[i] == arr[i+1]).

  • If the condition arr[i] == arr[i+1] is true, then arr[i] is a duplicate number.

  • Return or store the duplicate element as needed.

• Complexity: Time Complexity: O(N log N), where N is the size of the array. This is because we are sorting the array, which takes O(N log N) time.

  Space Complexity: O(1), as we are sorting the array in-place and not using any additional data structures that grow with input size.

Solutions

C++

#include <bits/stdc++.h>
using namespace std;

// find the duplicate by sorting and checking adjacent elements
int findDuplicate(vector<int>& arr) {
  // get size
  int n = arr.size();
  // sort array in-place
  sort(arr.begin(), arr.end());
  // scan adjacent pairs
  for (int i = 0; i < n - 1; i++) {
    // return when a duplicate is found
    if (arr[i] == arr[i + 1]) {
      return arr[i];
    }
  }
  // fallback if no duplicate found
  return -1;
}

// program entry
int main() {
  // declare and initiali""ze array
  vector<int> arr = {1, 3, 4, 2, 2};
  // print result
  cout << "The duplicate element is " << findDuplicate(arr) << endl;
  // exit
  return 0;
}

Java

import java.util.*;

// utility class holding the logic
class Solution {
    // find the duplicate by sorting and checking adjacent elements
    static int findDuplicate(int[] arr) {
        // get size
        int n = arr.length;
        // sort array in-place
        Arrays.sort(arr);
        // scan adjacent pairs
        for (int i = 0; i < n - 1; i++) {
            // return when a duplicate is found
            if (arr[i] == arr[i + 1]) {
                return arr[i];
            }
        }
        // fallback if no duplicate found
        return -1;
    }
}

// separate main class
public class Main {
    // program entry
    public static void main(String[] args) {
        // declare and initialize array
        int[] arr = new int[]{1, 3, 4, 2, 2};
        // print result
        System.out.println("The duplicate element is " + Solution.findDuplicate(arr));
    }
}

Python

# find the duplicate by sorting and checking adjacent elements
def find_duplicate(arr: list[int]) -> int:
    # get size
    n = len(arr)
    # sort array in-place
    arr.sort()
    # scan adjacent pairs
    for i in range(n - 1):
        # return when a duplicate is found
        if arr[i] == arr[i + 1]:
            return arr[i]
    # fallback if no duplicate found
    return -1

# program entry
def main():
    # declare and initialize array
    arr = [1, 3, 4, 2, 2]
    # print result
    print("The duplicate element is " + str(find_duplicate(arr)))

# run main
if __name__ == "__main__":
    main()

JavaScript

// find the duplicate by sorting and checking adjacent elements
function findDuplicate(arr) {
    // get size
    const n = arr.length;
    // sort array in-place
    arr.sort((a, b) => a - b);
    // scan adjacent pairs
    for (let i = 0; i < n - 1; i++) {
        // return when a duplicate is found
        if (arr[i] === arr[i + 1]) {
        return arr[i];
        }
    }
    // fallback if no duplicate found
  return -1;
}

// program entry
function main() {
    // declare and initialize array
    const arr = [1, 3, 4, 2, 2];
    // print result
    console.log("The duplicate element is " + findDuplica""te(arr));
}

// run main
main();

C++ (2)

#include <bits/stdc++.h>
using namespace std;

// find the duplicate using a frequency array
int findDuplicate(vector<int>& arr) {
  // get size
  int n = arr.size();
  // allocate frequency array initialized to 0
  vector<int> freq(n + 1, 0);
  // scan elements
  for (int i = 0; i < n; i++) {
    // return current value if already seen
    if (freq[arr[i]] == 0) {
      // mark as seen
      freq[arr[i]] += 1;
    } else {
      // duplicate found
      return arr[i];
    }
  }
  // fallback if none (per original)
  return 0;
}

// program entry
int main() {
  // declare and initialize array
  vector<int> arr = {1, 3, 4, 2, 3};
  // print result
  cout << "The duplicate element is " << findDuplicate(arr) << endl;
  // exit
  return 0;
}

Java (2)

import java.util.*;

// utility with frequency-array duplicate finder
class Solution {
    // find the duplicate using a frequency array
    static int findDuplicate(int[] arr) {
        // get size
        int n = arr.length;
        // allocate frequency array initialized to 0
        int[] freq = new int[n + 1];
        // scan elements
        for (int i = 0; i < n; i++) {
            // return current value if already seen
            if (freq[arr[i]] == 0) {
                // mark as seen
                freq[arr[i]] += 1;
            } else {
                // duplicate found
                return arr[i];
            }
        }
        // fallback if none (per original)
        return 0;
    }
}

// separate main class
public class Main {
    // program entry
    public static void main(String[] args) {
        // declare and initialize array
        int[] arr = new int[]{1, 3, 4, 2, 3};
        // print result
        System.out.println("The duplicate element is " + Solution.findDuplicate(arr));
    }
}

Python (2)

# find the duplicate using a frequency array
def find_duplicate(arr: list[int]) -> int:
# get size
    n = len(arr)
    # allocate frequency array initialized to 0
    freq = [0] * (n + 1)
    # scan elements
    for x in arr:
        # return current value if already seen
        if freq[x] == 0:
            # mark as seen
            freq[x] += 1
        else:
            # duplicate found
            return x
    # fallback if none (per original)
    return 0

# program entry
def main():
    # declare and initialize array
    arr = [1, 3, 4, 2, 3]
    # print result
    print("The duplicate element is " + str(find_duplicate(arr)))

# run main
if __name__ == "__main__":
    main()

JavaScript (2)

// find the duplicate using a frequency array
function findDuplicate(arr) {
  // get size
  const n = arr.length;
  // allocate frequency array initialized to 0
  const freq = new Array(n + 1).fill(0);
  // scan elements
  for (let i = 0; i < n; i++) {
    // return current value if already seen
    if (freq[arr[i]] === 0) {
      // mark as seen
      freq[arr[i]] += 1;
    } else {
      // duplicate found
      return arr[i];
    }
  }
  // fallback if none (per original)
  return 0;
}

// program entry
function main() {
  // declare and initialize array
  const arr = [1, 3, 4, 2, 3];
  // print result
  console.log("The duplicate element is " + findDuplicate(arr));
}

// run main
main();

Approach 2: Optimal Approach

• Initially, we have a linked list with values like: 2, 9, 1, 5, 3, 6, 8, 7, and then we reach back to 9, forming a cycle.

  • The slow and fast pointers both start at the first element of the list. The slow pointer moves one step at a time, and the fast pointer moves two steps at a time.

  • After a few steps, the slow and fast pointers will meet at an index (in this case, at 7).

  • Now, place the fast pointer back to the first element (2) and move both the slow and fast pointers one step at a time.

  • The point where the slow and fast pointers meet again will be the duplicate number in the list (in this case, 9).

  • Intuition: Since there is a duplicate number, a cycle is always formed. The first collision between slow and fast pointers guarantees that a cycle exists.

  • When slow and fast pointers meet, the distance between their collision points represents the cycle length. This allows us to find the duplicate number.

• Complexity: Time Complexity: O(N), where N is the size of the array. This is because we traverse the array at most twice (once to find the intersection and once to find the duplicate).

  Space Complexity: O(1), as we are using only a constant amount of space for the slow and fast pointers, regardless of the input size.

Solutions

C++

#include <bits/stdc++.h>
using namespace std;

// find the duplicate using Floyd's Tortoise and Hare cycle detection
int findDuplicate(vector<int>& nums) {
  // initialize pointers at the start
  int slow = nums[0];
  int fast = nums[0];

  // move slow by 1 step and fast by 2 steps until they meet
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow != fast);

  // reset fast to start to find the entrance to the cycle
  fast = nums[0];

  // move both by 1 step until they meet at the duplicate
  while (slow != fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  // return the duplicate value
  return slow;
}

// program entry
int main() {
  // initialize input
  vector<int> arr = {1, 3, 4, 2, 3};

  // print result
  cout << "The duplicate element is " &l""t;< findDuplicate(arr) << endl;

  // exit
  return 0;
}

Java

import java.util.*;

// solution utility using Floyd's Tortoise and Hare
class Solution {
    // find the duplicate using cycle detection
    static int findDuplicate(int[] nums) {
        // initialize pointers at the start
        int slow = nums[0];
        int fast = nums[0];

        // move slow by 1 step and fast by 2 steps until they meet
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // reset fast to start to find the entrance to the cycle
        fast = nums[0];

        // move both by 1 step until they meet at the duplicate
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        // return the duplicate value
        return slow;
    }
}

// separate main class
public class Main {
    // program entry
    public static void main(String[] args) {
        // initialize input
        int[] arr = new int[]{1, 3, 4, 2, 3};

        // compute and print result
        System.out.println("The duplicate element is " + Solution.findDuplicate(arr));
    }
}

Python

# find the duplicate using Floyd's Tortoise and Hare cycle detection
def find_duplicate(nums: list[int]) -> int:
    # initialize pointers at the start
    slow = nums[0]
    fast = nums[0]

    # move slow by 1 step and fast by 2 steps until they meet
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # reset fast to start to find the entrance to the cycle
    fast = nums[0]

    # move both by 1 step until they meet at the duplicate
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    # return the duplicate value
    return slow

# program entry
def main():
    # initialize input
    arr = [1, 3, 4, 2, 3]

    # compute and print result
    print("The duplicate element is " + str(find_duplicate(arr)))

# run main
if __name__ == "__main__":
    main()

JavaScript

// find the duplicate using Floyd's Tortoise and Hare cycle detection
function findDuplicate(nums) {
  // initialize pointers at the start
  let slow = nums[0];
  let fast = nums[0];

  // move slow by 1 step and fast by 2 steps until they meet
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  // reset fast to start to find the entrance to the cycle
  fast = nums[0];

  // move both by 1 step until they meet at the duplicate
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  // return the duplicate value
  return slow;
}

// program entry
function main() {
  // initialize input
  const arr = [1, 3, 4, 2, 3];

  // compute and print result
  console.log("The duplicate element is " + findDuplicate(arr));
}

// run main
main();

Reference

• TakeUForward