Finding the number of even perfect square proper divisors of a given number N

Question

I tried to solve a question on HackerRank (Problem Link: https://www.hackerrank.com/challenges/mehta-and-his-laziness/problem) which involves calculating the number of even perfect square proper divisors of a given number N. The problem requires the program to calculate the probability of a divisor of a given number N being even perfect square among all of N's proper divisors.

For example, given N = 36, the set of proper divisors is {1,2,3,4,6,9,12,18}, and only 4 is an even perfect square. The probability will be 1/8.

Another example will be N = 900, there will be a total of 26 proper divisors and 3 of them {4,36,100} are even perfect square. The probability will be 3/26.

These 2 examples are taken from the problem description on HackerRank. I solved this problem and passed all tests but my solution is not optimal. So I read the "Smarter Strategy" mentioned in the editorial provided by HackerRank. I understood the theoretical explanation but I got really confused by the line

divisors[j] += divisors[j] / e

I don't know whether it is appropriate to copy and paste the explanation and full code here from the editorial on HackerRank (https://www.hackerrank.com/challenges/mehta-and-his-laziness/editorial) since it requires the user to log in first (can use Gmail, Facebook, GitHub and LinkedIn accounts) and unlock (no need to pay, it is free), so I just pasted the line that I got really confused. I hope someone can also access the editorial and answer my following questions.

I understand the explanations and codes of other solutions, but I just don't get why the update of the divisors list should be done in this way for this optimal method. divisors[j] is the value from the last cycle of the loop, how can this be used to calculate the divisors produced by the current prime number and specific exponent? I think that it /e instead of /(e+1) is because of the initialization of all 1s in the list (already counted the 1 being divisors of every number). Also, I think this method of update is related to avoid double-counting, but I really don't understand how this formula was derived?

For example, 36 = 2^2 * 3^2.

After loop 2^1, divisors[36] should be 2. Then after loop 2^2, divisors[36] should be 3 (2/2+2). After loop 3^1, divisors[36] should be 6 (3/1+3). And then after 3^2, divisors[36] should be 9 (6/2+6).

My guess is that after each loop the divisors is adding the possibilities of divisors caused by the current value, for example, in the 36 case:

val : divisors list
2^1 : {1,2}
2^2 : {1,2,4}
3^1 : {1,2,4,3,6,12}
3^2 : {1,2,4,3,6,12,9,18,36}

But I don't know how the formula was mathematically derived... Can anyone explain it to me? Thank you so much...

Answer 1

It is not clear about which formula you are talking about but if you are talking about how the list

  val : divisors list
  2^1 : {1,2}
  2^2 : {1,2,4}
  3^1 : {1,2,4,3,6,12}
  3^2 : {1,2,4,3,6,12,9,18,36}

was created then here is the answer your number is 36 = 2² * 3 ² and think you have a list A = {} which is empty initially and we will find all the divisors. At that point I think you know how the prime factorization was done. Now, from simple combinatorics you have three possible choice for 2 to include it in every divisors. Suppose you don't want to calculate the divisors that contains any number of 2 means you want 2⁰=1 in

So, if you choose 2⁰ and any number of 3 then you have the possible choice 2⁰ * 3⁰, 2⁰ * 3¹, 2⁰ * 3² So, for 2⁰ and any number of 3: list contains: 2⁰ * 3⁰ = 1, 2⁰ * 3¹ = 3, 2⁰ * 3² = 9

So, A = {1, 3, 9}

Then you choose exactly 2 once and any number of 3 then you have the possible choice 2¹ * 3⁰, 2¹ * 3¹, 2¹ * 3²

for 2¹ and any number of 3:list contains: 2¹ * 3⁰ = 2, 2¹ * 3¹ = 6,2¹ * 3² = 18

So, A = {1, 3, 9} U {2, 6, 18} = {1, 2, 3, 6, 9, 18} and continue for when 2 occurs twice. then you have all the divisors in the list.

This can be easily implemented using sieve.