fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector<int> computePowerArray(const vector<int>& A) {
  7.     const int BITS = 20;
  8.     vector<int> result(BITS, 0);
  9.  
  10.     for (int i = 0; i < BITS; ++i) {
  11.         int requiredMask = (1 << (i + 1)) - 1; // all bits from 0 to i
  12.         int currentMask = 0, count = 0;
  13.  
  14.         vector<int> sortedA = A;
  15.         sort(sortedA.begin(), sortedA.end(), greater<int>()); // greedy pick
  16.  
  17.         for (int val : sortedA) {
  18.             currentMask |= val;
  19.             ++count;
  20.  
  21.             if ((currentMask & requiredMask) == requiredMask) {
  22.                 result[i] = count;
  23.                 break;
  24.             }
  25.         }
  26.     }
  27.  
  28.     return result;
  29. }
  30.  
  31. void runTest(const vector<int>& input) {
  32.     vector<int> output = computePowerArray(input);
  33.     for (int x : output) cout << x << " ";
  34.     cout << endl;
  35. }
  36.  
  37. int main() {
  38.     cout << "Test Case 1: [1, 2, 3, 4, 5]" << endl;
  39.     runTest({1, 2, 3, 4, 5});
  40.  
  41.     cout << "Test Case 2: [4, 16, 16, 36, 36]" << endl;
  42.     runTest({4, 16, 16, 36, 36});
  43.  
  44.     cout << "Test Case 3: [5, 5, 3, 2, 1, 1]" << endl;
  45.     runTest({5, 5, 3, 2, 1, 1});
  46.  
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test Case 1: [1, 2, 3, 4, 5]
1 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
Test Case 2: [4, 16, 16, 36, 36]
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
Test Case 3: [5, 5, 3, 2, 1, 1]
1 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
https://ideone.com/XI3C97
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!