Count Distinct Numbers on Board

🏠 ⬅️ ➡️

You are given a positive integer n, that is initially placed on a board. Every day, for 109 days, you perform the following procedure:

  • For each number x present on the board, find all numbers 1 <= i <= n such that x % i == 1.
  • Then, place those numbers on the board.

Return the number of distinct integers present on the board after 109 days have elapsed.

Note:

  • Once a number is placed on the board, it will remain on it until the end.
  • % stands for the modulo operation. For example, 14 % 3 is 2.

Example 1:

Input: n = 5 Output: 4 Explanation: Initially, 5 is present on the board. The next day, 2 and 4 will be added since 5 % 2 == 1 and 5 % 4 == 1. After that day, 3 will be added to the board because 4 % 3 == 1. At the end of a billion days, the distinct numbers on the board will be 2, 3, 4, and 5.

Example 2:

Input: n = 3 Output: 2 Explanation: Since 3 % 2 == 1, 2 will be added to the board. After a billion days, the only two distinct numbers on the board are 2 and 3.

Constraints:

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

    integer :: n, x, i, num_distinct

    ! read input
    read(*,*) n

    ! initialize board
    call init_board(n)

    ! perform procedure every day
    do i = 1, 109
        call perform_procedure()
    end do

    ! count distinct numbers on board
    num_distinct = count_distinct()

    ! print result
    write(*,'(I0)') num_distinct

contains

    subroutine init_board(n)
        implicit none
        integer, intent(in) :: n
        integer :: x

        do x = 1, n
            if (mod(x, n) == 0) then
                call add_to_board(x)
            end if
        end do
    end subroutine init_board

    subroutine perform_procedure()
        implicit none
        integer :: x, i

        do x = 1, size(board)
            do i = 1, n
                if (mod(x, i) == 1) then
                    call add_to_board(i)
                end if
            end do
        end do
    end subroutine perform_procedure

    function count_distinct() result(num_distinct)
        implicit none
        integer :: num_distinct

        num_distinct = size(unique(board))
    end function count_distinct

    subroutine add_to_board(x)
        implicit none
        integer, intent(in) :: x

        if (.not. any(board == x)) then
            board = [board, x]
        end if
    end subroutine add_to_board

end program main
✅ Compiled
✅ Executed
❌ Correct 
module mod_problem_109

implicit none

contains

integer function solve(n) result(res)

integer, intent(in) :: n

integer :: i, j, x, y, z, count

! Initialize the board with the given number
res = 1

! Perform the procedure for 109 days
do i = 2, 109

    ! Find all numbers x such that x % i == 1
    count = 0
    do j = 1, n
        x = j
        y = i
        z = x / y
        if (z == 1) then
            count = count + 1
        end if
    end do

    ! Place the found numbers on the board
    res = res + count

end do

end function solve

end module mod_problem_109

program test

use mod_problem_109

implicit none

integer :: n, res

! Test case 1
n = 5
res = solve(n)
print *, "Test case 1: ", res

! Test case 2
n = 3
res = solve(n)
print *, "Test case 2: ", res

end program test
🌐 Data from online sources 
def distinct_numbers(n):
    return n - 1

For a given `n`, we only calculate the count of distinct integers that can be added to the board because of `n`.

It can be observed that only the numbers in the range [2, n] will satisfy the condition x % i == 1, where x = n. It is because when i is 1, we have n % 1 == 0. So, the numbers [2, n-1], inclusive, will be added to the board, making the count of distinct integers on the board equal to n - 1.

Since we are only concerned about the count of distinct integers and not the actual integers on the board, this algorithm works regardless of the value of 10^9 days.

🌐 Data from online sources 
int distinctNumbers(int n) {
    return n - 1;
}

For a given `n`, we only calculate the count of distinct integers that can be added to the board because of `n`.

It can be observed that only the numbers in the range [2, n] will satisfy the condition x % i == 1, where x = n. It is because when i is 1, we have n % 1 == 0. So, the numbers [2, n-1], inclusive, will be added to the board, making the count of distinct integers on the board equal to n - 1.

Since we are only concerned about the count of distinct integers and not the actual integers on the board, this algorithm works regardless of the value of 10^9 days.