Sum of Square Numbers

Problem Statement :

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Sample :

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Little bit of Math we will do here.

a² + b² = c. 

Since we have a given value c, we can rewrite the formula as

a = √c-b² 

Now we need to iterate all possible values of b and check whether √c-b² is a valid integer.

Java Program

public class Solution {
  public static void main(String args[]){
    int[] input = {5,3};
    for(int i=0; i<input.length; i++){
      boolean result =new Solution().isSquareSum(input[i]);
      System.out.println("isSquareSum("+input[i]+") is "+result);
    }
  }
  public boolean isSquareSum(int c){
    for(long b=1; b*b <= c; b++){
       double a = Math.sqrt(c-(b*b));
       int val = (int)a;
       if(val == a){
          return true;
       } 
    }
    return false;
  }
}

Output:

isSquareSum(5) is true
isSquareSum(3) is false

Few things to remember, for loop must have b² ≤ c because we can have the input as 0. Also the variables ‘a’ and ‘b’ should be large enough to hold higher values.

Happy Coding

Enjoy!!!