Count Largest Group

• Initialize a frequency map (or an array since digit sums are small) to store the size of each group. For instance, an integer array counts of size 37 (for sums 1 to 36) initialized to zeros.
• Loop through each number i from 1 to n.
• For each number i, create a helper function getDigitSum(i) that calculates the sum of its digits. This function works by repeatedly taking the number modulo 10 to get the last digit and dividing the number by 10 to remove the last digit, until the number becomes 0.
• Use the returned digit sum as an index into the counts array and increment the value: counts[digitSum]++.
• After iterating through all numbers, scan the counts array to find the maximum group size, maxSize.
• Scan the counts array again to count how many groups have a size equal to maxSize.
• Return this final count.

The core of this method is a loop that runs from 1 to n. Inside this loop, we compute the sum of digits for the current number. A helper function, say getDigitSum(num), can be implemented for this. This function would initialize a sum variable to zero, and then in a while loop, it would continuously add num % 10 to the sum and update num to num / 10 until num becomes zero. The maximum possible sum of digits for a number up to 10^4 is for 9999, which is 36. Therefore, an array of size 37 is sufficient to act as a frequency map, where the index represents the digit sum and the value at that index represents the size of the group.

After calculating the digit sum for a number i, we increment the count at the corresponding index in our frequency array. While doing this, we can also keep track of the maximum frequency seen so far. After the main loop finishes, we iterate through the frequency array one more time to count how many entries match the maximum frequency found. This count is the result.

1class Solution {2    private int getDigitSum(int num) {3        int sum = 0;4        while (num > 0) {5            sum += num % 10;6            num /= 10;7        }8        return sum;9    }10 11    public int countLargestGroup(int n) {12        // Max sum for n=10000 is for 9999 -> 36. Array size 37 is safe.13        int[] counts = new int[37];14        int maxSize = 0;15 16        for (int i = 1; i <= n; i++) {17            int sum = getDigitSum(i);18            counts[sum]++;19            if (counts[sum] > maxSize) {20                maxSize = counts[sum];21            }22        }23 24        int result = 0;25        for (int count : counts) {26            if (count == maxSize) {27                result++;28            }29        }30        return result;31    }32}

• Initialize an integer array digitSum of size n + 1 to store the sum of digits for each number from 0 to n.
• Initialize an integer array counts of size 37 to store the frequency of each digit sum.
• Initialize a variable maxSize = 0 to keep track of the largest group size.
• Loop through each integer i from 1 to n.
• Inside the loop, calculate digitSum[i] using the dynamic programming relation: digitSum[i] = digitSum[i / 10] + (i % 10).
• Increment the count for this sum in the counts array: counts[digitSum[i]]++.
• Update maxSize = Math.max(maxSize, counts[digitSum[i]]).
• After the loop, initialize result = 0.
• Iterate through the counts array. If a count is equal to maxSize, increment result.
• Return result.

We can define dp[i] as the sum of digits of number i. There's a simple recurrence relation: dp[i] = dp[i / 10] + (i % 10). For example, the sum of digits for 123 is (sum of digits for 12) + 3. We can use an array, let's call it digitSum, of size n + 1 to store these values.

We iterate from i = 1 to n. In each step, we compute digitSum[i] using our recurrence. Since i / 10 is always less than i, digitSum[i / 10] will have already been computed. Once we have the digit sum for i, we use it to update our group size frequency array, counts. We also track the maximum group size (maxSize) as we populate the counts array.

After the loop finishes, we have the final maxSize. A simple iteration over the counts array will give us the number of groups that have this size. This approach trades O(n) space to reduce the time complexity from O(n log n) to O(n).

1class Solution {2    public int countLargestGroup(int n) {3        // Max sum for n=10000 is for 9999 -> 36.4        int[] counts = new int[37];5        int[] digitSum = new int[n + 1];6        int maxSize = 0;7        8        for (int i = 1; i <= n; i++) {9            // DP relation: sum(i) = sum(i/10) + i%1010            digitSum[i] = digitSum[i / 10] + (i % 10);11            counts[digitSum[i]]++;12            maxSize = Math.max(maxSize, counts[digitSum[i]]);13        }14 15        int result = 0;16        for (int count : counts) {17            if (count == maxSize) {18                result++;19            }20        }21        return result;22    }23}