Question

Formatted question description: https://leetcode.ca/all/287.html

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Constraints:

1 <= n <= 10⁵
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem in linear runtime complexity?

Algorithm

Binary search

Using the binary search method, search in the interval [1, n], first find the midpoint mid, then traverse the entire array, count all the numbers less than or equal to mid,

If the number is less than or equal to mid, the repeated value is between [mid+1, n],
On the contrary, the repeated value should be between [1, mid-1], Until the search is completed, low index then is the repeated value we require.

Bit

For each digit, the number of 1s in this digit in all numbers from 0 to n-1 should be fixed. If there are more 1s in this digit in all numbers in the nums array, it means that the this 1 is in duplicated number. We can reproduce the repeated number by adding up all the 1 bits of the repeated number.

Code

import java.util.Arrays;

public class Find_the_Duplicate_Number {

    class Solution_bit {
        public int findDuplicate(int[] nums) {
            int res = 0, len = nums.length;
            for (int i = 0; i < 32; ++i) {
                int bit = (1 << i), cnt1 = 0, cnt2 = 0;
                for (int k = 0; k < len; ++k) { // len is actually n+1
                    if ((k & bit) > 0) ++cnt1; // 1s count with no duplicate
                    if ((nums[k] & bit) > 0) ++cnt2; // 1s count with no duplicate
                }
                if (cnt2 > cnt1) res += bit;
            }
            return res;

        }
    }

    class Solution {
        public int findDuplicate(int[] nums) {
            int left = 1, right = nums.length;
            while (left < right) {
                int mid = left + (right - left) / 2, cnt = 0;
                for (int num : nums) {
                    if (num <= mid) ++cnt;
                }
                // eg. 1,1,1,1,1,1,1,2
                // eg. 1,2,2,2,2,2,2,2
                if (cnt <= mid) left = mid + 1;
                else right = mid;
            }
            return right;
        }
    }

    class Solution_sort {
        public int findDuplicate(int[] nums) {
            Arrays.sort(nums);
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == nums[i-1]) {
                    return nums[i];
                }
            }

            return -1;
        }
    }
}

############

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            int cnt = 0;
            for (int v : nums) {
                if (v <= mid) {
                    ++cnt;
                }
            }
            if (cnt > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

// OJ: https://leetcode.com/problems/find-the-duplicate-number/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int findDuplicate(vector<int>& A) {
        int L = 1, R = A.size() - 1;
        while (L < R) {
            int M = (L + R) / 2, cnt = 0;
            for (int n : A) cnt += n <= M;
            if (cnt <= M) L = M + 1;
            else R = M;
        }
        return L;
    }
};

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left, right = 1, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            cnt = sum(v <= mid for v in nums)
            if cnt > mid:
                right = mid
            else:
                left = mid + 1
        return left

############

class Solution(object):
  def findDuplicate(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums) - 1
    start, end = 1, n
    while start + 1 < end:
      mid = start + (end - start) / 2
      count = 0
      for num in nums:
        if num < mid:
          count += 1
      if count >= mid:
        end = mid
      else:
        start = mid
    if nums.count(start) > nums.count(end):
      return start
    return end

func findDuplicate(nums []int) int {
	left, right := 1, len(nums)-1
	for left < right {
		mid := (left + right) >> 1
		cnt := 0
		for _, v := range nums {
			if v <= mid {
				cnt++
			}
		}
		if cnt > mid {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

function findDuplicate(nums: number[]): number {
    let left = 1,
        right = nums.length - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        let cnt = 0;
        for (let v of nums) {
            if (v <= mid) {
                ++cnt;
            }
        }
        if (cnt > mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
    let left = 1,
        right = nums.length - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        let cnt = 0;
        for (let v of nums) {
            if (v <= mid) {
                ++cnt;
            }
        }
        if (cnt > mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

impl Solution {
    #[allow(dead_code)]
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let mut left = 0;
        let mut right = nums.len() - 1;

        while left < right {
            let mid = (left + right) >> 1;
            let cnt = nums
                .iter()
                .filter(|x| **x <= mid as i32)
                .count();
            if cnt > mid {
                right = mid;
            } else  {
                left = mid + 1;
            }
        }

        left as i32
    }
}

287 - Find the Duplicate Number

Question

Algorithm

Binary search

Bit

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Binary search

Bit

Code

All Problems

All Solutions