1399. Count Largest Group
Problem Description
In this problem, you are given an integer n
. Your task is to count how numbers from 1
to n
can be grouped based on the sum of their digits. Then, you need to return the count of the groups with the largest size. A group's size is determined by how many numbers share the same digit sum. For example, if n
is 13, the numbers 11
(1+1=2) and 20
(2+0=2) would belong to the same group with a digit sum of 2. If the group with a digit sum of 2 has the most numbers in it, you would include that in your count of the largest groups.
Intuition
To solve this problem, the approach is to create a map that will keep track of how many times each digit sum appears across the numbers from 1
to n
. The key intuition is that instead of directly grouping numbers and then comparing sizes, we can efficiently tally counts for each possible digit sum using a map or dictionary.
Here's the process to arrive at the solution:
- We iterate through all numbers from
1
ton
. - For each number, we calculate the sum of its digits.
- We record the digit sum in a counter (dictionary) by incrementing the corresponding digit sum's count.
- As we update the counter, we also keep track of the maximum count (size of the largest group) encountered so far.
- If we encounter a digit sum with a count higher than our current maximum, we update the maximum and reset our answer to 1 since we have found a larger group size.
- If we encounter a digit sum with a count equal to the maximum, we increment our answer because this is another group of the same largest size.
The final answer is the count of digit sum groups/counts that equal the maximum size we found throughout the iteration.
The provided Python solution follows this intuition and keeps track of the digit sums using the Counter
class from the collections
module, offering a clean and efficient way to manage the counts.
Learn more about Math patterns.
Solution Approach
The solution uses a hash table and some basic arithmetic operations to solve the problem. Specifically, it employs a Counter
object from Python's collections
module, which is a subclass of dictionary designed to count hashable objects.
Here's a detailed walk-through of the implementation:
-
A
Counter
calledcnt
is initialized to store the frequency of each possible digit sum. It maps each sum to the number of times it has appeared. -
Two variables,
ans
andmx
, are initialized to0
.ans
will store the final answer (the number of groups with the largest size), andmx
will store the current maximum size encountered. -
We iterate over every number from
1
ton
inclusive, using afor
loop. -
Inside the loop, for each number
i
, we calculate the digit sum by repeatedly takingi % 10
(which gives the last digit) and adding it to an accumulator variables
. After each step, we updatei
toi // 10
which effectively removes the last digit fromi
. This process continues in awhile
loop untili
becomes0
. -
We then update the Counter
cnt
by incrementing the count for the computed digit sums
. -
After updating
cnt
, we compare the updated countcnt[s]
to the currentmx
. If the new count is greater, this means we have a new largest group size, so we updatemx
tocnt[s]
, and resetans
to1
as this is the first group of this new size. -
If the new count
cnt[s]
is equal to the currentmx
, then we have found another group of the current largest size, and we incrementans
by1
. -
After the loop has finished executing, the variable
ans
holds the number of groups that have the largest size, and we return this value.
Mathematically, given s
as the sum of digits of a number i
, the operation to update cnt
can be represented as:
cnt[s] += 1
And the comparisons to determine if we found a new largest group size or another group of that size is:
if mx < cnt[s]: mx = cnt[s] ans = 1 elif mx == cnt[s]: ans += 1
The provided code efficiently calculates the required group sizes and finds the number of groups with the largest size, adhering to the solution approach described.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example using n = 15
to illustrate the solution approach:
-
Initialize a
Counter
namedcnt
and two variables:ans
set to0
andmx
also set to0
. -
We begin to iterate from
1
to15
. Firstly, we take number1
, the sum of its digits is1
. We updatecnt[1]
to be1
. Sincemx < cnt[1]
,mx
is now set to1
andans
is set to1
. -
Next, we consider number
2
, the sum of its digits is2
. We updatecnt[2]
to be1
. Nowmx
is still1
, butans
is now2
, as we have two groups (for digit sums1
and2
) with the same size,1
. -
This process continues for numbers
3
,4
,5
,6
,7
,8
, and9
, each forming a new group of size1
.ans
is now9
. -
Number
10
has a digit sum of1
, updatingcnt[1]
to2
. Nowmx < cnt[1]
, so we setmx
to2
andans
to1
, since we have found a larger group size (group of digit sum1
is now the largest with size2
). -
Numbers
11
,12
, and13
have digit sums of2
,3
, and4
respectively:- For
11
,cnt[2]
becomes2
, tying with the current maximum size. This incrementsans
to2
because there's another group with the same size as the largest found so far. - For
12
,cnt[3]
becomes2
, tying again, andans
goes up to3
. - For
13
,cnt[4]
becomes2
, tying again, andans
goes up to4
.
- For
-
For Number
14
, the digit sum is5
, and updatingcnt[5]
to2
ties with the current max;ans
is incremented to5
. -
For Number
15
, the digit sum is6
, which also ties with the max after updatingcnt[6]
to2
;ans
is incremented to6
.
After considering all numbers from 1
to 15
, we find there are 6
groups tied for the largest size, which is 2
. The groups are the digit sums of 1
, 2
, 3
, 4
, 5
, and 6
.
Therefore, the final answer that would be returned is 6
, representing the count of the largest groups by digit sum from 1
to 15
.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def countLargestGroup(self, n: int) -> int:
5 # Initialize a counter to keep track of the sum of digits
6 digit_sum_counter = Counter()
7 # Initialize variables to keep track of the maximum count and the number of groups with that count
8 max_count = 0
9 num_groups_with_max_count = 0
10
11 # Iterate over each integer from 1 to n
12 for i in range(1, n + 1):
13 sum_of_digits = 0
14 current_number = i
15 # Calculate the sum of the digits of the current number
16 while current_number:
17 sum_of_digits += current_number % 10
18 current_number //= 10
19 # Increment the count for the group represented by this sum of digits
20 digit_sum_counter[sum_of_digits] += 1
21
22 # Update max_count and num_groups_with_max_count based on the current sums
23 if max_count < digit_sum_counter[sum_of_digits]:
24 max_count = digit_sum_counter[sum_of_digits]
25 num_groups_with_max_count = 1
26 elif max_count == digit_sum_counter[sum_of_digits]:
27 num_groups_with_max_count += 1
28
29 # Return the number of groups that have the maximum size
30 return num_groups_with_max_count
31
1class Solution {
2 public int countLargestGroup(int n) {
3 // Initialize a count array to keep track of the frequency of sums.
4 int[] sumFrequency = new int[40]; // The maximum sum for n digits can be 9 * 4 = 36, thus 40 is safe.
5 int largestGroupSizeCount = 0; // This will hold the count of groups with the largest size.
6 int maxGroupSize = 0; // This will hold the maximum size of any group encountered.
7
8 // Loop through each number from 1 to n.
9 for (int i = 1; i <= n; ++i) {
10 int sumOfDigits = 0; // This will hold the sum of digits of the current number.
11
12 // Loop to calculate the sum of digits of the current number.
13 for (int x = i; x > 0; x /= 10) {
14 sumOfDigits += x % 10;
15 }
16
17 // Increase the frequency count of the current sum.
18 ++sumFrequency[sumOfDigits];
19
20 // If the current sum frequency is greater than the maxGroupSize, update maxGroupSize and reset largestGroupSizeCount.
21 if (maxGroupSize < sumFrequency[sumOfDigits]) {
22 maxGroupSize = sumFrequency[sumOfDigits];
23 largestGroupSizeCount = 1;
24 } else if (maxGroupSize == sumFrequency[sumOfDigits]) {
25 // If the current sum frequency is equal to the maxGroupSize, increment the count.
26 ++largestGroupSizeCount;
27 }
28 }
29
30 // Return the count of the sums that have the largest group size.
31 return largestGroupSizeCount;
32 }
33}
34
1class Solution {
2public:
3 int countLargestGroup(int n) {
4 // Array to store counts of sum groups with a large enough size
5 // to avoid the constant reallocation.
6 int sumCounts[40] = {};
7
8 // Variables to keep track of the largest group size and the
9 // number of groups with this size.
10 int largestGroupSizeCount = 0;
11 int largestGroupSize = 0;
12
13 // Iterate over all numbers from 1 to n.
14 for (int i = 1; i <= n; ++i) {
15 int digitSum = 0; // This will hold the sum of the digits.
16
17 // Calculate the sum of digits of the current number.
18 for (int x = i; x; x /= 10) {
19 digitSum += x % 10;
20 }
21
22 // Increment the count of the found sum.
23 ++sumCounts[digitSum];
24
25 // If we've found a new maximum size for our digit groups.
26 if (largestGroupSize < sumCounts[digitSum]) {
27 largestGroupSize = sumCounts[digitSum]; // Update the largest group size.
28 largestGroupSizeCount = 1; // Reset the count to reflect this new largest group size.
29 } else if (largestGroupSize == sumCounts[digitSum]) {
30 // If this group size is the same as the current largest, increment the count.
31 ++largestGroupSizeCount;
32 }
33 }
34
35 // Return the number of groups that have the largest size.
36 return largestGroupSizeCount;
37 }
38};
39
1function countLargestGroup(n: number): number {
2 // Initialize an array to store the count of each sum of digits
3 const sumCounts: number[] = new Array(40).fill(0);
4 let maxCount = 0; // Variable to keep track of the maximum count of any sum
5 let numMaxGroups = 0; // Variable to count how many groups have this maximum count
6
7 // Iterate over each number from 1 to n
8 for (let i = 1; i <= n; ++i) {
9 let sum = 0; // Variable to store sum of digits of the current number i
10 // Calculate the sum of digits of i
11 for (let x = i; x > 0; x = Math.floor(x / 10)) {
12 sum += x % 10;
13 }
14 // Increase the count of this sum in the 'sumCounts' array
15 sumCounts[sum]++;
16 // Check if the current sum has a new maximum count
17 if (maxCount < sumCounts[sum]) {
18 maxCount = sumCounts[sum]; // Update the max count
19 numMaxGroups = 1; // Reset the number of max groups as a new max is found
20 } else if (maxCount === sumCounts[sum]) {
21 // If the current sum is equal to the maximum count,
22 // increment the number of groups with max count
23 numMaxGroups++;
24 }
25 }
26 // Return the number of groups with the maximum count of sums
27 return numMaxGroups;
28}
29
Time and Space Complexity
The given Python code computes the size of the largest group of numbers based on the sum of the digits of each number from 1
to n
.
Time Complexity:
To analyze the time complexity, let's examine the primary operations in the code:
-
The for loop runs from
1
ton
which gives usO(n)
complexity. -
Inside the loop, we calculate the sum of digits of an integer
i
. Since in the worst case scenario integeri
can have at mostO(log n)
digits (since every increase by an order of magnitude adds one digit), the inner while loop runs inO(log n)
time for each number. -
Updating the counter for sum
s
and comparingmx
withcnt[s]
for each number is done in constant time,O(1)
.
The overall time complexity is thus the product of the complexity of the outer loop and the inner while loop, which gives us O(n log n)
.
Space Complexity:
For space complexity, we need to consider:
-
The counter
cnt
will at most have an entry for each distinct sum of digits s that we can get from numbers1
ton
. In the worst case, this sum would not exceed9 * log n
(assuming each digit of a numbern
is9
). Therefore, the space complexity due to thecnt
map isO(log n)
. -
The variables
s
,i
,mx
, andans
use constant spaceO(1)
.
The space complexity of the algorithm is mainly determined by the cnt
map. Hence, the overall space complexity is O(log n)
.
The code you provided is already efficient with respect to big-O notation, and any further optimization would depend on specific constraints or requirements of the problem not detailed here.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!