Skip to content

3678. Smallest Absent Positive Greater Than Average

SourceBiweekly Contest 165 Q1DifficultyEasyRating1306

Description

You are given an integer array nums.

Return the smallest absent positive integer in nums such that it is strictly greater than the average of all elements in nums.

The average of an array is defined as the sum of all its elements divided by the number of elements.

 

Example 1:

Input: nums = [3,5]

Output: 6

Explanation:

  • The average of nums is (3 + 5) / 2 = 8 / 2 = 4.
  • The smallest absent positive integer greater than 4 is 6.

Example 2:

Input: nums = [-1,1,2]

Output: 3

Explanation:

  • ​​​​​​​The average of nums is (-1 + 1 + 2) / 3 = 2 / 3 = 0.667.
  • The smallest absent positive integer greater than 0.667 is 3.

Example 3:

Input: nums = [4,-1]

Output: 2

Explanation:

  • The average of nums is (4 + (-1)) / 2 = 3 / 2 = 1.50.
  • The smallest absent positive integer greater than 1.50 is 2.

 

Constraints:

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100​​​​​​​

Solutions

Solution 1: Hash Map

Thinking

We want the least positive integer absent from the array and strictly above the average. Starting at \(\max(1,\lfloor\textit{avg}\rfloor+1)\) is enough: a missing positive cannot lie far away.

Store the array in a set and take the integer average as a lower bound. Increment the candidate while it remains in the set.

The walk along the value axis is short and still linear in \(n\).

We use a hash map \(\textit{s}\) to record the elements that appear in the array \(\textit{nums}\).

Then, we calculate the average value \(\textit{avg}\) of the array \(\textit{nums}\), and initialize the answer \(\textit{ans}\) as \(\max(1, \lfloor \textit{avg} \rfloor + 1)\).

If \(\textit{ans}\) appears in \(\textit{s}\), we increment \(\textit{ans}\) until it no longer appears in \(\textit{s}\).

Finally, we return \(\textit{ans}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
class Solution:
    def smallestAbsent(self, nums: List[int]) -> int:
        s = set(nums)
        ans = max(1, sum(nums) // len(nums) + 1)
        while ans in s:
            ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int smallestAbsent(int[] nums) {
        Set<Integer> s = new HashSet<>();
        int sum = 0;
        for (int x : nums) {
            s.add(x);
            sum += x;
        }
        int ans = Math.max(1, sum / nums.length + 1);
        while (s.contains(ans)) {
            ++ans;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int smallestAbsent(vector<int>& nums) {
        unordered_set<int> s;
        int sum = 0;
        for (int x : nums) {
            s.insert(x);
            sum += x;
        }
        int ans = max(1, sum / (int) nums.size() + 1);
        while (s.contains(ans)) {
            ++ans;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func smallestAbsent(nums []int) int {
    s := map[int]bool{}
    sum := 0
    for _, x := range nums {
        s[x] = true
        sum += x
    }
    ans := max(1, sum/len(nums)+1)
    for s[ans] {
        ans++
    }
    return ans
}

1
2
3
4
5
6
7
8
9
function smallestAbsent(nums: number[]): number {
    const s = new Set<number>(nums);
    const sum = nums.reduce((a, b) => a + b, 0);
    let ans = Math.max(1, Math.floor(sum / nums.length) + 1);
    while (s.has(ans)) {
        ans++;
    }
    return ans;
}

Comments