Dada una array arr[] de tamaño N , la tarea es contar el número de arrays que tienen al menos K elementos mayores que el XOR de todos los elementos de la array, generados al realizar las siguientes operaciones X veces.
- Seleccione el primer o el último elemento de la array dada.
- Incremente el elemento seleccionado en 1 o elimine el elemento seleccionado.
Ejemplos:
Entrada: arr[] = {10, 2, 10, 5}, X = 3, K = 3
Salida: 1
Explicación:
XOR de la array dada = 7. La única array posible que satisface la condición es {10, 2, 10 , 8}, obtenido al incrementar tres veces el último elemento de la array.Entrada: arr[] = {3, 3, 4}, X = 3, K = 2
Salida: 3
Enfoque: la idea es utilizar el enfoque de retroceso para probar recursivamente todos los movimientos posibles e incrementar el conteo cuando se obtiene la array requerida. Los movimientos posibles son:
- Inicialice una variable, digamos xorValue , para calcular el XOR de la array original .
- Inicialice una variable, digamos count , para almacenar el recuento final de las arrays requeridas.
- Intente recursivamente las siguientes cuatro posibilidades e incremente el conteo cuando se obtenga la array requerida:
- Elimina el primer elemento de la array.
- Elimina el último elemento de la array.
- Incrementa el primer elemento de la array en uno.
- Incrementa el último elemento de la array en uno.
- Imprime el conteo final como la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the final answer
int ans = 0;
// Utility function to count arrays
// having at least K elements exceeding
// XOR of all given array elements
void countArraysUtil(vector<int>& arr,
int X, int K,
int xorVal)
{
// If no operations are left
if (X == 0) {
// Stores the count of
// possible arrays
int cnt = 0;
// Count array elements are
// greater than XOR
for (int i = 0; i < arr.size(); i++) {
if (arr[i] > xorVal)
cnt++;
}
if (cnt >= K)
ans++;
return;
}
// Stores first element
int temp = arr[0];
// Delete first element
arr.erase(arr.begin());
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Insert first element into vector
arr.insert(arr.begin(), temp);
// Stores the last element
temp = arr.back();
// Remove last element from vector
arr.pop_back();
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Push last element into vector
arr.push_back(temp);
// Increment first element
arr[0]++;
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Decrement first element
arr[0]--;
// Increment last element
arr[arr.size() - 1]++;
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Decrement last element
arr[arr.size() - 1]--;
}
// Function to find the count of
// arrays having atleast K elements
// greater than XOR of array
void countArrays(vector<int>& arr,
int X, int K)
{
// Stores the XOR value
// of original array
int xorVal = 0;
// Traverse the vector
for (int i = 0; i < arr.size(); i++)
xorVal = xorVal ^ arr[i];
countArraysUtil(arr, X, K, xorVal);
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
// Given vector
vector<int> arr = { 10, 2, 10, 5 };
// Given value of X & K
int X = 3, K = 3;
countArrays(arr, X, K);
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
class GFG{
// Stores the final answer
static int ans = 0;
// Utility function to count arrays
// having at least K elements exceeding
// XOR of all given array elements
public static void countArraysUtil(ArrayList<Integer> arr,
int X, int K,
int xorVal)
{
// If no operations are left
if (X == 0) {
// Stores the count of
// possible arrays
int cnt = 0;
// Count array elements are
// greater than XOR
for (int i = 0; i < arr.size(); i++) {
if (arr.get(i) > xorVal)
cnt++;
}
if (cnt >= K)
ans++;
return;
}
// Stores first element
int temp = arr.get(0);
// Delete first element
arr.remove(0);
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Insert first element into vector
arr.add(0, temp);
// Stores the last element
temp = arr.get(arr.size() - 1);
// Remove last element from vector
arr.remove(arr.size() - 1);
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Push last element into vector
arr.add(temp);
// Increment first element
arr.set(0, arr.get(0) + 1);
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Decrement first element
arr.set(0, arr.get(0) - 1);
// Increment last element
arr.set(arr.size() - 1, arr.get(arr.size() - 1) + 1);
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Decrement last element
arr.set(arr.size() - 1, arr.get(arr.size() - 1) - 1);
}
// Function to find the count of
// arrays having atleast K elements
// greater than XOR of array
public static void countArrays(ArrayList<Integer> arr,
int X, int K)
{
// Stores the XOR value
// of original array
int xorVal = 0;
// Traverse the vector
for (int i = 0; i < arr.size(); i++)
xorVal = xorVal ^ arr.get(i);
countArraysUtil(arr, X, K, xorVal);
// Print the answer
System.out.println(ans);
}
// Driver Code
public static void main(String arg[])
{
// Given vector
int[] input = {10, 2, 10, 5};
// Convert the input as ArrayList
ArrayList<Integer> arr = new ArrayList<Integer>();
for(int i : input){
arr.add(i);
}
// Given value of X & K
int X = 3, K = 3;
countArrays(arr, X, K);
}
}
// This code is contributed by gfgking.
Python3
# Python program for the above approach # Stores the final answer ans = 0 # Utility function to count arrays # having at least K elements exceeding # XOR of all given array elements def countArraysUtil( arr, X, K, xorVal): global ans # If no operations are left if (X == 0): # Stores the count of # possible arrays cnt = 0 # Count array elements are # greater than XOR for i in range(len(arr)): if (arr[i] > xorVal): cnt += 1 if (cnt >= K): ans += 1 return # Stores first element temp = arr[0] # Delete first element arr.pop(0) # Recursive call countArraysUtil(arr, X - 1, K, xorVal) # Insert first element into vector arr.insert(0, temp) # Stores the last element temp = arr[-1] # Remove last element from vector arr.pop() # Recursive call countArraysUtil(arr, X - 1, K, xorVal) # Push last element into vector arr.append(temp) # Increment first element arr[0] += 1 # Recursive call countArraysUtil(arr, X - 1,K, xorVal) # Decrement first element arr[0] -= 1 # Increment last element arr[len(arr) - 1] += 1 # Recursive call countArraysUtil(arr, X - 1, K, xorVal) # Decrement last element arr[len(arr) - 1] -= 1 # Function to find the count of # arrays having atleast K elements # greater than XOR of array def countArrays(arr, X, K): # Stores the XOR value # of original array xorVal = 0 # Traverse the vector for i in range(len(arr)): xorVal = xorVal ^ arr[i] countArraysUtil(arr, X, K, xorVal) # Print the answer print(ans) # Driver Code # Given vector arr = [ 10, 2, 10, 5 ] # Given value of X & K X = 3 K = 3 countArrays(arr, X, K) # This code is contributed by rohitsingh07052.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Stores the final answer
static int ans = 0;
// Utility function to count arrays
// having at least K elements exceeding
// XOR of all given array elements
static void countArraysUtil(List<int> arr, int X, int K,
int xorVal)
{
// If no operations are left
if (X == 0) {
// Stores the count of
// possible arrays
int cnt = 0;
// Count array elements are
// greater than XOR
for (int i = 0; i < arr.Count; i++) {
if (arr[i] > xorVal)
cnt++;
}
if (cnt >= K)
ans++;
return;
}
// Stores first element
int temp = arr[0];
// Delete first element
arr.RemoveAt(0);
// Recursive call
countArraysUtil(arr, X - 1, K, xorVal);
// Insert first element into vector
arr.Insert(0, temp);
// Stores the last element
temp = arr[arr.Count - 1];
// Remove last element from vector
arr.RemoveAt(arr.Count - 1);
// Recursive call
countArraysUtil(arr, X - 1, K, xorVal);
// Push last element into vector
arr.Add(temp);
// Increment first element
arr[0]++;
// Recursive call
countArraysUtil(arr, X - 1, K, xorVal);
// Decrement first element
arr[0]--;
// Increment last element
arr[arr.Count - 1]++;
// Recursive call
countArraysUtil(arr, X - 1, K, xorVal);
// Decrement last element
arr[arr.Count - 1]--;
}
// Function to find the count of
// arrays having atleast K elements
// greater than XOR of array
static void countArrays(List<int> arr, int X, int K)
{
// Stores the XOR value
// of original array
int xorVal = 0;
// Traverse the vector
for (int i = 0; i < arr.Count; i++)
xorVal = xorVal ^ arr[i];
countArraysUtil(arr, X, K, xorVal);
// Print the answer
Console.Write(ans);
}
// Driver Code
public static void Main()
{
// Given vector
List<int> arr = new List<int>() { 10, 2, 10, 5 };
// Given value of X & K
int X = 3, K = 3;
countArrays(arr, X, K);
}
}
// This code is contributed by chitranayal.
Javascript
<script>
// JavaScript program for the above approach
// Stores the final answer
let ans = 0;
// Utility function to count arrays
// having at least K elements exceeding
// XOR of all given array elements
function countArraysUtil(arr,X,K,xorVal)
{
// If no operations are left
if (X == 0) {
// Stores the count of
// possible arrays
let cnt = 0;
// Count array elements are
// greater than XOR
for (let i = 0; i < arr.length; i++) {
if (arr[i] > xorVal)
cnt++;
}
if (cnt >= K)
ans++;
return;
}
// Stores first element
let temp = arr[0];
// Delete first element
arr.shift();
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Insert first element into vector
arr.unshift(temp);
// Stores the last element
temp = arr[arr.length-1];
// Remove last element from vector
arr.pop();
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Push last element into vector
arr.push(temp);
// Increment first element
arr[0]++;
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Decrement first element
arr[0]--;
// Increment last element
arr[arr.length - 1]++;
// Recursive call
countArraysUtil(arr, X - 1,
K, xorVal);
// Decrement last element
arr[arr.length - 1]--;
}
// Function to find the count of
// arrays having atleast K elements
// greater than XOR of array
function countArrays(arr,X,K)
{
// Stores the XOR value
// of original array
let xorVal = 0;
// Traverse the vector
for (let i = 0; i < arr.length; i++)
xorVal = xorVal ^ arr[i];
countArraysUtil(arr, X, K, xorVal);
// Print the answer
document.write(ans);
}
// Driver Code
let arr=[10, 2, 10, 5];
// Given value of X & K
let X = 3, K = 3;
countArrays(arr, X, K);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1
Complejidad de Tiempo: O(4 K * N)
Espacio Auxiliar: O(1)