Count Largest Group solution and explanation
Google
9 more videos on this problem
Count Largest Group | Simple Simulation | Dry Run | Leetcode 1399 | codestorywithMIKcodestorywithMIK · 12:05 · 6K views
LeetCode 1399 Count Largest Group | Hash Table | Digit Sum | Easy | Asked in MetaCode Harmony · 15:39 · 946 views
Leetcode 1399. Count Largest Group | Python Prefix Sum + HashMap Logic ExplainedStatLearn Tech · 11:53 · 438 views
1399. Count Largest Group | Leetcode Daily - PythonLeetcode Daily · 7:53 · 424 views
How to Solve "1399 Count Largest Group" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 8:53 · 399 views
LeetCode- 1399. Count Largest GroupPatrick Codes · 7:56 · 256 views
1399. Count Largest Group | Leetcode Daily (POTD) 23 April 2025 | Map | Java | HindiAlgorithmHQ · 6:35 · 183 views
#LeetCode 1399 | Count Largest Group #JavaSleepy Cracker · 5:35 · 127 views
LeetCode 1399. Count Largest Group Java SolutionBrokeBoyCodes · 11:21 · 101 views
Leetcode 1399. Count Largest GroupExpertFunda · 10:04 · 41 views
The problem
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
Approach overview
Problem Overview: You receive an integer n. For every number from 1 to n, compute the sum of its digits and group numbers that share the same digit sum. The task is to determine how many groups end up with the maximum size.
The key observation is that the digit sum acts as a natural grouping key. Once you count how many numbers fall into each digit-sum bucket, the rest of the problem reduces to identifying the largest bucket size and counting how many buckets reach that size.
Approach 1: Grouping by Digit Sum using Hash Table (O(n * d) time, O(k) space)
Iterate through every integer from 1 to n. For each number, compute its digit sum by repeatedly taking num % 10 and dividing by 10. Use a hash table where the key is the digit sum and the value is the count of numbers that produce that sum. Each iteration performs constant work plus digit extraction, so the complexity is O(n * d), where d is the number of digits in n. After filling the map, scan the values to find the maximum frequency and count how many entries match it.
This approach is intuitive and flexible. A hash map handles any digit-sum range without precomputing limits, which keeps the logic straightforward.
Approach 2: Using an Array for Counting (O(n * d) time, O(1) space)
Instead of a hash table, use a fixed-size array where the index represents the digit sum. For typical constraints, the maximum digit sum for numbers up to 104 is small (for example, 9999 → 36). That means you can allocate an array of size ~40 and use it as a counting bucket. For each number from 1 to n, compute its digit sum and increment count[sum]. After processing all numbers, iterate over the array to determine the largest frequency and count how many sums achieve it.
This version replaces hash lookups with direct indexing, which reduces overhead and keeps memory usage constant. The logic relies on simple math operations for digit extraction and works efficiently even for the upper bound of n.
Recommended for interviews: The counting-array approach is usually the best answer. It shows that you recognized the limited range of digit sums and optimized the data structure choice. Starting with the hash table version demonstrates clear thinking about grouping, while the array optimization shows deeper understanding of constraints and constant-space techniques.
Approach 1: Grouping by Digit Sum
This 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.
def countLargestGroup(n):
def digit_sum(num):
return sum(int(d) for d in str(num))
groups = {}
for i in range(1, n + 1):
s = digit_sum(i)
if s in groups:
groups[s] += 1
else:
groups[s] = 1
max_size = max(groups.values())
return sum(1 for size in groups.values() if size == max_size)
# Example usage:
n = 13
print(countLargestGroup(n))
import java.util.HashMap;
import java.util.Map;
public class CountLargestGroup {
private static int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
public static int countLargestGroup(int n) {
Map<Integer, Integer> count = new HashMap<>();
for (int i = 1; i <= n; ++i) {
int sum = digitSum(i);
count.put(sum, count.getOrDefault(sum, 0) + 1);
}
int maxCount = 0;
int numGroups = 0;
for (int value : count.values()) {
if (value > maxCount) {
maxCount = value;
numGroups = 1;
} else if (value == maxCount) {
numGroups++;
}
}
return numGroups;
}
public static void main(String[] args) {
int n = 13;
System.out.println(countLargestGroup(n));
}
}#include <iostream>
#include <unordered_map>
using namespace std;
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int countLargestGroup(int n) {
unordered_map<int, int> count;
for (int i = 1; i <= n; ++i) {
int sum = digitSum(i);
count[sum]++;
}
int maxCount = 0, numGroups = 0;
for (const auto &pair : count) {
if (pair.second > maxCount) {
maxCount = pair.second;
numGroups = 1;
} else if (pair.second == maxCount) {
numGroups++;
}
}
return numGroups;
}
int main() {
int n = 13;
cout << countLargestGroup(n) << endl;
return 0;
}function countLargestGroup(n) {
const digitSum = (num) => num.toString().split('').reduce((sum, d) => sum + parseInt(d, 10), 0);
const groups = {};
for (let i = 1; i <= n; i++) {
const sum = digitSum(i);
if (groups[sum]) {
groups[sum]++;
} else {
groups[sum] = 1;
}
}
const groupSizes = Object.values(groups);
const maxSize = Math.max(...groupSizes);
return groupSizes.filter(size => size === maxSize).length;
}
// Example usage:
const n = 13;
console.log(countLargestGroup(n));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int countLargestGroup(int n) {
int count[46] = {0};
for (int i = 1; i <= n; ++i) {
int sum = digitSum(i);
count[sum]++;
}
int maxCount = 0, numGroups = 0;
for (int i = 0; i < 46; ++i) {
if (count[i] > maxCount) {
maxCount = count[i];
numGroups = 1;
} else if (count[i] == maxCount) {
numGroups++;
}
}
return numGroups;
}
int main() {
int n = 13;
printf("%d\n", countLargestGroup(n));
return 0;
}using System;
using System.Collections.Generic;
class CountLargestGroupSolution {
private static int DigitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
public static int CountLargestGroup(int n) {
Dictionary<int, int> count = new Dictionary<int, int>();
for (int i = 1; i <= n; ++i) {
int sum = DigitSum(i);
if (count.ContainsKey(sum)) {
count[sum]++;
} else {
count[sum] = 1;
}
}
int maxCount = 0, numGroups = 0;
foreach (int value in count.Values) {
if (value > maxCount) {
maxCount = value;
numGroups = 1;
} else if (value == maxCount) {
numGroups++;
}
}
return numGroups;
}
static void Main() {
int n = 13;
Console.WriteLine(CountLargestGroup(n));
}
}This Python solution utilizes a dictionary to track the size of groups, and a helper function digit_sum to compute digit sums. Post-calculation, we identify the largest group size and count occurrences.
Time Complexity: O(n), iterating over each number once and performing simple operations.
Space Complexity: O(k), with k being the range of possible digit sums, generally small (around 36).
Approach 2: Using an Array for Counting
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.
def countLargestGroup(n):
def digit_sum(num):
return sum(int(d) for d in str(num))
count = [0] * 46
for i in range(1, n + 1):
count[digit_sum(i)] += 1
max_count = max(count)
return count.count(max_count)
# Example usage:
n = 13
print(countLargestGroup(n))public class CountLargestGroupArray {
private static int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
public static int countLargestGroup(int n) {
int[] count = new int[46];
for (int i = 1; i <= n; ++i) {
int sum = digitSum(i);
count[sum]++;
}
int maxCount = 0, numGroups = 0;
for (int c : count) {
if (c > maxCount) {
maxCount = c;
numGroups = 1;
} else if (c == maxCount) {
numGroups++;
}
}
return numGroups;
}
public static void main(String[] args) {
int n = 13;
System.out.println(countLargestGroup(n));
}
}#include <iostream>
#include <vector>
using namespace std;
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int countLargestGroup(int n) {
vector<int> count(46, 0);
for (int i = 1; i <= n; ++i) {
int sum = digitSum(i);
count[sum]++;
}
int maxCount = 0, numGroups = 0;
for (const int &c : count) {
if (c > maxCount) {
maxCount = c;
numGroups = 1;
} else if (c == maxCount) {
numGroups++;
}
}
return numGroups;
}
int main() {
int n = 13;
cout << countLargestGroup(n) << endl;
return 0;
}function countLargestGroup(n) {
const digitSum = (num) => {
let sum = 0;
while (num > 0) {
sum += num % 10;
num = Math.floor(num / 10);
}
return sum;
};
const count = new Array(46).fill(0);
for (let i = 1; i <= n; i++) {
count[digitSum(i)]++;
}
const maxSize = Math.max(...count);
return count.filter(size => size === maxSize).length;
}
// Example usage:
const n = 13;
console.log(countLargestGroup(n));#include <stdio.h>
#include <string.h>
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int countLargestGroup(int n) {
int count[46] = {0};
for (int i = 1; i <= n; ++i) {
int sum = digitSum(i);
count[sum]++;
}
int maxCount = 0, numGroups = 0;
for (int i = 0; i < 46; ++i) {
if (count[i] > maxCount) {
maxCount = count[i];
numGroups = 1;
} else if (count[i] == maxCount) {
numGroups++;
}
}
return numGroups;
}
int main() {
int n = 13;
printf("%d\n", countLargestGroup(n));
return 0;
}using System;
class CountLargestGroupArraySolution {
private static int DigitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
public static int CountLargestGroup(int n) {
int[] count = new int[46];
for (int i = 1; i <= n; ++i) {
int sum = DigitSum(i);
count[sum]++;
}
int maxCount = 0, numGroups = 0;
foreach (int c in count) {
if (c > maxCount) {
maxCount = c;
numGroups = 1;
} else if (c == maxCount) {
numGroups++;
}
}
return numGroups;
}
static void Main() {
int n = 13;
Console.WriteLine(CountLargestGroup(n));
}
}The Python implementation uses a list initialized to 46 elements to streamline the counting of numbers within the ranges defined by their digit sums, resulting in an efficient storage and lookup mechanism.
Time Complexity: O(n).
Space Complexity: O(1) utilizing a fixed length array.
Approach 3: Hash Table or Array
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.
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;
}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
}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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Grouping by Digit Sum | Time Complexity: O(n), iterating over each number once and performing simple operations. |
| Using an Array for Counting | Time Complexity: O(n). |
| Hash Table or Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Table Grouping by Digit Sum | O(n * d) | O(k) | General solution when digit-sum range is unknown or when using hash maps is more intuitive |
| Array Counting by Digit Sum | O(n * d) | O(1) | Best when the digit-sum range is small and predictable |
Frequently asked questions
Is Count Largest Group easy or hard?
Count Largest Group is classified as an Easy problem. It mainly tests basic iteration, digit extraction, and frequency counting rather than advanced algorithms.
Count Largest Group Python/Java solution
The typical implementation iterates from 1 to n, computes the digit sum using modulo and division, and updates a counter array or hash map. Python often uses a list or defaultdict, while Java commonly uses an int array or HashMap.
How to solve Count Largest Group in O(n)?
Iterate from 1 to n, compute the digit sum of each number, and increment a counter for that sum. Store counts in a small array indexed by the digit sum. After processing all numbers, scan the array to find the maximum frequency and count how many groups reach it.
What is the best approach for Count Largest Group?
The most efficient approach groups numbers by their digit sum and counts frequencies using a fixed array. Since the digit sum range is small, direct indexing avoids hash map overhead. This gives O(n * d) time, where d is the number of digits, and O(1) extra space.
Is Count Largest Group asked at Google/Amazon/Meta?
Problems involving digit manipulation, grouping, and frequency counting appear frequently in interviews at companies like Amazon and Google. While this exact problem may not always appear, the pattern of grouping elements using a computed key is common.
What data structure is used in Count Largest Group?
The core data structure is a frequency counter indexed by digit sum. This can be implemented with a hash table for flexibility or a fixed-size array for better performance when the range of sums is known.
What is the time complexity of Count Largest Group?
The time complexity is O(n * d) because each number from 1 to n is processed once and computing the digit sum takes d operations. For typical constraints where numbers have at most 4–5 digits, this behaves like O(n).