 # PROBLEM LINK:

Div-1 Contest

Div-2 Contest

Div-3 Contest

Author: anshugarg12 and dyrroth

Tester: catastrophic25 and dyrroth

Editorialist: dyrroth

CAKEWALK

None

# PROBLEM:

You are given a positive integer N and you need to find the number of positive integers M such that N mod M ≤ N/2.

# EXPLANATION:

• 1 ≤ M ≤ N/2 :
We know that a mod b is always less than b. Therefore for 1≤M≤N/2, N mod M is always less than N/2.

• N/2<M ≤ N :
Now for N/2<M≤ N, we can say M=N-k for some 0≤k<N/2 .Therefore N mod M = N mod (N-k) = k, which is less than N/2

• M>N :
N mod (N+k) = N, for all k>0. Hence for M>N, N mod M is always greater than N/2.

Therefore, we can say that N mod M≤N/2 for all M = {1,2,3,…, N}.

# TIME COMPLEXITY:

The time complexity is O(1) per test case.

The memory complexity is O(1) per test case.

# SOLUTIONS:

Editorialist's Solution
``````
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
int T=1;
cin>>T;
while(T--){
ll n;
cin>>n;
cout<<n<<"\n";
}
return 0;
}
/*_*/
``````
Tester's Solution
``````
T = int(input())
while T:
n = int(input())
print(n)
T-=1
``````
1 Like