1

I came across this problem today, in this we have been given a sorted array a[] in ascending order and then we find sum of the numbers 2a1, 2a2, 2a3, ..., 2an and we need to find the minimum number of additional integers of the type 2l (l is non-negative) that must be required such that the sum total of all integers present equals 2k - 1 for some integer k (k is non-negative).

For example:

The input consists of an integer n in first line. The second input line contains n space-separated integers a(1), a(2), ..., a(n).

Example 1:
3
0 1 2

The answer in this case is 0 since 20+21+22 = 7 is already in the form of 2k-1 for k=3.

Example 2:
3
2 4 5

the answer for this case is 3 since 22+24+25=52 and to make it of 2k-1 we have 63 so required 20,21,23 as the three term.

I approached this problem to find the sum and then count the number of 1's in the binary representation and then answer equals max(a[i])-count.

But the problem that I get is the given constraints in the problem
1 ≤ n ≤ 10^5
0 ≤ a[i] ≤ 2*10^9

Can someone help? This problem i got in a programming contest and solutions accepted in 2.6 MB memory. So,Storing or taking array bits of 2*10^9 bits would not be better.There will be a different approach or idea i think.

4

2 回答 2

3

你不需要 2*10^9 位的内存来解决这个问题。n (n < 10^5) 上的边界提出了另一种解决方案：

(1) 排序a_i：

3 3 3 3 3 5 7 9

(2) 通过二分查找找到连续的副本来消除重复。在这种情况下，你有5（=101二进制），所以3 3 3 3 3变成3 5. 你a_i现在是3 5 5 7 9。（请注意，这相当于添加二进制数字，但它更有效，因为您知道您的数字最多有 10^9 位，但最多设置 10^5 位！）

(3) 重复步骤 2，直到不再有重复项。在这个例子中，你只需要另一个步骤，你最终得到3 6 7 9.

(4) 计算max(a_i) - number of a_i left + 1。这是你的结果，在这种情况下9-4+1=6。

步骤（2）的可能实现：

我会尝试的第一件事是从头开始覆盖，但保留一个指针来检查我现在的位置，所以：你读3. 您对最后一个进行二进制搜索3并保留指向下一个元素的指针。然后覆盖：3 3 3 3 3 5 7 9-> 3 5 x x x *5 7 9（位置上的内容无关紧要x，指针现在位于5）。现在，对于第一个解决方案，只需从末尾复制所有内容以使其再次连续：3 5 5 7 9并记住您的数组现在更短了。

这不是最有效的解决方案，因为如果您有一个类似的数组，它将导致大量复制3 3 4 4 5 5 6 6...，但它应该足够体面。

为了获得更好的性能，您只能执行步骤 (1)，然后将所有内容插入到映射a_i到其出现次数的 hashmap 中，然后对该 hashmap 进行操作。这对于您的约束来说非常快，但是在 C 中实现哈希图并非易事。

于 2013-10-26T23:14:11.053 回答
0

您需要做的是使用位数组。

你需要一个i <= 2*10 9 (20 亿)。要表示 20 亿位，您需要大约 256MB 的内存（每个字节存储 8 位）。您可能需要创建一些方便的抽象层来提供类似的函数.get(int n)，.set(int n)这些函数将读取和保存该位数组中的位。

要分配数组，请使用malloc：

typedef byte unsigned char;
// 256MB, enough for 2 billion bits
byte * bit_array = malloc(256*1024*1024);

// or use calloc, which initializes to 0:
byte * bit_array = calloc(256*1024*1024, 1);

要设置位 n，请使用以下分配：

bit_array[n/8] |= 1 << (n % 8);

要获得位 n，请使用以下表达式：

(bit_array[n/8] >> (n % 8)) & 1

你的算法可能是这样的：

  • 全部 1 组创建所需最大长度的位数组。
  • 循环遍历所有 a i并将该位数组中的第 i 位设置为 0。
  • 计算仍然设置为 1 的位数。这就是你的答案。
于 2013-10-26T22:22:17.497 回答