A lot of people have participated and qualified in Qualification Round of Facebook Hacker Cup. Luckily I am also qualified for First Round. Facebook Hacker Cup Qualification Round consisted 3 problems. All of these problems were programmatically easy but tricky. Lots of people made very simple mistakes while solving these problem(including me).
First Problem of the round was:
A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 32+ 12. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 32 + 12 (we don’t count 12 + 32 as being different). On the other hand, 25 can be written as 52 + 02 or as 42 + 32.
You should first read an integer N, the number of test cases. The next N lines will contain N values of X.
0 â‰¤ X â‰¤ 2147483647
1 â‰¤ N â‰¤ 100
For each value of X, you should output the number of ways to write X as the sum of two squares.
Analysis and Solution
This problem was by far the easiest of the lot. But as Facebook title for the problem said â€œToo hard for brute force, switching to dpâ€, this problem was almost impossible to be solved with Brute Force.
The strategy I used was quite simple. If we consider M is the given number, and we want to find out x, y such that:
M = x^2 + y^2
So basically weâ€™ll loop from 0 to sqrt(M) and will find out D such that:
D = M â€“ i*i
and if D is square root is an integer then, this number is a double square.
The python code of this problem is: