/**
 * 1-1000這1000個數(shù)放在含有1001個元素的數(shù)組中,還有唯一的一個元素值重復,
 * 其他均只出現(xiàn)一次.每個數(shù)組元素只能訪問一次,設計一個算法,將它找出來;
 * 不用輔助存儲空間,能否設計一個算法實現(xiàn)?
 */

import java.util.Random;
import java.util.Scanner;

public class 唯一成對的數(shù) {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//數(shù)組大小
        int[] nums = new int[n];
        //按1---(n-1)個數(shù)字依次存入數(shù)組中
        for (int i = 0; i < n - 1; i++) {
            nums[i] = i + 1;
        }
        //數(shù)組最后一個元素用隨機數(shù)來確定,用來確定哪個數(shù)會是成對
        nums[n - 1] = new Random().nextInt(n - 1) + 1;
        //隨機一個index下標,用于與最后一個元素交換位置
        int index = new Random().nextInt(n - 1);

        // swap 位置
        int temp = nums[n - 1];
        nums[n - 1] = nums[index];
        nums[index] = temp;

        // foreach 出來看一下數(shù)組
        for (int i : nums) {
            System.out.print(i + " ");
        }
        System.out.println();
        /*
            知識點1:任何數(shù)異或0等于數(shù)本身
            知識點2:數(shù)異或自己等于0, 即A^A=0, 可用于消除兩兩重復的數(shù)

            假設 n = 1001 那么就存1到1000的數(shù)進數(shù)組,最后一個數(shù)用于確定哪個數(shù)字是一對
            解題思路: A^A^B^C^C = B 可知異或可以消除兩兩重復的數(shù)
            那么,我們題目要求的是,找出兩兩重復的數(shù),而不是消除它,腦筋急轉(zhuǎn)彎
            我們可以通過 1^2^...k..^1000 ^(1^2^....k......k.^1000)
            那么因為數(shù)值1,2,3,....n都成對存在而消除了,但是卻有3個k ,
            k^k^k ===>  k^k = 0,0^k = k,這就可以得出結(jié)果了
         */
        int result = 0;
        for (int i = 1; i <= n - 1; i++) {
            result ^= i;
        }
        for (int i = 0; i < n; i++) {
            result ^= nums[i];
        }
        System.out.println(result);
    }
}