Dada una array arr[] que consta de N enteros positivos y un entero positivo K , la tarea es contar el XOR bit a bit mínimo de los elementos de la array con 1 requerido de modo que la suma de la array sea al menos K .
Ejemplos:
Entrada: arr[] = {0, 1, 1, 0, 1}, K = 4
Salida: 1
Explicación: realizar XOR bit a bit de arr[0] y 1 modifica arr[] a {1, 1, 1, 0, 1}. Ahora, la suma de la array = 1 + 1 + 1 + 0 + 1 = 4(= K).Entrada: arr[] = {14, 0, 1, 0}, K = 20
Salida: -1
Enfoque: El problema dado se puede resolver utilizando el hecho de que Bitwise XOR de 1 con un elemento par aumenta el elemento en 1 .
Siga los pasos a continuación para resolver el problema:
- Encuentre la suma de la array dada arr[] y guárdela en una variable, digamos S .
- Cuente el número de elementos pares en la array y guárdelo en una variable, digamos E .
- Si S es mayor o igual que K , imprima 0 .
- De lo contrario, si el valor de S + E es menor que K , imprima -1 .
- De lo contrario, imprima el valor de (K – S) ya que se requiere el número mínimo de Bitwise XOR de un elemento de array con 1 .
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; // Function to find minimum number // of Bitwise XOR of array elements // with 1 required to make sum of // the array at least K int minStepK(int arr[], int N, int K) { // Stores the count of // even array elements int E = 0; // Stores sum of the array int S = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Increment sum S += arr[i]; // If array element is even if (arr[i] % 2 == 0) // Increase count of even E += 1; } // If S is at least K if (S >= K) return 0; // If S + E is less than K else if (S + E < K) return -1; // Otherwise, moves = K - S else return K - S; } // Driver Code int main() { int arr[] = { 0, 1, 1, 0, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 4; cout << minStepK(arr, N, K); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find minimum number // of Bitwise XOR of array elements // with 1 required to make sum of // the array at least K static int minStepK(int arr[], int N, int K) { // Stores the count of // even array elements int E = 0; // Stores sum of the array int S = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // Increment sum S += arr[i]; // If array element is even if (arr[i] % 2 == 0) // Increase count of even E += 1; } // If S is at least K if (S >= K) return 0; // If S + E is less than K else if (S + E < K) return -1; // Otherwise, moves = K - S else return K - S; } // Driver code public static void main(String[] args) { int arr[] = { 0, 1, 1, 0, 1 }; int N = arr.length; int K = 4; System.out.println(minStepK(arr, N, K)); } } // This code is contributed by offbeat
Python3
# Python 3 program for the above approach # Function to find minimum number # of Bitwise XOR of array elements # with 1 required to make sum of # the array at least K def minStepK(arr, N, K): # Stores the count of # even array elements E = 0 # Stores sum of the array S = 0 # Traverse the array arr[] for i in range(N): # Increment sum S += arr[i] # If array element is even if (arr[i] % 2 == 0): # Increase count of even E += 1 # If S is at least K if (S >= K): return 0 # If S + E is less than K elif (S + E < K): return -1 # Otherwise, moves = K - S else: return K - S # Driver Code if __name__ == "__main__": arr = [0, 1, 1, 0, 1] N = len(arr) K = 4 print(minStepK(arr, N, K)) # This code is contributed by ukasp.
C#
// C# program for the above approach using System; class GFG { // Function to find minimum number // of Bitwise XOR of array elements // with 1 required to make sum of // the array at least K static int minStepK(int[] arr, int N, int K) { // Stores the count of // even array elements int E = 0; // Stores sum of the array int S = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // Increment sum S += arr[i]; // If array element is even if (arr[i] % 2 == 0) // Increase count of even E += 1; } // If S is at least K if (S >= K) return 0; // If S + E is less than K else if (S + E < K) return -1; // Otherwise, moves = K - S else return K - S; } // Driver Code public static void Main() { int[] arr= { 0, 1, 1, 0, 1 }; int N = arr.Length; int K = 4; Console.WriteLine(minStepK(arr, N, K)); } } // This code is contributed by sanjoy_62.
Javascript
<script> // JavaScript program for the above approach // Function to find minimum number // of Bitwise XOR of array elements // with 1 required to make sum of // the array at least K function minStepK(arr, N, K) { // Stores the count of // even array elements var E = 0; // Stores sum of the array var S = 0; // Traverse the array arr[] for(var i = 0; i < N; i++) { // Increment sum S += arr[i]; // If array element is even if (arr[i] % 2 === 0) // Increase count of even E += 1; } // If S is at least K if (S >= K) return 0; // If S + E is less than K else if (S + E < K) return -1; // Otherwise, moves = K - S else return K - S; } // Driver Code var arr = [ 0, 1, 1, 0, 1 ]; var N = arr.length; var K = 4; document.write(minStepK(arr, N, K)); // This code is contributed by rdtank </script>
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA