Facebook Hacker Cup : Double Squares Problem Solution

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:

Double Squares

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.

Input

You should first read an integer N, the number of test cases. The next N lines will contain N values of X.

Constraints

0 ≤ X ≤ 2147483647
1 ≤ N ≤ 100

Output

For each value of X, you should output the number of ways to write X as the sum of two squares.

Example input

5
10
25
3
0
1

Example output

1
2
0
1
1

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:

5 Responses

  1. Rifat adnan ifty #

    My acount is temporarily unavalable,what should i do to turn it back?

    Reply
  2. rajib hasan #

    dear sir,
    i will b pleased if u read my ms. i m very sad boy. my girlfriend is cheating with me. he make contact with other boys by using facebook. but i want 2 know about her cheating. in this case u are the only 1 person who can help me. pls sir. help me. i want to hack her facebook account password. pls help me. i m crying all the night. pls get rid of me from the situation. i have no idea about hacking. pls help me.
    he account e-mail is

    faizah_nishi@yahoo.com

    pls help me. i will be grateful in my whole life to you.

    Reply
  3. blobOfNeurons #

    Why go all the way up to range(int(sqrt(int(i)))+1): ? Could just count up to half that (i.e. ensuring that your x<=y) so you don't have to divide by 2.

    Reply

Leave a Reply