### 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 given number is divisible by n or not. If the number is divisible by n, increase odd or even(divisor) counter accordingly.

Here it can also be improved by checking only till th**e square root** of n, because we can find another divisor by dividing n with the number smaller than the square root of n.

### 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=p_{1}^{a1}p_{2}^{a2}p_{3}^{a3}……p_{k}^{ak}

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:-

p_{1}^{b1}p_{2}^{b2}p_{3}^{b3}….p_{k}^{bk} 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; }

## 0 Comments