3 min read

Problem Statement:-

Your task is simple.Given a number(say,n) find if it’s number of odd divisors are equal to it’s number of even divisors.

For Example:-Let’s say the number is 6.

The divisors of 6 are:-1,2,3 and 6.

Here number of odd divisors=2(1 and 3) and number of even divisors=(2 and 6).

As the no. of even divisors and no. of odd divisors are equal the output would be ‘YES’(without quotes) otherwise it would be ‘NO’.

NAIVE APPROACH:-

One of the simplest approach would be to go from 1 to the number n and check if the number is divisible or not.If the number is divisor of n increase and odd or even(divisor) counter accordingly.

Here it can also be improved to check only till square root of n,because we can found other divisor by dividing n with the number.

Implementation in C++

#include<iostream>
using namespace std;
int main(){
    int n,even_divisor=0,odd_divisor=0,d;
    cin>>n;//Taking input from the user
    int i=1;
    while(i*i<=n){
        if(n%i==0){
            if(i%2==0){
                even_divisor++;
            }
            else{
                odd_divisor++;
            }
            d=n/i;//Here d is the other divisor of n which is greater than sqrt(n)
            if(d%2==0){
                even_divisor++;
            }
            else{
                odd_divisor++;
            }
        }
        i++;
    }
    if(even_divisor==odd_divisor){
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n";
    }
return 0;
}

Efficient Approach

The complexity of above solution was O(sqrt(n)).But the problem can be solved efficiently in O(1) complexity also.

For this we have to use some laws of mathematics and combinators.
According to Unique Factorisation Theorem any no. can be express in terms of product of power of primes and regardless of the order,this would be unique.

So,we can express n as:-

n=p1a1p2a2p3a3……pkak
where, each pi(1<=i<=k) is a prime and each ai is a positive integer.

Now,Using law of combinators any divisor of n would be of the form:-
p1b1p2b2p3b3….pkbk where bi is an integer and 0<=bi<=ai for 1<=i<=k.

Now a divisor would be odd if it does not contain power of prime 2.So, if p1=2 then b1=0.It can be done in only 1 way.

For even divisors b1 can be replaced by 1 (or) 2 (or)….a1 to get a divisor.It can be done in b1 ways.

Now for others each bi can be replaced either with 0(or) 1 (or) 2…(or)ai for 1<=i<=k.It can be done be done in (ai+1) ways.

By Fundamental principle:-
Number of odd divisors are 1*(a2+1)(a3+1)….(ak+1).
Similarly,Number of even divisors are a1*(a2+1)(a3+1)….(ak+1).

For no. of even divisors to be equal to no. of odd divisors:-

1*(a2+1)(a3+1)….(ak+1) and a1*(a2+1)(a3+1)….(ak+1) are equal.
This is possible only when a1=1.

So,from above discussion we can conclude that:-
No. of even and odd divisors of a number are equal if it has 1(and only 1 )power of 2.

Implementation:-

#include <iostream>
using namespace std;
int main(){
    cin>>n;
    if((n%2==0) && (n%4!=0)){
    //A no. has power of 2 as 1 if it is only divisible by 2 and not with its power.
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n";
    }
    return 0;
}

Kapil Bansal

A student of B.Tech CSE working on competitive programming, a cybersecurity devotee working towards strengthing the concepts. I am also working on Python modules, Data Structures and Algorithms etc.

0 Comments

Leave a Reply