add 634

fishercoder1534 · fishercoder1534 · commit 6380ca3ce844 · 2017-07-04T09:37:52.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
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
+|634|[Find the Derangement of An Array](https://leetcode.com/problems/find-the-derangement-of-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_634.java) | O(n) |O(1) | Medium | Math
 |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 | 
diff --git a/src/main/java/com/fishercoder/solutions/_634.java b/src/main/java/com/fishercoder/solutions/_634.java
@@ -0,0 +1,31 @@
+package com.fishercoder.solutions;
+
+/**
+ * 634. Find the Derangement of An Array
+ *
+ * In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.
+
+ There's originally an array consisting of n integers from 1 to n in ascending order, you need to find the number of derangement it can generate.
+
+ Also, since the answer may be very large, you should return the output mod 109 + 7.
+
+ Example 1:
+ Input: 3
+ Output: 2
+ Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].
+
+ Note:
+ n is in the range of [1, 106].
+ */
+public class _634 {
+    /**reference: https://discuss.leetcode.com/topic/94442/java-5-lines-o-1-space-solution
+     * and https://leetcode.com/articles/find-derangements/#approach-5-using-formula-accepted*/
+    private static final int M = 1000000007;
+    public int findDerangement(int n) {
+        long ans = 1;
+        for (int i = 1; i <= n; i++) {
+            ans = (i * ans % M + (i%2 == 0 ? 1 : -1)) % M;
+        }
+        return (int) ans;
+    }
+}
