How to Determine Sum of Two Square Numbers?

  • 时间：2020-10-05 13:15:44
  • 分类：网络文摘
  • 阅读：163 次

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a^2 + b^2 = c.

Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:
Input: 3
Output: False

This is a typical/classic math problem, and the computer is very good at solving it by bruteforce algorithms.

Bruteforce Algorithm to Check Sum of Two Square Numbers

The following C++ implements the bruteforce with no optimisation, which runs at O(C) complexity.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (unsigned int a = 0; a * a <= c; ++ a) {
            for (unsigned int b = 0; b * b <= c; ++ b) {
                if (a * a + b * b == c)
                    return true;
            }
        }
        return false;
    }    
};
class Solution {
public:
    bool judgeSquareSum(int c) {
        for (unsigned int a = 0; a * a <= c; ++ a) {
            for (unsigned int b = 0; b * b <= c; ++ b) {
                if (a * a + b * b == c)
                    return true;
            }
        }
        return false;
    }    
};

Optimised Bruteforce Algorithm

We know that n-th square number is the sum of the n-th odd number. For example, 9 = 1 + 3 + 5, and 16 = 1 + 3 + 5 + 7 … Therefore, we can reduce the runtime for the inner loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (unsigned int a = 0; a * a <= c; ++ a) {
            int b =  c - a * a;
            if (isSquare(b)) {
                return true;
            }
        }
        return false;
    }    
 
private:
    inline bool isSquare(unsigned int b) {
        unsigned int i = 1, sum = 0;
        while (sum < b) {
            sum += i;
            i += 2;
        }
        return sum == b;
    }
};
class Solution {
public:
    bool judgeSquareSum(int c) {
        for (unsigned int a = 0; a * a <= c; ++ a) {
            int b =  c - a * a;
            if (isSquare(b)) {
                return true;
            }
        }
        return false;
    }    

private:
    inline bool isSquare(unsigned int b) {
        unsigned int i = 1, sum = 0;
        while (sum < b) {
            sum += i;
            i += 2;
        }
        return sum == b;
    }
};

This optimisation is great, however, the approach still runs at O(C) complexity.

Using SQRT

In fact, we can compute the b value once a is determined, we just need to check if b is an integer, which can be done using the sqrt function, that runs at O(logC). 

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (unsigned int a = 0; a * a <= c; ++ a) {
            int b = (int)sqrt(c - a * a);
            if ((unsigned long)b * b + (unsigned long)a * a == c) {
                return true;
            }
        }
        return false;
    }    
};
class Solution {
public:
    bool judgeSquareSum(int c) {
        for (unsigned int a = 0; a * a <= c; ++ a) {
            int b = (int)sqrt(c - a * a);
            if ((unsigned long)b * b + (unsigned long)a * a == c) {
                return true;
            }
        }
        return false;
    }    
};

The overall complexity is O(sqrt(c)log(c)).

Using Binary Search to Determine if An integer is sum of two square integers

Last but not least, we can use the binary search to determine if an integer is a square – that runs at O(logN) complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (unsigned int a = 0; a * a < = c; ++ a) {
            unsigned int b = c - a * a;
            if (binarySearch(0, b, b)) {
                return true;
            }
        }
        return false;
    }    
    
    bool binarySearch(unsigned int left, unsigned int right, unsigned int n) {
        if (left > right) return false;
        int64_t mid = left + (right - left) / 2;
        if (mid * mid == n) return true;
        if (mid * mid > n) {
            return binarySearch(left, mid - 1, n);
        }
        return binarySearch(mid + 1, right, n);
    }
};
class Solution {
public:
    bool judgeSquareSum(int c) {
        for (unsigned int a = 0; a * a < = c; ++ a) {
            unsigned int b = c - a * a;
            if (binarySearch(0, b, b)) {
                return true;
            }
        }
        return false;
    }    
    
    bool binarySearch(unsigned int left, unsigned int right, unsigned int n) {
        if (left > right) return false;
        int64_t mid = left + (right - left) / 2;
        if (mid * mid == n) return true;
        if (mid * mid > n) {
            return binarySearch(left, mid - 1, n);
        }
        return binarySearch(mid + 1, right, n);
    }
};

This approach also runs at O(log(C)sqrt(C)) complexity.

--EOF (The Ultimate Computing & Technology Blog) --

推荐阅读：
北京体育频道直播-北京体育在线直播观看「高清」　 五星体育直播-五星体育在线直播观看「高清」　 风云足球直播-风云足球在线直播观看「高清」　 吉林篮球直播-吉林篮球在线直播观看「高清」　 江苏体育直播-江苏体育在线直播观看「高清」　 广州竞赛直播-广州竞赛频道在线直播观看「高清」　 广东体育频道直播-广东体育频道在线直播观看「高清」　 高尔夫网球频道直播-CCTV高尔夫网球在线直播「高清」　 央视台球频道直播-斯诺克直播「高清」　 山东体育频道直播-山东体育在线直播观看「高清」　
评论列表
添加评论