yashsaha555's blog

By yashsaha555, history, 7 weeks 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

»
7 weeks 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).

»
7 weeks 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
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Thanks a lot for the explanation and the code.

  • »
    »
    7 weeks 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(){
         
             ios_base::sync_with_stdio(false);
             cin.tie(NULL);
             cout.tie(NULL);
         
             factFind();
         
             int t=1;
           //  cin>>t;
             
             while(t--){
              
                ll n;
                cin>>n;
                
                set<ll>S;
                
                S.insert(n);
                
                ll ans = 0LL;
                
                while(S.size()){
                    
                    ll x = *S.rbegin();
                    S.erase(x);
                    ans++;
                    
                    // 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;){
                        if((x%i)==1){
                            S.insert(x-i);
                        }
                        ll curr = (i+1)/2;
                        i = curr;
                    }
                    
                }
                
                cout<<ans<<"\n";
                
             }
          
        return 0;
        
    }