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

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 (Math)

Given the array, we can easily compute the total sum using the sum function in O(N) time. We can alternatively accumulate the sum in a for loop or using the accumulate function.

Then we can use a set to keep the unique numbers, and we can easily get the sum for this part. The difference divided by N-1 will be the duplicate number.

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        totalSum = sum(nums)
        allNumbers = sum(set(nums))
        return (totalSum - allNumbers) // (len(nums) // 2 - 1)

Time/space complexity is O(N).

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