Join Us
In Q2. We can use DP with states as dp[prev][xor_value] as boolean telling that is it possible to get xor_value with prev value...
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int bitCount(int x) {
return __builtin_popcount(x);
}
vector<int> A;
set<int> result;
int n;
const int MAX_VAL = 1001;
const int MAX_XOR = 2048;
vector<vector<bool>> dp;
void dfs(int curr, int prev_val, int xor_val) {
if (curr == n) return;
if (prev_val >= MAX_VAL || xor_val >= MAX_XOR) return;
if (dp[prev_val][xor_val]) return;
dp[prev_val][xor_val] = true;
// Option 1: Not pick A[curr]
dfs(curr + 1, prev_val, xor_val);
// Option 2: Pick A[curr] if valid
if (A[curr] > prev_val) {
int bc = bitCount(A[curr] ^ prev_val);
int bc2 = bitCount(A[curr]);
if (bc <= bc2) {
int new_xor = xor_val ^ A[curr];
result.insert(new_xor);
dfs(curr + 1, A[curr], new_xor);
}
}
}
int countDistinctXors(vector<int>& input) {
A = input;
n = A.size();
result.clear();
dp = vector<vector<bool>>(MAX_VAL, vector<bool>(MAX_XOR, false));
for (int i = 0; i < n; ++i) {
result.insert(A[i]);
dfs(i + 1, A[i], A[i]);
}
return result.size();
}
};
int main() {
Solution sol;
vector<int> A1 = {1, 2, 3};
cout << "Test 1: " << sol.countDistinctXors(A1) << endl;
vector<int> A2 = {5, 5, 5};
cout << "Test 2: " << sol.countDistinctXors(A2) << endl;
vector<int> A3 = {4, 3, 2, 1};
cout << "Test 3: " << sol.countDistinctXors(A3) << endl;
vector<int> A4 = {3, 7, 5};
cout << "Test 4: " << sol.countDistinctXors(A4) << endl;
return 0;
}
I don't know it will work or not I got this exact same question and failed to solve in OA but came up with this solution after OA
.