Skip to content

1399. Count Largest Group

SourceBiweekly Contest 23 Q1DifficultyEasyRating1341

Description

You are given an integer n.

We need to group the numbers from 1 to n according to the sum of its digits. For example, the numbers 14 and 5 belong to the same group, whereas 13 and 3 belong to different groups.

Return the number of groups that have the largest size, i.e. the maximum number of elements.

 

Example 1:

Input: n = 13
Output: 4
Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13:
[1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9].
There are 4 groups with largest size.

Example 2:

Input: n = 2
Output: 2
Explanation: There are 2 groups [1], [2] of size 1.

 

Constraints:

  • 1 <= n <= 104

Solutions

Solution 1: Hash Table or Array

Thinking

Group \(1..n\) by digit sum and count how many groups share the maximum size. \(n \le 10^4\), so digit sums are at most \(36\). Sum digits for each integer, tally group sizes, and track the current maximum size together with how many groups attain it.

We note that the number does not exceed \(10^4\), so the sum of the digits also does not exceed \(9 \times 4 = 36\). Therefore, we can use a hash table or an array of length \(40\), denoted as \(cnt\), to count the number of each sum of digits, and use a variable \(mx\) to represent the maximum count of the sum of digits.

We enumerate each number in \([1,..n]\), calculate its sum of digits \(s\), then increment \(cnt[s]\) by \(1\). If \(mx < cnt[s]\), we update \(mx = cnt[s]\) and set \(ans\) to \(1\). If \(mx = cnt[s]\), we increment \(ans\) by \(1\).

Finally, we return \(ans\).

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the given number.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def countLargestGroup(self, n: int) -> int:
        cnt = Counter()
        ans = mx = 0
        for i in range(1, n + 1):
            s = 0
            while i:
                s += i % 10
                i //= 10
            cnt[s] += 1
            if mx < cnt[s]:
                mx = cnt[s]
                ans = 1
            elif mx == cnt[s]:
                ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int countLargestGroup(int n) {
        int[] cnt = new int[40];
        int ans = 0, mx = 0;
        for (int i = 1; i <= n; ++i) {
            int s = 0;
            for (int x = i; x > 0; x /= 10) {
                s += x % 10;
            }
            ++cnt[s];
            if (mx < cnt[s]) {
                mx = cnt[s];
                ans = 1;
            } else if (mx == cnt[s]) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countLargestGroup(int n) {
        int cnt[40]{};
        int ans = 0, mx = 0;
        for (int i = 1; i <= n; ++i) {
            int s = 0;
            for (int x = i; x; x /= 10) {
                s += x % 10;
            }
            ++cnt[s];
            if (mx < cnt[s]) {
                mx = cnt[s];
                ans = 1;
            } else if (mx == cnt[s]) {
                ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func countLargestGroup(n int) (ans int) {
    cnt := [40]int{}
    mx := 0
    for i := 1; i <= n; i++ {
        s := 0
        for x := i; x > 0; x /= 10 {
            s += x % 10
        }
        cnt[s]++
        if mx < cnt[s] {
            mx = cnt[s]
            ans = 1
        } else if mx == cnt[s] {
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function countLargestGroup(n: number): number {
    const cnt: number[] = Array(40).fill(0);
    let mx = 0;
    let ans = 0;
    for (let i = 1; i <= n; ++i) {
        let s = 0;
        for (let x = i; x; x = Math.floor(x / 10)) {
            s += x % 10;
        }
        ++cnt[s];
        if (mx < cnt[s]) {
            mx = cnt[s];
            ans = 1;
        } else if (mx === cnt[s]) {
            ++ans;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
impl Solution {
    pub fn count_largest_group(n: i32) -> i32 {
        let mut cnt = vec![0; 40];
        let mut ans = 0;
        let mut mx = 0;

        for i in 1..=n {
            let mut s = 0;
            let mut x = i;
            while x > 0 {
                s += x % 10;
                x /= 10;
            }
            cnt[s as usize] += 1;
            if mx < cnt[s as usize] {
                mx = cnt[s as usize];
                ans = 1;
            } else if mx == cnt[s as usize] {
                ans += 1;
            }
        }

        ans
    }
}

Comments