Cuente arrays que tengan al menos K elementos que excedan XOR de todos los elementos de array dados por X operaciones dadas

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:

 

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) 

Publicación traducida automáticamente

Artículo escrito por knockpit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *