Count Largest Group

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: n

    call get_arguments(n)

    write (*, '(A, I0)') 'The number of groups with largest size is ', solve(n)

contains

    subroutine get_arguments(n)
        implicit none
        integer, intent(out) :: n

        if (command_argument_count() /= 1) then
            write (*, '(A)') 'ERROR: Expected one argument'
            stop 1
        end if

        call get_command_argument(1, buffer)
        read (buffer, '(I0)', iostat=iostat) n
        if (iostat /= 0) then
            write (*, '(A)') 'ERROR: Invalid argument'
            stop 1
        end if
    end subroutine get_arguments

    function solve(n) result(groups)
        implicit none
        integer, value :: n
        integer :: groups

        integer :: i, j, k, l, m, n_digits, digit_sums(n), max_digit_sum, &
                   group_size(n), group_index(n)

        do i = 1, n
            digit_sums(i) = 0
            do j = 1, n_digits(i)
                digit_sums(i) = digit_sums(i) + mod(i, 10)
                i = i / 10
            end do
        end do

        max_digit_sum = 0
        do i = 1, n
            if (digit_sums(i) > max_digit_sum) then
                max_digit_sum = digit_sums(i)
            end if
        end do

        groups = 0
        do i = 1, n
            if (digit_sums(i) == max_digit_sum) then
                groups = groups + 1
            end if
        end do

    contains

        function n_digits(x) result(nd)
            implicit none
            integer, value :: x
            integer :: nd

            nd = 0
            do while (x > 0)
                nd = nd + 1
                x = x / 10
            end do
        end function n_digits

    end function solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module e99_largest_group_size

implicit none

contains

integer function largest_group_size(n) result(largest_size)

integer, intent(in) :: n

integer :: i, j, k, l, m, n_digits, digit_sum, max_digit_sum, &
max_digit_sum_index, group_size, largest_group_size

! Initialize variables
largest_size = 0
max_digit_sum = 0
max_digit_sum_index = 0

! Loop through all numbers from 1 to n
do i = 1, n

! Get the number of digits of the current number
n_digits = number_of_digits(i)

! Initialize the digit sum to 0
digit_sum = 0

! Loop through all digits of the current number
do j = 1, n_digits

! Get the current digit
k = digit(i, j)

! Add the current digit to the digit sum
digit_sum = digit_sum + k

end do

! If the digit sum is greater than the max digit sum, update the max digit sum and max digit sum index
if (digit_sum > max_digit_sum) then
max_digit_sum = digit_sum
max_digit_sum_index = i
end if

end do

! Get the group size for the max digit sum index
group_size = group_size(max_digit_sum_index)

! If the group size is greater than the largest group size, update the largest group size
if (group_size > largest_size) then
largest_size = group_size
end if

end function

! Return the number of digits of a given number
integer function number_of_digits(n) result(n_digits)

integer, intent(in) :: n

integer :: i, j

! Initialize the number of digits to 1
n_digits = 1

! Loop through all digits of the number
do i = 1, n

! If the current digit is not 0, increment the number of digits
if (digit(n, i) /= 0) then
n_digits = n_digits + 1
end if

end do

end function

! Return the digit of a given number at a given position
integer function digit(n, i) result(digit)

integer, intent(in) :: n, i

integer :: j, k

! Initialize the digit to 0
digit = 0

! Loop through all digits of the number
do j = 1, i

! If the current digit is not 0, increment the digit
if (digit(n, j) /= 0) then
digit = digit + 1
end if

end do

! Get the current digit
k = digit(n, i)

! If the current digit is not 0, add it to the digit
if (k /= 0) then
digit = digit + k
end if

end function

! Return the group size of a given number
integer function group_size(n) result(group_size)

integer, intent(in) :: n

integer :: i, j, k, l, m, n_digits, digit_sum, group_size

! Initialize the group size to 1
group_size = 1

! Loop through all numbers from 1 to n
do i = 1, n

! Get the number of digits of the current number
n_digits = number_of_digits(i)

! Initialize the digit sum to 0
digit_sum = 0

! Loop through all digits of the current number
do j = 1, n_digits

! Get the current digit
k = digit(i, j)

! Add the current digit to the digit sum
digit_sum = digit_sum + k

end do

! If the digit sum is equal to the current number, increment the group size
if (digit_sum == i) then
group_size = group_size + 1
end if

end do

end function

end module

program main

use e99_largest_group_size

implicit none

integer :: n, largest_group_size

! Read the value of n
read
🌐 Data from online sources 
def countLargestGroup(n: int) -> int:
    groups = [0] * 37
    largest_group_size = 0
    count_largest_groups = 0

    for i in range(1, n + 1):
        sum_of_digits = sum(map(int, str(i)))
        groups[sum_of_digits] += 1
        if groups[sum_of_digits] > largest_group_size:
            largest_group_size = groups[sum_of_digits]
            count_largest_groups = 1
        elif groups[sum_of_digits] == largest_group_size:
            count_largest_groups += 1

    return count_largest_groups

The algorithm iterates through every number from 1 to n. For each number, calculate the sum of its digits. Increment the count for the group corresponding to that sum of digits. Update the largest group size if the current group becomes larger than the previous largest group. If the current group size is equal to the largest group size, increment the count of largest groups.

The algorithm has a time complexity of O(n), as it processes each number from 1 to n once.

🌐 Data from online sources 
int countLargestGroup(int n) {
    std::vector<int> groups(37, 0);
    int largest_group_size = 0;
    int count_largest_groups = 0;

    for (int i = 1; i <= n; i++) {
        int sum = 0, num = i;
        while (num) {
            sum += num % 10;
            num /= 10;
        }
        groups[sum]++;
        if (groups[sum] > largest_group_size) {
            largest_group_size = groups[sum];
            count_largest_groups = 1;
        } else if (groups[sum] == largest_group_size) {
            count_largest_groups++;
        }
    }
    return count_largest_groups;
}

The algorithm iterates through every number from 1 to n. For each number, calculate the sum of its digits. Increment the count for the group corresponding to that sum of digits. Update the largest group size if the current group becomes larger than the previous largest group. If the current group size is equal to the largest group size, increment the count of largest groups.

The algorithm has a time complexity of O(n), as it processes each number from 1 to n once.