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 <= 104This approach involves iterating over each number from 1 to n, calculating the sum of its digits, and then grouping these numbers based on their digit sum. We'll use a map (or dictionary) where the keys are the digit sums and the values are the counts of numbers that have those digit sums. Finally, we'll find the largest count and return the number of groups that have this largest count.
The number of digits in input numbers is at most 4 because n can be up to 10,000. Hence, the maximum possible digit sum is 9 + 9 + 9 + 9 = 36. We create an array count of size 37 to store frequencies of each possible digit sum (0 through 36). Then, we iterate over each number from 1 to n, compute its digit sum, and increment the corresponding count. Finally, we determine the maximum group size by iterating over this count array and count how many times this size appears.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because we iterate through numbers from 1 to n and perform a constant-time operation (calculating digit sum).
Space Complexity: O(1) because we only use a fixed size array.
By leveraging the fact that the maximum digit sum for any number from 1 to n is relatively small, we can efficiently use an array instead of a map. The array index corresponds to the digit sum, and the values represent the frequencies (counts) of the respective digit sums.
In this approach, we use an array sized according to the maximum possible digit sum, allowing us to track group sizes directly based on their corresponding digit sums. This is a more space-efficient solution compared to using a Hashtable.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1), as the count array is fixed in size (46).
| Approach | Complexity |
|---|---|
| Grouping by Digit Sum | Time Complexity: O(n) because we iterate through numbers from 1 to n and perform a constant-time operation (calculating digit sum). |
| Using an Array for Counting | Time Complexity: O(n). |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,177 views views
Watch 9 more video solutions →Practice Count Largest Group with our built-in code editor and test cases.
Practice on FleetCode