OJ1：丢失的练习册 ¶

Description¶

开学了，阳光小学准备给每个学生发放三本练习册。为了方便发放，每本练习册上都印上了学生的学号。然而，运输过程中由于道路的颠簸，原本捆绑整齐的练习册散落一地，司机师傅再将练习册堆叠在一起时，学号已经完全打乱。更糟糕的是，当他清点练习册总数时，发现少了一本，为了尽快弄清楚丢失的是印有哪位学生学号的练习册，司机师傅只好拿出本子，一个个记录每个练习册上的学号。聪明的你能够通过编程的方法找到是印有哪个同学学号的练习册丢失了吗？

Input¶

第 1 行为学生的总数：N；

第 2 到第 3N 行为司机师傅记录的练习册上的学号；

注意：没有丢失练习册的学号会出现 3 次，而丢失练习册的学号只会出现 2 次。

Output¶

丢失练习册上对应的学号。

Example¶

input:
3
2021001
2021001
2023002
2023003
2023002
2023003
2023002
2021001

output:
2023003

Hint¶

1. 取值范围 .

N 的取值范围为 \([1,1\times10^6]\) 的整数；

学生学号的取值范围为 \([0,2\times10^9]\) 的整数；

2. 测试样例 .

1~3 测试样例 \(N<1\times10^4\) ;

4~5 测试样例 \(1\times10^4\leq N\leq 5\times10^5\)；

6~10 测试样例 \(5\times10^5< N \leq1\times10^6\)；

3. 时间和空间 .

本道 OJ 本身并不难，但对程序运行的时间和空间有较为严格的要求，时间需要为 \(O(n)\)，空间为 \(O(1)\) 才能通过所有的测试样例，请同学们从算法效率的角度出发，选择合适的算法。

Solution¶

每一位数二进制所有位数字之和，模 3 除以 2 得到结果的二进制表示，在使用左移操作得到结果。

Code¶

Language: C

#include <stdio.h>

int main(int argc, const char *argv[])
{
    int N, input, result = 0;
    int arr[32] = {0};

    scanf("%d", &N);
    for (int i = 0; i < 3 * N - 1; i++)
    {
        scanf("%d", &input);
        for (int j = 0; j < 32; j++)
        {
            arr[j] += (input & (1 << j)) ? 1 : 0;
        }
    }

    for (int i = 0; i < 32; i++)
    {
        result += ((arr[i] % 3) / 2) << i;
    }

    printf("%d", result);
    return 0;
}