Teaching Kids Programming – N-Repeated Element in Size 2N Array (Pigeonhole Principle)

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 (Pigeonhole Principle)

Given 2N numbers and 50% of them is duplicate. That means in at least one of the subarray that is size of two, we have a duplicate number. We can extend the case: two duplicates must be in at least one of the subarray that is size of 4.

Thus, we can check the numbers at distance 1, 2, and 3 of the neighbour numbers.

1
2
3
4
5
6

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        for k in range(1, 4):
            for i in range(len(nums) - k):
                if nums[i] == nums[i + k]:
                    return nums[i]

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        for k in range(1, 4):
            for i in range(len(nums) - k):
                if nums[i] == nums[i + k]:
                    return nums[i]

This can be optimised to check the next number or the alternated number. And the exception is that the [1,2,3,1] where the duplicate is the last/first number. The time complexity is O(N) for example, [1,2,3,4,5,…,N,N,N,N,…N]

1
2
3
4
5
6

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        for i in range(len(nums) - 2):
            if nums[i] == nums[i + 1] or nums[i] == nums[i + 2]:
                return nums[i]
        return nums[-1]

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        for i in range(len(nums) - 2):
            if nums[i] == nums[i + 1] or nums[i] == nums[i + 2]:
                return nums[i]
        return nums[-1]

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) —