PROBLEM LINK:
Author: anshugarg12 and dyrroth
Tester: catastrophic25 and dyrroth
Editorialist: dyrroth
DIFFICULTY:
CAKEWALK
PREREQUISITES:
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