ICM0013 (Lucky Boundaries) - Editorial

PROBLEM LINK:

Div-1 Contest

Div-2 Contest

Div-3 Contest

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        
    
1 Like