Dada una array arr[] que consta de N enteros positivos. La tarea es contar el número de diferentes subconjuntos no vacíos de arr[] que tienen un XOR bit a bit máximo .
Ejemplos:
Entrada: arr[] = {3, 1}
Salida: 1
Explicación: El XOR bit a bit máximo posible de un subconjunto es 3.
En arr[] solo hay un subconjunto con XOR bit a bit como 3, que es {3}.
Por lo tanto, 1 es la respuesta.Entrada: arr[] = {3, 2, 1, 5}
Salida: 2
Enfoque: este problema se puede resolver utilizando el enmascaramiento de bits . Siga los pasos a continuación para resolver el problema dado.
- Inicialice una variable, digamos maxXorVal = 0 , para almacenar el XOR bit a bit máximo posible de un subconjunto en arr[].
- Recorra la array arr[] para encontrar el valor de maxXorVal .
- Inicialice una variable, digamos countSubsets = 0 , para contar el número de subconjuntos con el máximo XOR bit a bit.
- Después de eso, cuente el número de subconjuntos con el valor maxXorVal .
- Devuelve countSubsets como la respuesta final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find subsets having maximum XOR
int countMaxOrSubsets(vector<int>& nums)
{
// Store the size of arr[]
long long n = nums.size();
// To store maximum possible
// bitwise XOR subset in arr[]
long long maxXorVal = 0;
// Find the maximum bitwise xor value
for (int i = 0; i < (1 << n); i++) {
long long xorVal = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
xorVal = (xorVal ^ nums[j]);
}
}
// Take maximum of each value
maxXorVal = max(maxXorVal, xorVal);
}
// Count the number
// of subsets having bitwise
// XOR value as maxXorVal
long long count = 0;
for (int i = 0; i < (1 << n); i++) {
long long val = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
val = (val ^ nums[j]);
}
}
if (val == maxXorVal) {
count++;
}
}
return count;
}
// Driver Code
int main()
{
int N = 4;
vector<int> arr = { 3, 2, 1, 5 };
// Print the answer
cout << countMaxOrSubsets(arr);
return 0;
}
Java
// Java program for above approach
import java.util.*;
public class GFG
{
// Function to find subsets having maximum XOR
static int countMaxOrSubsets(int []nums)
{
// Store the size of arr[]
long n = nums.length;
// To store maximum possible
// bitwise XOR subset in arr[]
long maxXorVal = 0;
// Find the maximum bitwise xor value
for (int i = 0; i < (1 << n); i++) {
long xorVal = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) == 0) {
xorVal = (xorVal ^ nums[j]);
}
}
// Take maximum of each value
maxXorVal = Math.max(maxXorVal, xorVal);
}
// Count the number
// of subsets having bitwise
// XOR value as maxXorVal
long count = 0;
for (int i = 0; i < (1 << n); i++) {
long val = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) == 0) {
val = (val ^ nums[j]);
}
}
if (val == maxXorVal) {
count++;
}
}
return (int)count;
}
// Driver Code
public static void main(String args[])
{
int N = 4;
int []arr = { 3, 2, 1, 5 };
// Print the answer
System.out.print(countMaxOrSubsets(arr));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program for above approach # Function to find subsets having maximum XOR def countMaxOrSubsets(nums): # Store the size of arr[] n = len(nums) # To store maximum possible # bitwise XOR subset in arr[] maxXorVal = 0 # Find the maximum bitwise xor value for i in range(0, (1 << n)): xorVal = 0 for j in range(0, n): if (i & (1 << j)): xorVal = (xorVal ^ nums[j]) # Take maximum of each value maxXorVal = max(maxXorVal, xorVal) # Count the number # of subsets having bitwise # XOR value as maxXorVal count = 0 for i in range(0, (1 << n)): val = 0 for j in range(0, n): if (i & (1 << j)): val = (val ^ nums[j]) if (val == maxXorVal): count += 1 return count # Driver Code if __name__ == "__main__": N = 4 arr = [3, 2, 1, 5] # Print the answer print(countMaxOrSubsets(arr)) # This code is contributed by rakeshsahni
C#
// C# program for above approach
using System;
public class GFG
{
// Function to find subsets having maximum XOR
static int countMaxOrSubsets(int []nums)
{
// Store the size of []arr
int n = nums.Length;
// To store maximum possible
// bitwise XOR subset in []arr
int maxXorVal = 0;
// Find the maximum bitwise xor value
for (int i = 0; i < (1 << n); i++) {
long xorVal = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) == 0) {
xorVal = (xorVal ^ nums[j]);
}
}
// Take maximum of each value
maxXorVal = (int)Math.Max(maxXorVal, xorVal);
}
// Count the number
// of subsets having bitwise
// XOR value as maxXorVal
long count = 0;
for (int i = 0; i < (1 << n); i++) {
long val = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) == 0) {
val = (val ^ nums[j]);
}
}
if (val == maxXorVal) {
count++;
}
}
return (int)count;
}
// Driver Code
public static void Main(String []args)
{
int []arr = { 3, 2, 1, 5 };
// Print the answer
Console.Write(countMaxOrSubsets(arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for above approach
// Function to find subsets having maximum XOR
function countMaxOrSubsets(nums)
{
// Store the size of arr[]
let n = nums.length;
// To store maximum possible
// bitwise XOR subset in arr[]
let maxXorVal = 0;
// Find the maximum bitwise xor value
for(let i = 0; i < (1 << n); i++)
{
let xorVal = 0;
for(let j = 0; j < n; j++)
{
if (i & (1 << j))
{
xorVal = (xorVal ^ nums[j]);
}
}
// Take maximum of each value
maxXorVal = Math.max(maxXorVal, xorVal);
}
// Count the number
// of subsets having bitwise
// XOR value as maxXorVal
let count = 0;
for(let i = 0; i < (1 << n); i++)
{
let val = 0;
for (let j = 0; j < n; j++)
{
if (i & (1 << j))
{
val = (val ^ nums[j]);
}
}
if (val == maxXorVal)
{
count++;
}
}
return count;
}
// Driver Code
let N = 4;
let arr = [ 3, 2, 1, 5 ];
// Print the answer
document.write(countMaxOrSubsets(arr));
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad de Tiempo: O(2 16 )
Espacio Auxiliar : O(1)