add 633

fishercoder1534 · fishercoder1534 · commit 37297e47553b · 2017-07-04T09:22:26.000+08:00
diff --git a/README.md b/README.md
@@ -20,6 +20,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
+|633|[Sum of Square Numbers](https://leetcode.com/problems/sum-of-square-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_633.java) | O(logn) |O(1) | Easy | Binary Search
 |628|[Maximum Product of Three Numbers](https://leetcode.com/problems/maximum-product-of-three-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_628.java) | O(nlogn) |O(1) | Easy |
 |625|[Minimum Factorization](https://leetcode.com/problems/minimum-factorization/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_625.java) | O(?) |O(?) | Medium | 
 |624|[Maximum Distance in Arrays](https://leetcode.com/problems/maximum-distance-in-arrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_624.java) | O(nlogn) |O(1) | Easy | Sort, Array
diff --git a/src/main/java/com/fishercoder/solutions/_629.java b/src/main/java/com/fishercoder/solutions/_629.java
@@ -0,0 +1,31 @@
+package com.fishercoder.solutions;
+
+/**
+ * 629. K Inverse Pairs Array
+ *
+ * Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.
+ We define an inverse pair as following: For ith and jth element in the array,
+ if i < j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.
+ Since the answer may very large, the answer should be modulo 109 + 7.
+
+ Example 1:
+ Input: n = 3, k = 0
+ Output: 1
+ Explanation:
+ Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.
+
+ Example 2:
+ Input: n = 3, k = 1
+ Output: 2
+ Explanation:
+ The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.
+
+ Note:
+ The integer n is in the range [1, 1000] and k is in the range [0, 1000].
+ */
+public class _629 {
+
+    public int kInversePairs(int n, int k) {
+        return 0;
+    }
+}
diff --git a/src/main/java/com/fishercoder/solutions/_633.java b/src/main/java/com/fishercoder/solutions/_633.java
@@ -0,0 +1,32 @@
+package com.fishercoder.solutions;
+
+/**
+ * Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.
+
+ Example 1:
+ Input: 5
+ Output: True
+ Explanation: 1 * 1 + 2 * 2 = 5
+
+ Example 2:
+ Input: 3
+ Output: False
+ */
+public class _633 {
+    public boolean judgeSquareSum(int c) {
+        if (c < 0) return false;
+        int left = 0;
+        int right = (int) (Math.sqrt(c));
+        while (left <= right) {
+            int curr = left*left + right*right;
+            if (curr > c) {
+                right--;
+            } else if (curr < c) {
+                left++;
+            } else {
+                return true;
+            }
+        }
+        return false;
+    }
+}
