# Hackerrank Solution: Sherlock and Divisors

Original Problem

Watson gives an integer $$N$$ to Sherlock and asks him: What is the number of divisors of $$N$$ that are divisible by 2?

## Input Format

First line contains $$T$$, the number of testcases. This is followed by $$T$$ lines each containing an integer $$N$$.

## Output Format

For each testcase, print the required answer in one line.

## Constraints

• $$1\leq T\leq 100$$
• $$1\leq N\leq 10^9$$

## Solution

When writing a number $$N$$ as the product of its prime factors, we have $$N = p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}\dots$$. From which the number of divisors follows as $$d(N) = (e_1+1)(e_2+1)(e_3+1)\dots$$

From the general case we have to count only the numbers that are divisible by 2. We have two cases for $$p_k=2$$:

1) if $$e_k=0$$ then the result must be zero, as no factor of 2 is present

2) if $$e_k\neq 0$$ then we know that at least one factor of 2 is present. Since we want to know the number of divisors of $$N$$ that are divisible by 2, we factor out 2 to say $$N=2M$$. Calculating the number of divisors $$d(M)$$ is then just $$d(M)=e_k (e_1+1)(e_2+1)\dots$$

Since $$p_i\equiv1\pmod{2}$$ for all $$p_i\neq 2$$, we can use this to avoid branching completely like so, using Rubys prime factorization library:

def divisors(n)
Prime.prime_division(n).inject(1) {|s, k|
s * (k[1] + k[0] % 2) * (1 - k[0] % 2)
}
end

« Back to problem overview