# 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;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://syjohnson11.gitbook.io/leetcode/9_math.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.