KS2 - Editorial

editorial
, ,
1

Problem Link - Guddu on a Date Practice Problem in 1400 to 1600 difficulty problems

Problem Statement:

Find the N-th smallest “round integer”. A round integer is defined as:

  • It is greater than 0.
  • The sum of its digits is a multiple of 10.

Approach:

Step 1: Sum of Digits Calculation

For any given number n, the first thing we need to do is calculate the sum of its digits. This can be done easily by repeatedly extracting the last digit and adding it to a sum.
We keep repeating this process until the number becomes zero.

Step 2: Check if Sum of Digits is Divisible by 10

After calculating the sum of the digits of n, we check if this sum is divisible by 10. If it is, then the number is already “round”, and we don’t need to modify it.

Step 3: Find the Next Round Integer

If the sum of the digits is not divisible by 10, we need to adjust the number to make the sum divisible by 10. To do this:

  • Calculate the remainder of the sum when divided by 10: sum % 10.
  • The next number will be formed by adding a digit to n such that the new sum of digits becomes divisible by 10. To achieve this, we append a digit d such that (sum + d) % 10 == 0. This can be done by computing d = (10 - (sum % 10)) % 10. This ensures that the sum of digits of n plus the digit d will be divisible by 10.

Step 4: Output the Result

We output the number formed by appending the digit d to the number n.

Complexity:

  • Time Complexity: The number of digits of n is O(log⁡ n), so calculating the sum of digits requires O(log ⁡n) time.
  • Space Complexity: O(1) No extra space is used.