1500. Count Largest Group¶

LeetCode Problem View on GitHub

1500. Count Largest Group

Easy

You are given an integer n.

Each number from 1 to n is grouped according to the sum of its digits.

Return the number of groups that have the largest size.

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

Solution¶

class Solution {
    public int countLargestGroup(int n) {
        int freq[] = new int[100];
        for (int i = 1; i <= n; i++) {
            freq[solve(i)]++;
        }
        int maxi = 0, count = 0;
        for (int ele : freq) maxi = Math.max(maxi, ele);
        for (int ele : freq) if (ele == maxi) count++;
        return count;
    }
    private int solve(int n) {
        int temp = n;
        int sum = 0;
        while (temp > 0) {
            sum += temp % 10;
            temp /= 10;
        }
        return sum;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here