Sum of Square Numbers


  • 0

    Click here to see the full article post


  • 0
    L

    why the for loop use long instead of int?
    for (long a = 0; a * a <= c; a++) --> for (int a = 0; a * a <= c; a++)


  • 0

    @limin9 because a*a can exceed integer range for some integer a.


  • 0
    L

    @vinod23 since c is integer, the condition of a*a <=c will limit the value of a to be in the range of integer.


  • 0

    @limin9 let say range of integer is 10 and c =10. Then when a becomes 4 then a*a exceeds integer range and becomes negative.


  • 0
    E

    One solution not mentioned is to optimize the brute force method by keeping track of squares as we calculate a². Then we can just check the hash to see if c - a² is in there.

        HashMap<Integer, Integer> square_hash = new HashMap<>();  //<Square, Root>        
        //Largest int square
        if (2147395600 < c)
            return false;
        
        for (int n = 0; n*n <= c; n++) {
            int a2 = n*n;
            square_hash.put(a2, n);
            
            if (square_hash.containsKey(c - a2))
                return true;
        }

  • 0

    @emilieroberts Thanks for sharing your approach. We will add it soon in our article.


  • 0
    J

    It is possible to use Two pointers method

      bool judgeSquareSum(int c) {
        assert(c >= 0);
        int i = std::floor(std::sqrt(c));
        if (i * i == c) {
          return true;
        } else {
          int j = 1;
          while (j <= i) {
            if (i * i + j * j == c) {
              return true;
            } else if (i * i + j * j < c) {
              j++;
            } else {
              i--;
            }
          }
        }
    
        return false;
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.