Problem D:

You have an array arr containing N integers. You can perform the following operation as many time as required:

  • Choose any two elements say arr[i] = x and arr[j] = y.
  • Set arr[i] = x | y and arr[j] = x & y.

You need to maximize the sum of squares of the resulting array.

Constraints are:

Hint 1
  • Take some small examples and write numbers in binary representation and try to observe when you get the maximum sum of squares.

  • To verify:

    • if the following binary numbers are input: 0001, 0011, 0101, 1000.
    • They will get converted to: 0000, 0001, 0001, 1111, to get the optimal answer.

Hint 2
  • Try to sort the numbers and perform operations on adjacent numbers, observe that this does not lead to optimal solution in some cases, for eg (numbers in binary):
    • Input: 00011, 00110, 01000, 10000, 10001, 11000
    • Output array for optimal answer: 00000, 00000, 00000, 10000, 11011, 11111
  • Observe any pattern?
  • Think in terms of count of bits set at a particular position in the input numbers!

Solution approach
  • OBSERVATION: We can shift the bits set at a particular position to the maximum numbers (in the end, i.e. largest numbers), so as to maximize the square value.
  • Find the count of set bits at a particular position in all the numbers, these many numbers from the end should have this bit set while calculating the answer, try some examples yourself.
  • So, we can just maintain a count array for 20 bits, and at the end, construct numbers from the last number using the counts, and break when constructed no is zero, i.e. all counts are used up. See implementation below for details.

Time Complexity

Code

 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template <typename T>
inline void readArray(vector<T>& arr, int n) {
  arr.resize(n);
  for (auto& element : arr) {
    cin >> element;
  }
}

void solve() {
  int n;
  cin >> n;
  vector<ll> arr;
  readArray(arr, n);
  ll ans = 0;
  vector<ll> cnt(21, 0);
  for (int bit = 0; bit <= 20; ++bit) {
    for (int j = 0; j < n; ++j) {
      if (arr[j] & (1 << bit)) {  // bit is set in j-th num
        ++cnt[bit];
      }
    }
  }
  while (1) {
    ll cur = 0;  // constructed number from the last
    for (int bit = 0; bit <= 20; ++bit) {
      if (cnt[bit] > 0) {  // bit available for use
        cur |= (1 << bit);
        --cnt[bit];  // used up;
      }
    }
    ans += cur * cur;  // update ans
    if (cur == 0) {
      break;
    }
  }
  cout << ans << endl;
}

int main() {
  solve();
  return 0;
}

Problem C:

Hint 1

Hint 2

Time Complexity

Code

Problem B:

Hint 1

Hint 2

Time Complexity

Code

Problem A:

Hint 1

Hint 2

Time Complexity

Code