Maximum Number of Balls in a Box

🏠 ⬅️ ➡️

You are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive (i.e., n == highLimit - lowLimit + 1), and an infinite number of boxes numbered from 1 to infinity.

Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball's number. For example, the ball number 321 will be put in the box number 3 + 2 + 1 = 6 and the ball number 10 will be put in the box number 1 + 0 = 1.

Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.

Example 1:

Input: lowLimit = 1, highLimit = 10 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 ... Ball Count: 2 1 1 1 1 1 1 1 1 0 0 ... Box 1 has the most number of balls with 2 balls.

Example 2:

Input: lowLimit = 5, highLimit = 15 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 ... Ball Count: 1 1 1 1 2 2 1 1 1 0 0 ... Boxes 5 and 6 have the most number of balls with 2 balls in each.

Example 3:

Input: lowLimit = 19, highLimit = 28 Output: 2 Explanation: Box Number: 1 2 3 4 5 6 7 8 9 10 11 12 ... Ball Count: 0 1 1 1 1 1 1 1 1 2 0 0 ... Box 10 has the most number of balls with 2 balls.

Constraints:

  • 1 <= lowLimit <= highLimit <= 105
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: n, lowLimit, highLimit, i, j, k, maxCount, count

    ! read input
    read(*,*) n
    read(*,*) lowLimit
    read(*,*) highLimit

    ! initialize variables
    maxCount = 0

    ! loop over all possible box numbers
    do i = 1, infinity
        ! reset count for current box
        count = 0

        ! loop over all balls
        do j = lowLimit, highLimit
            ! check if ball belongs to current box
            if (sumDigits(j) == i) then
                ! increment count for current box
                count = count + 1
            end if
        end do

        ! check if current box has more balls than previous one
        if (count > maxCount) then
            maxCount = count
        end if
    end do

    ! print result
    write (*,*) maxCount

contains

    function sumDigits(n) result(sum)
        implicit none
        integer, intent(in) :: n
        integer :: sum
        integer :: digit

        sum = 0
        do while (n /= 0)
            digit = mod(n, 10)
            sum = sum + digit
            n = n / 10
        end do
    end function sumDigits

end program main
❌ Compiled
❌ Executed
❌ Correct 
! This is a Fortran code to solve the problem

program ball_factory
    implicit none
    integer :: lowLimit, highLimit, n, i, j, k, max_balls, box_count
    integer, dimension(:), allocatable :: balls

    ! Read the input
    read(*,*) lowLimit
    read(*,*) highLimit

    ! Calculate the number of balls
    n = highLimit - lowLimit + 1

    ! Allocate memory for the balls
    allocate(balls(n))

    ! Initialize the balls
    do i = 1, n
        balls(i) = i
    end do

    ! Sort the balls based on the sum of digits
    call sort(balls, n)

    ! Initialize the box count
    box_count = 0

    ! Loop through the balls and count the number of balls in each box
    do i = 1, n
        k = 0
        do j = 1, n
            if (balls(j) == i) then
                k = k + 1
            end if
        end do
        if (k > box_count) then
            box_count = k
        end if
    end do

    ! Print the result
    write(*,*) box_count

    ! Deallocate the memory
    deallocate(balls)
end program ball_factory

! This is a subroutine to sort the balls based on the sum of digits
subroutine sort(balls, n)
    implicit none
    integer, dimension(n), intent(inout) :: balls
    integer, intent(in) :: n
    integer :: i, j, temp

    ! Bubble sort algorithm
    do i = 1, n - 1
        do j = 1, n - i
            if (sum_digits(balls(j)) > sum_digits(balls(j + 1))) then
                temp = balls(j)
                balls(j) = balls(j + 1)
                balls(j + 1) = temp
            end if
        end do
    end do

contains

    ! This is a function to calculate the sum of digits of a number
    function sum_digits(n) result(sum)
        implicit none
        integer, intent(in) :: n
        integer :: sum, digit

        sum = 0
        do while (n > 0)
            digit = mod(n, 10)
            sum = sum + digit
            n = n / 10
        end do
    end function sum_digits
end subroutine sort
🌐 Data from online sources 
def maxWidthOfVerticalArea(points):
    xs = sorted([point[0] for point in points])
    max_width = 0
    for i in range(1, len(xs)):
        max_width = max(max_width, xs[i] - xs[i - 1])
    return max_width

1. Obtain all the x-coordinates from the given points, and store them in a new list (`xs`).
  1. Sort the x-coordinates in ascending order.
  2. Initialize the maximum width (max_width) to be 0.
  3. Iterate through the sorted x coordinates:
  4. For each consecutive pair of x-coordinates, calculate their difference.
  5. Update the max_width with the maximum value between the current max_width and the difference.
  6. Return the max_width.
🌐 Data from online sources 
#include <vector>
#include <algorithm>

int maxWidthOfVerticalArea(std::vector<std::vector<int>>& points) {
    std::vector<int> xs;
    for (const auto& point : points) {
        xs.push_back(point[0]);
    }
    std::sort(xs.begin(), xs.end());

    int max_width = 0;
    for (size_t i = 1; i < xs.size(); ++i) {
        max_width = std::max(max_width, xs[i] - xs[i - 1]);
    }

    return max_width;
}

1. Obtain all the x-coordinates from the given points, and store them in a new list (`xs`).
  1. Sort the x-coordinates in ascending order.
  2. Initialize the maximum width (max_width) to be 0.
  3. Iterate through the sorted x coordinates:
  4. For each consecutive pair of x-coordinates, calculate their difference.
  5. Update the max_width with the maximum value between the current max_width and the difference.
  6. Return the max_width.