### yashsaha555's blog

By yashsaha555, history, 2 months ago,

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.

• 0

 » 2 months ago, # |   -8 Auto comment: topic has been updated by yashsaha555 (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 3 →   -8 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$#include using namespace std;int main(){ int n; cin >> n; set st; int ans =0 ; st.insert(n) ; while(st.empty() == 0) { int x = *st.rbegin() ; st.erase(x) ; vector te ; for(int i= 1 ; i < x ;i++) if(x%i == 1) te.push_back(x-i) ; for(int ch : te) st.insert(ch) ; ans++; } cout << ans ; return 0;}$
•  » » 2 months ago, # ^ |   -8 Thanks a lot for the explanation and the code.
•  » » 2 months ago, # ^ |   -8 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; setS; 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<