Welcome to Subscribe On Youtube

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 <= 105
  • 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

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
        }
    }
    

All Problems

All Solutions