yashsaha555's blog

Count of Distinct Integers
By yashsaha555, history, 2 years 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

Comments Comments (2)
| Write comment?
»
2 years 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
→ Reply
  • »
    »
    2 years 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;
    
}
    → Reply