hardBacktrackingPattern: Subsets/Permutations
Count of Safe XOR Permutations Solution
Problem Statement
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
Example 1:
Input:nums = [1, 2, 3], banned = [3]
Output:2
Explanation: Out of 6 possible permutations, the unique safe ones are [1, 3, 2] (prefix XORs: 1, 2, 0) and [2, 3, 1] (prefix XORs: 2, 1, 0). All other permutations contain a prefix with a bitwise XOR sum of 3.
Example 2:
Input:nums = [1, 1, 2], banned = [0]
Output:2
Explanation: The distinct permutations of the array are [1, 1, 2], [1, 2, 1], and [2, 1, 1]. Among these, [1, 1, 2] is unsafe because its second prefix [1, 1] has a XOR sum of 1 ^ 1 = 0, which is banned.
Constraints
- 1 <= nums.length <= 11
- 0 <= nums[i] <= 10^6
- 1 <= banned.length <= 10^5
- 0 <= banned[i] <= 10^6
Time: O(N!) Space: O(N)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from collections import Counter
def count_safe_xor_permutations(nums, banned):
banned_set = set(banned)
counts = Counter(nums)
unique_elements = sorted(counts.keys())
memo = {}
def backtrack(curr_xor, state_tuple, remaining):
state = (curr_xor, state_tuple)
if state in memo:
return memo[state]
if remaining == 0:
return 1
total = 0
state_list = list(state_tuple)
for i, num in enumerate(unique_elements):
if state_list[i] > 0:
next_xor = curr_xor ^ num
if next_xor not in banned_set:
state_list[i] -= 1
total += backtrack(next_xor, tuple(state_list), remaining - 1)
state_list[i] += 1
memo[state] = total
return total
initial_state = tuple(counts[x] for x in unique_elements)
return backtrack(0, initial_state, len(nums))