Count of Safe XOR Permutations — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums, which may contain duplicate elements, and an integer array banned. A permutation of nums is considered "safe" if the bitwise XOR sum of any of its prefixes is not present in the banned array. Return the total number of unique safe permutations of nums. Since the array nums can contain duplicate values, you must only count distinct permutations.
Examples
Input
[1, 2, 3], [0, 3]
Output
0
Explanation: Step-by-step: We have three elements [1, 2, 3] and two banned numbers [0, 3]. The XOR sum of any prefix of the permutation [1, 2, 3] will always be present in the banned array {0, 3}. Therefore, the total number of unique safe permutations of nums is 0.
Input
[1], []
Output
1
Explanation: Step-by-step: We have one element [1] and no banned numbers. The permutation [1] is safe. Therefore, the total number of unique safe permutations of nums is 1.
Constraints
- 1 <= nums.length <= 11
- 0 <= nums[i] <= 10^6
- 1 <= banned.length <= 10^5
- 0 <= banned[i] <= 10^6
Optimal Approach & Strategy
Use backtracking with a frequency map to generate unique permutations directly. Maintain the current prefix XOR value and prune branches immediately if the current XOR sum is in the banned set, achieving O(N!) complexity with efficient state pruning.
Brute Force Approach
Generate all possible permutations of the array using backtracking, then verify each permutation by calculating every prefix XOR sum. Filter out permutations that contain a banned value.
Verified Code Solutions
function countSafeXorPermutations(nums, banned) {
const bannedSet = new Set(banned);
const counts = new Map();
for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
const uniqueNums = [...new Set(nums)].sort((a, b) => a - b);
function backtrack(currXor, remaining) {
if (remaining === 0) return 1;
let count = 0;
for (const num of uniqueNums) {
if (counts.get(num) > 0) {
const nextXor = currXor ^ num;
if (!bannedSet.has(nextXor)) {
counts.set(num, counts.get(num) - 1);
count += backtrack(nextXor, remaining - 1);
counts.set(num, counts.get(num) + 1);
}
}
}
return count;
}
let safeCount = 0;
for (const num of uniqueNums) {
const countsCopy = new Map(counts);
countsCopy.set(num, countsCopy.get(num) - 1);
safeCount += backtrack(0, uniqueNums.length - 1);
countsCopy.set(num, countsCopy.get(num) + 1);
}
return safeCount;
}#include <vector>
#include <unordered_set>
#include <algorithm>
class Solution {
private:
int n;
std::vector<int> memo;
std::unordered_set<int> banned_set;
std::vector<int> sorted_nums;
int dfs(int mask, int curr_xor) {
if (mask == (1 << n) - 1) {
return 1;
}
if (memo[mask] != -1) {
return memo[mask];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) == 0) {
// To avoid duplicate permutations, we only use a duplicate element
// if its preceding identical element in the sorted array has already been used.
if (i > 0 && sorted_nums[i] == sorted_nums[i - 1] && (mask & (1 << (i - 1))) == 0) {
continue;
}
int next_xor = curr_xor ^ sorted_nums[i];
if (banned_set.find(next_xor) == banned_set.end()) {
ans += dfs(mask | (1 << i), next_xor);
}
}
}
return memo[mask] = ans;
}
public:
int countSafeXorPermutations(std::vector<int>& nums, std::vector<int>& banned) {
n = nums.size();
sorted_nums = nums;
std::sort(sorted_nums.begin(), sorted_nums.end());
banned_set = std::unordered_set<int>(banned.begin(), banned.end());
memo.assign(1 << n, -1);
return dfs(0, 0);
}
};class Solution {
public int countSafePermutations(int[] nums, int[] banned) {
Set<Integer> xor_set = new HashSet<>();
for (int num : banned) {
xor_set.add(num);
}
xor_set.add(0);
int n = nums.length;
int res = 0;
backtrack(0, 0);
return res;
}
private void backtrack(int idx, int curr_xor) {
if (idx == n) {
res += 1;
return;
}
for (int i = 0; i < n; i++) {
if (!xor_set.contains(nums[i]) && !xor_set.contains(curr_xor ^ nums[i])) {
backtrack(idx + 1, curr_xor ^ nums[i]);
}
}
}
}def countSafePermutations(nums, banned):
xor_set = set()
for num in banned:
xor_set.add(num)
n = len(nums)
xor_set.add(0)
res = 0
def backtrack(idx, curr_xor):
if idx == n:
res += 1
return
for i in range(n):
if i not in xor_set and (curr_xor ^ nums[i]) not in xor_set:
backtrack(idx + 1, curr_xor ^ nums[i])
backtrack(0, 0)
return resfunction countSafeXorPermutations(nums, banned) {
const bannedSet = new Set(banned);
const counts = new Map();
for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
const uniqueNums = [...new Set(nums)].sort((a, b) => a - b);
function backtrack(currXor, remaining) {
if (remaining === 0) return 1;
let count = 0;
for (const num of uniqueNums) {
if (counts.get(num) > 0) {
const nextXor = currXor ^ num;
if (!bannedSet.has(nextXor)) {
counts.set(num, counts.get(num) - 1);
count += backtrack(nextXor, remaining - 1);
counts.set(num, counts.get(num) + 1);
}
}
}
return count;
}
let safeCount = 0;
for (const num of uniqueNums) {
const countsCopy = new Map(counts);
countsCopy.set(num, countsCopy.get(num) - 1);
safeCount += backtrack(0, uniqueNums.length - 1);
countsCopy.set(num, countsCopy.get(num) + 1);
}
return safeCount;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.