Teaching Kids Programming – Remove One Number to Make Average

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums and an integer k, return true if you can remove exactly one element from the list to make the average equal to exactly k.

Constraints
2 ≤ n ≤ 1,000 where n is length of nums
nums[i], k ≤ 1,000,000
Example 1
Input
nums = [1, 2, 3, 10]
k = 2
Output
True
Explanation
We can take 10 out to reach an average of 2 since (1 + 2 + 3) / 3 = 2

Example 2
Input
nums = [1, 3]
k = 2
Output
False
Explanation
If we remove 1, we get an average of 3 and if we remove 3, we get an average of 1.

Hints:
Can we calculate the sum of all numbers we want to keep?

Just Average Algorithm

We can simulate removing one element (bruteforce) and see it the average is k. This takes O(N) time.

1
2
3
4
5
6
7

class Solution:
    def removeOneAndMakeAverage(self, nums, k):
        total = sum(nums)
        for i in nums:
            if total - i == k * (len(nums) - 1):
                return True
        return False

class Solution:
    def removeOneAndMakeAverage(self, nums, k):
        total = sum(nums)
        for i in nums:
            if total - i == k * (len(nums) - 1):
                return True
        return False

Alternatively, we can remove the new sum (calculated via the average*len), and the difference should be the number to remove – and checking this in array takes O(N) time.

1
2
3

class Solution:
    def removeOneAndMakeAverage(self, nums, k):
        return (sum(nums) - (len(nums) - 1) * k) in nums

class Solution:
    def removeOneAndMakeAverage(self, nums, k):
        return (sum(nums) - (len(nums) - 1) * k) in nums

–EOF (The Ultimate Computing & Technology Blog) —