yashsaha555's blog

By yashsaha555, history, 2 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by yashsaha555 (previous revision, new revision, compare).

2 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

Every number added to the board by some $$$X$$$ will be smaller than $$$X$$$.

So if we consider the board is a set and while the board is not empty we can consider the largest number in the board is the current $$$X$$$ and we will iterate from $$$1$$$ to $$$X-1$$$ and add all numbers which have modulo $$$1$$$ to the set, then erase the current $$$X$$$ from the board.

The code
  • »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Thanks a lot for the explanation and the code.

  • »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Just thought of a little bit modification of your code , please check these out whether you can find out some failing test cases or not .

    int main(){
             int t=1;
           //  cin>>t;
                ll n;
                ll ans = 0LL;
                    ll x = *S.rbegin();
                    // X = 25 , the largest i , for which X%i = 1 , i = X - 1
                    // Then we will iterate through i , (i+1)/2 , ..... , so on
                    // Just checking those i values , who has the possibility X%i = 1
                    // Add the corresponding (X-i) inside the set
                    for(ll i=x-1;i>=2;){
                        ll curr = (i+1)/2;
                        i = curr;
        return 0;