287. Duplicate number

287_solution1_binarysearch.c

int findDuplicate(int *nums, int numsSize) {
  int left = 1, right = numsSize - 1; // right = n

  while (left < right) {
    int mid = left + (right - left) / 2;

    // count how many numbers are <= mid
    int count = 0;
    for (int i = 0; i < numsSize; i++)
      if (nums[i] <= mid)
        count++;

    if (count > mid)
      right = mid; // duplicate is in [left, mid]
    else
      left = mid + 1; // duplicate is in [mid + 1, right]
  }

  return left;
}

287_solution2_fast_slow.c

int findDuplicate(int *nums, int numsSize) {
  int slow = 0, fast = 0;

  // Phase 1: find a meeting point inside the cycle
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow != fast);

  // Phase 2: find the cycle entrance (the duplicate)
  slow = 0;
  while (slow != fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  return slow;
}

287_solution1_binarysearch.cpp

#include <vector>
using namespace std;

class Solution {
public:
  int findDuplicate(vector<int> &nums) {
    int left = 1, right = nums.size() - 1; // right = n

    while (left < right) {
      int mid = left + (right - left) / 2;

      // count how many numbers are <= mid
      int count = 0;
      for (int x : nums)
        if (x <= mid)
          count++;

      if (count > mid)
        right = mid; // duplicate is in [left, mid]
      else
        left = mid + 1; // duplicate is in [mid + 1, right]
    }

    return left;
  }
};

287_solution2_fast_slow.cpp

#include <vector>
using namespace std;

class Solution {
public:
  int findDuplicate(vector<int> &nums) {
    int slow = 0, fast = 0;

    // Phase 1: find a meeting point inside the cycle
    do {
      slow = nums[slow];
      fast = nums[nums[fast]];
    } while (slow != fast);

    // Phase 2: find the cycle entrance (the duplicate)
    slow = 0;
    while (slow != fast) {
      slow = nums[slow];
      fast = nums[fast];
    }

    return slow;
  }
};

287_solution1_binarysearch.go

package linkedlists

func findDuplicateBinarySearch(nums []int) int {
    left, right := 1, len(nums)-1 // right = n

    for left < right {
        mid := left + (right-left)/2

        // count how many numbers are <= mid
        count := 0
        for _, x := range nums {
            if x <= mid {
                count++
            }
        }

        if count > mid {
            right = mid // duplicate is in [left, mid]
        } else {
            left = mid + 1 // duplicate is in [mid + 1, right]
        }
    }

    return left
}

287_solution2_fast_slow.go

package linkedlists

func findDuplicate(nums []int) int {
    slow, fast := 0, 0

    // Phase 1: find a meeting point inside the cycle
    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }

    // Phase 2: find the cycle entrance (the duplicate)
    slow = 0
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }

    return slow
}

287_solution1_binarysearch.java

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1; // right = n

        while (left < right) {
            int mid = left + (right - left) / 2;

            // count how many numbers are <= mid
            int count = 0;
            for (int x : nums)
                if (x <= mid)
                    count++;

            if (count > mid)
                right = mid; // duplicate is in [left, mid]
            else
                left = mid + 1; // duplicate is in [mid + 1, right]
        }

        return left;
    }
}

287_solution2_fast_slow.java

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;

        // Phase 1: find a meeting point inside the cycle
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Phase 2: find the cycle entrance (the duplicate)
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

287_solution1_binarysearch.js

var findDuplicate = function (nums) {
  let left = 1, right = nums.length - 1; // right = n

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    // count how many numbers are <= mid
    let count = 0;
    for (const x of nums) if (x <= mid) count++;

    if (count > mid) right = mid; // duplicate is in [left, mid]
    else left = mid + 1; // duplicate is in [mid + 1, right]
  }

  return left;
};

287_solution2_fast_slow.js

var findDuplicate = function (nums) {
  let slow = 0, fast = 0;

  // Phase 1: find a meeting point inside the cycle
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  // Phase 2: find the cycle entrance (the duplicate)
  slow = 0;
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  return slow;
};

287_solution1_binarysearch.py

from typing import List


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left, right = 1, len(nums) - 1  # right = n

        while left < right:
            mid = left + (right - left) // 2

            # count how many numbers are <= mid
            count = sum(1 for x in nums if x <= mid)

            if count > mid:
                right = mid  # duplicate is in [left, mid]
            else:
                left = mid + 1  # duplicate is in [mid + 1, right]

        return left

287_solution2_fast_slow.py

from typing import List


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0

        # Phase 1: find a meeting point inside the cycle
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # Phase 2: find the cycle entrance (the duplicate)
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

287_solution1_binarysearch.rs

struct Solution;

impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let (mut left, mut right) = (1, nums.len() as i32 - 1); // right = n

        while left < right {
            let mid = left + (right - left) / 2;

            // count how many numbers are <= mid
            let count = nums.iter().filter(|&&x| x <= mid).count() as i32;

            if count > mid {
                right = mid; // duplicate is in [left, mid]
            } else {
                left = mid + 1; // duplicate is in [mid + 1, right]
            }
        }

        left
    }
}

287_solution2_fast_slow.rs

struct Solution;

impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let (mut slow, mut fast) = (0usize, 0usize);

        // Phase 1: find a meeting point inside the cycle
        loop {
            slow = nums[slow] as usize;
            fast = nums[nums[fast] as usize] as usize;
            if slow == fast {
                break;
            }
        }

        // Phase 2: find the cycle entrance (the duplicate)
        slow = 0;
        while slow != fast {
            slow = nums[slow] as usize;
            fast = nums[fast] as usize;
        }

        slow as i32
    }
}