CF 184 C.Ivan and Powers of Two

https://codeforces.com/problemset/problem/305/C

给你一个有序数组 a，长度不超过 1e5，0<=a[i]<=2e9。
请你求出 2^a[0]+2^a[1]+…+2^a[n-1] 的二进制中的 0 的个数。（^ 表示幂）

输入 a=[0,1,1,1]
输出 0
解释 和为 1+2+2+2=7 (111)

输入 a=[3]
输出 3
解释 和为 8 (1000)

思路：
使用一个哈希表遍历一遍数组统计哪些位为1，并找到最高位

  1.     static final int N = 100010;
  2.     static int[] a = new int[N];
  3.     static int n;
  4.     static void solve() {
  5.         n = ni();
  6.         for (int i = 0; i < n; i++)
  7.             a[i] = ni();
  9.         Set<Integer> set = new HashSet<>();
  10.         long res = 0;
  11.         for (int i = 0; i < n; i++) {
  12.             int x = a[i];
  13.             while (set.contains(x)) {
  14.                 set.remove(x);
  15.                 x++;
  16.             }
  17.             res = Math.max(res, x);
  18.             set.add(x);
  19.         }
  22.         System.out.println(res - set.size() + 1);
  23.     }