Count of Distinct Integers

Revision en2, by yashsaha555, 2022-12-09 13:33:20

Given a board with an integer 'n' written on it, select an integer 'x' from the board. For each, 'i' from 1 to 'x', if the remainder when 'x' is divided by 'i' is 1, add the integer (x-i) to the board. Find out the maximum number of distinct integers that can be present on the board.

Example- n = 4

Initially, only the given number 4 is on the board. There is one value that leaves a remainder of 1: 4%3=1. Add the value 4-3=1 to the board, so it now contains [1,4]. There is no longer 'i' such that 1%i=1. There are 2 distinct integers on the board, so return 2.

Constraints- 1<=n<=1000

If someone could explain the approach then it would be very helpful. Thanks.

Tags math, recursion, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English yashsaha555 2022-12-09 13:33:20 80
en1 English yashsaha555 2022-12-09 13:32:42 625 Initial revision (published)