Find the Duplicate Number

1. Problem Description

Given an array nums containing n + 1 integers, where every integer is between 1 and n inclusive, at least one repeated integer is guaranteed to exist.

Assume nums contains only one repeated integer. Find that duplicate number.

2. Approach

1. Approach 1
   • Sort first
   • Traverse and compare adjacent numbers
2. Approach 2
   • Use a map to count occurrences
3. Approach 3
   • In-place hash
4. Binary search

3. Implementation

3.1. Sort

import "sort"

// Time: O(nlogn)
// Space: O(1)
func findDuplicate(nums []int) int {
	sort.Ints(nums)
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] == nums[i+1] {
			return nums[i]
		}
	}

	return 0
}

3.2. HashMap

// Time: O(n)
// Space: O(n)
func findDuplicate2(nums []int) int {
	m := make(map[int]int, 0)
	for _, num := range nums {
		m[num]++
	}
	for num, count := range m {
		if count >= 2 {
			return num
		}
	}

	return 0
}

3.3. In-place Hash

func findDuplicate(nums []int) int {
    for i := range nums {
        for {
            index := indexFor(nums[i])
            if index == i {
                break
            }
            if nums[index] == nums[i] {
                return nums[index]
            }
            nums[index], nums[i] = nums[i], nums[index]
        }
    }
    return 0
}

func indexFor(val int)int{
    return val
}

3.4. Binary Search

// Binary search
// Time: O(NlogN)
// Space: O(1)
func findDuplicate3(nums []int) int {
	left := 1
	right := len(nums) - 1
	for left < right {
		mid := left + (right-left)>>1

		cnt := getCnt(nums, mid)

		if cnt > mid {
			right = mid
		} else {
			left = mid + 1
		}

	}
	return left
}

func getCnt(nums []int, mid int) int {
	cnt := 0
	for _, num := range nums {
		if num <= mid {
			cnt++
		}
	}
	return cnt
}

4. References

• 287. Find the Duplicate Number - LeetCode