Teaching Kids Programming – N-Repeated Element in Size 2N Array (Random Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an integer array nums with the following properties:

nums.length == 2 * n.
nums contains n + 1 unique elements.
Exactly one element of nums is repeated n times.
Return the element that is repeated n times.

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

Example 2:
Input: nums = [2,1,2,5,3,2]
Output: 2

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

Constraints:
2 <= n <= 5000
nums.length == 2 * n
0 <= nums[i] <= 10^4
nums contains n + 1 unique elements and one of them is repeated exactly n times.

N-Repeated Element in Size 2N Array (Random Algorithm)

Sometimes Random can be quite a powerful algorithm especially if the odds are high. One typical Random algorithm is Bogo sorting (or Monkey sorting), it has the following code:

1
2
3
4
5

import random
def bogo(arr):
    while not is_array_sorted(arr):
        random.shuffle(arr)
    return arr

import random
def bogo(arr):
    while not is_array_sorted(arr):
        random.shuffle(arr)
    return arr

However, when the number of the elements in the array is large, the probability of getting a sorted array after shuffling is becoming significantly lower. Given N elements, there are N! different arrangements, so the probability of getting a sorted array is 1/N!, and on average it takes N! times to make array sorted. The best time complexity is O(1) if you get really lucky, and O(N!) on average, but in the worst case when the odds are not on your side, if could take forever, and thus O(+inf).

Similarly, in this problem, there are 50% duplicate numbers, thus the probability for the first time picking the duplicate number is 50%, and picking two duplicate numbers is O(25%). However, we have to make sure that we don’t pick the same index twice.

1
2
3
4
5
6
7
8
9
10

import random
 
class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        n = len(nums)
        while True:
            a = random.randint(0, n - 1)
            b = random.randint(0, n - 1)
            if a != b and nums[a] == nums[b]:
                return nums[a]

import random

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        n = len(nums)
        while True:
            a = random.randint(0, n - 1)
            b = random.randint(0, n - 1)
            if a != b and nums[a] == nums[b]:
                return nums[a]

The best time O(1) picking two times straight. The average time O(4), and in the worst case, O(+inf) as we might never be lucky.

N-Repeated Element in Size 2N Array

• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Pigeonhole Principle)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Random Algorithm)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Math)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Sorting)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Hash Map/Set)
• Algorithms: How to Find N-Repeated Element in Size 2N Array?

–EOF (The Ultimate Computing & Technology Blog) —