Sum of Square Numbers

    

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

Example 1:

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

Example 2:

Input: c = 3
Output: false

Example 3:

Input: c = 4
Output: true

Example 4:

Input: c = 2
Output: true

Example 5:

Input: c = 1
Output: true

 

Constraints:

  • 0 <= c <= 231 - 1

The solutions to the Above Question


There are several methods to solve this problem. The first one is the brute force approach in which we simply make two for loop one inside another and find two numbers such that their sum becomes equal to the given integer.
The second approach can be using two pointer approach where we take two integers and then square them and add them, just like two sum problem. For more, you can see the video. In the two-sum problem there we had three conditions the same condition will be here also and then we decide what to do next.
The third method is using a map. We will make an unordered map and then we make a for loop. In the loop, we find the remaining number, if found in the map we return true, else insert the current number. For better understanding see the video or the code below.


Solution 1
This is another approach in which we don't have two make map, or anything. Just a integer to keep the other number and a if condition to check the condition.
class Solution {
public:
    bool judgeSquareSum(int c) {
        cout<<(sqrt(90));
      for(int i=0;i<=sqrt(c);i++) {
            int k=sqrt(c-i*i);
            if(k*k==c-i*i){
              return true;  
            } 
        }
        return false;
    }
};


Solution 2

This is using the map as stated above.

class Solution {
public:
    bool judgeSquareSum(int c) {
        unordered_map<long long int,long long int>mymap;
        for(long long int i=0; i*i<=c; i++){
            if(mymap.find(c-i*i)==mymap.end()){
                mymap.insert({i*i,i});
                if(mymap.find(c-i*i)!=mymap.end()){
                return true;
            }
            }
            else{
                return true;
            }
        }
        return false;
    }
};


You can also try the two-pointer approach and the brute force approach by yourself.


Join our Telegram Channel for the latest updates-Click Here or search for Coding Karo.