> For the complete documentation index, see [llms.txt](https://syjohnson11.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://syjohnson11.gitbook.io/leetcode/9_math.md).

# 9. Math

## 获得随机数 Shuffle an array

* 这题的关键在于要设计一个shuffle算法使得每个位置的数被shuffle的概率相同
* 于是就有了int i = random.nextInt(j + 1)的这个trick
* int index = random.nextInt(i + 1);
* nextInt返回的是\[0,i+1)的整数
* 所以不可以是random.nextInt(0, i)，设想一共就两个数(6,4)
* 如果是nextInt(0,i) i start from 1, 这样的话4就只可能在\[0,0]区间内变换，就只有这一种shuffle可能了
* [这里有人给了个简单的证明](https://discuss.leetcode.com/topic/53978/first-accepted-solution-java/11)

```
public class Solution {
    private int[] nums = null;
    private Random random = null;
    public Solution(int[] nums) {
        this.nums = nums;
        random = new Random();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return Arrays.copyOf(nums, nums.length);
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int[] arr = Arrays.copyOf(nums, nums.length);
        for(int i = 1; i < arr.length; i++){
            int index = random.nextInt(i + 1);
            swap(arr, i, index);
        }
        return arr;
    }
    private void swap(int[] nums, int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}
```

## Count Primes

* 给定一个数n, 求比n小的素数的个数
* 建立一个boolean\[] notPrime = new boolean\[n]
* 然后每找到一个prime number, cnt++, 并把它的所有的倍数都设成notPrime = true

```
public int countPrimes(int n) {
        if (n < 2) return 0;
        boolean[] notPrime = new boolean[n];
        notPrime[0] = true;
        notPrime[1] = true;
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if(notPrime[i] == false) {
                cnt++;
                for (int j = 2; i * j < n; j++) {
                    notPrime[i * j] = true;
                }
            }
        }
        return cnt;
    }
```

## Reverse Integer

* 本身不难
* 注意integer overflow的edge case

```
public int reverse(int x) {
        if (x == 0) return 0;
        int sign = x > 0 ? 1 : -1;
        long num = Math.abs(x), res = 0;
        while (num > 0) {
            res = res * 10 + num % 10;
            num /= 10;
        }
        res = res * sign;
        if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) res;
    }
```