First give two algorithm questions for the interview.

• One number has an odd number and the other number has an even number. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)
• The two kinds of numbers appear odd times and the other numbers appear even times. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)

There are many solutions to these two problems, but the fastest and simplest should be XOR operation.

Next, we need to know what XOR operation is?

XOR operation

xor is a mathematical operator. It applies to Logical operation . The mathematical symbol of xor is "⊕" and the computer symbol is "xor". The algorithm is:

a⊕b = (¬a ∧ b) ∨ (a ∧¬b)

If the values of a and b are different, the XOR result is 1. If the values of a and b are the same, the XOR result is 0.

XOR is also called semi addition, and its algorithm is equivalent to binary addition without carry: in binary, 1 represents true and 0 represents false, then the algorithm of XOR is: 0 ⊕ 0 = 0, 1 ⊕ 0 = 1, 0 ⊕ 1 = 1, 1 ⊕ 1 = 0 (the same is 0 and the difference is 1). These algorithms are similar to addition Is the same, but without carry, so XOR is often regarded as non carry addition.

To sum up, the XOR operation is that the same is 0 and the difference is 1. And A ^ A = 0 A ^ 0 = A. Both commutative law and associative law are satisfied.

Next, we begin to solve the two algorithm problems we proposed before.

Topic 1

One number has an odd number and the other number has an even number. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)

thinking

1. Because it indicates that the space complexity is O(1), you can't create additional arrays, but only some additional variables.
2. From the XOR operation above, A ^ A = 0 A ^ 0 = A. Only one number in the changed title appears odd times. Therefore, even numbers are directly eliminated to 0, and finally there are only odd numbers.

Code demonstration

/**
 * @version v1.0
 * @ProjectName: data structure
 * @ClassName: demo01
 * @Description: One number has an odd number and the other number has an even number. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)
 *                The two kinds of numbers appear odd times and the other numbers appear even times. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)
 * @Author: Mr. Zhao
 * @Date: 2022/2/9 10:25
 */

public class demo01 {
    /**
     * One number has an odd number and the other number has an even number. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)
     * A ^ A = 0     A ^ 0 = A    Satisfy commutative law and associative law
     * @param arr
     */
    public static void printOddTimesNum1 (int[] arr) {
        int eor = 0;
        for (int cur : arr) {
            eor = cur ^ eor;
        }
        System.out.println(eor);
    }
}    

Topic 2

The two kinds of numbers appear odd times and the other numbers appear even times. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)

thinking

1. Let's start with the whole XOR operation. In this way, we need a number that is a ^ b. here ab refers to the two numbers that are odd times.
2. Then we extract the rightmost value in eor, because this value represents the bit different from a and b. (fixed writing)
3. We can separate a and b by this number, and then we need a or b
4. Finally, another bit is obtained by XOR operation between the obtained number and eor.

Code demonstration

/**
 * @version v1.0
 * @ProjectName: data structure
 * @ClassName: demo01
 * @Description: One number has an odd number and the other number has an even number. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)
 *                The two kinds of numbers appear odd times and the other numbers appear even times. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)
 * @Author: Mr. Zhao
 * @Date: 2022/2/9 10:25
 */

public class demo01 {
    
    /**
     * The two kinds of numbers appear odd times and the other numbers appear even times. It is required to find this number, and the time complexity is O(n) and the space complexity is O(1)
     * Idea:
     * 1，Let's start with the whole XOR operation. In this way, we need a number that is a ^ b. here ab refers to the two numbers that are odd times.
     * 2，Then we extract the rightmost value in eor, because this value represents the bit different from a and b.
     * 3，We can separate a and b by this number, and then we need a or b
     * 4，Finally, another bit is obtained by XOR operation between the obtained number and eor.
     * @param arr
     */
    public static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        //eor = a ^ b (here a and b represent the two odd numbers)
        //eor != 0
        //eor must have a position of 1, which is a position where a and b are different
        /**
         * Extract the rightmost 1
         * The principle is as follows:
         * A 10000111
         * ~A 01111000
         * ~A+1 01111001
         * A & (~A+1) 00000001
         */
        int rightOne = eor & (~eor + 1);
        int onlyOne = 0;
        //Through the following for loop, we can know a number of a or b, and then we can XOR another number through this number
        for (int cur : arr) {
            if ((cur & rightOne) == 1) {
                onlyOne ^= cur;
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }
}