10

これは、Google からの最近のインタビューの質問です。

f(X, Y) を、X と Y の 2 進数表現で対応する異なるビットの数として定義します。たとえば、2 と 7 の 2 進数表現はそれぞれ 010 と 111 であるため、f(2, 7) = 2 です。1 番目と 3 番目のビットが異なるため、f(2, 7) = 2 です。

N 個の正の整数、A1、A2、…、AN の配列が与えられます。1 ≤ i、j ≤ N となるすべてのペア (i, j) の f(Ai, Aj) の合計を求めます

例えば：

A=[1, 3, 5]

我々は返します

f(1, 1) + f(1, 3) + f(1, 5) + f(3, 1) + f(3, 3) + f(3, 5) + f(5, 1) + f (5, 3) + f(5, 5) =

0 + 1 + 1 + 1 + 0 + 2 + 1 + 2 + 0 = 8

O（n ^ 2）であるこのソリューションを考えることができました

int numSetBits(unsigned int A) {
    int count  = 0;

    while(A != 0) {
        A = A & (A-1);
        count++;
    }

    return count;
}

int count_diff_bits(int a, int b)
{
    int x = a ^ b;

    return numSetBits(x);
}

for (i = 0; i < n; i++)
   for (j = 0; j < n; j++) {
       sum += count_diff_bits(A[i], A[j]);
   }
}

私が考えることができる別のアプローチは次のとおりです（各要素には2進数が1つしか含まれていないことを考慮して）：

  • 配列の最後から開始
  • これまでに見つかった 1 と 0 の数を保持する
  • 現在の要素が 1 の場合count_of_zeros、最終的な合計に寄与します。
  • 配列の先頭に到達するまで、このように続けます。

このアプローチは正しいですか。

4

2 に答える 2

16

配列を反復し、 [1, 3, 5]のように、各ビット インデックスの「オン」ビットの数をカウントします。

0 0 1
0 1 1
1 0 1
-----
1 1 3

ここで、各ビット カウンターについて、次のように計算します。

[ビット数] * [配列サイズ - ビット数] * 2

すべてのビットの合計...

上記の例では:

3 * (3 - 3) * 2 = 0
1 * (3 - 1) * 2 = 4
1 * (3 - 1) * 2 = 4
          total = 8

これが機能する理由を示すために、1 ビットを使用して問題のサブセットを見てみましょう。の配列がある場合に何が起こるか見てみましょう: [1, 1, 0, 0, 1, 0, 1]。カウントは 4 で、サイズは 7 です。最初のビットを配列内のすべてのビット (問題のように自己を含む) で調べると、次のようになります。

1 xor 1 = 0
1 xor 1 = 0
1 xor 0 = 1
1 xor 0 = 1
1 xor 1 = 0
1 xor 0 = 1
1 xor 1 = 0

ご覧のとおり、このビットの寄与は「オフ」ビットの数です。同じことが他の「オン」ビットにも当てはまります。各「オン」ビットは「オフ」ビットの数としてカウントされると言えます。

[ビット数] * [配列サイズ - ビット数]

では、2 の掛け算はどこから来るのでしょうか? これらを除いて、「オフ」ビットで同じことを行うため、寄与は「オン」ビットの数です。

[配列サイズ - ビット数] * [ビット数]

もちろん、これは上記と同じで、乗算することができます...

複雑さはO(n*k)で、kはビット数 (コードでは 32) です。

于 2015-10-07T15:51:54.923 に答える
0 
#include <bits/stdc++.h>
#define MOD 1000000007ll
using namespace std;
typedef long long LL;

int solve(int arr[], int n) {

    int ans = 0;
    // traverse over all bits
    for(int i = 0; i < 31; i++) {

        // count number of elements with ith bit = 0
        long long count = 0;
        for(int j = 0; j < n; j++) if ( ( arr[j] & ( 1 << i ) ) ) count++;

        // add to answer count * (n - count) * 2
        ans += (count * ((LL)n - count) * 2ll) % MOD;
        if(ans >= MOD) ans -= MOD;
    }

    return ans;
}

int main() {

    int arr[] = {1, 3, 5};
    int n = sizeof arr / sizeof arr[0];
    cout << solve(arr, n) << endl; 
    return 0;
}
于 2016-07-02T18:11:51.593 に答える