Dada una array arr[] de tamaño N y dos enteros M y K , la tarea es encontrar el elemento de la array en el índice K después de realizar las siguientes operaciones M en la array dada.
En una sola operación, se forma una nueva array cuyos elementos tienen los valores Bitwise XOR de los elementos adyacentes de la array actual.
Si el número de operaciones M o el valor de K después de M operaciones no es válido, imprima -1 .
Ejemplos:
Entrada: arr[] = {1, 4, 5, 6, 7}, M = 1, K = 2
Salida: 3
Explicación:
Dado que M = 1, por lo tanto, la operación debe realizarse solo una vez en la array.
La array se modifica a {1^4, 4^5, 5^6, 6^7} = {5, 1, 3, 1}.
El valor del elemento en el índice K = 2 en la array actualizada es 3.Entrada: arr[] = {3, 2, 6}, M = 2, K = 1
Salida: -1
Explicación:
Dado que M = 2, la operación se ha realizado dos veces.
Al realizar la primera operación en la array {3, 2, 6}, se modifica como {3 ^ 2, 2 ^ 6} = {1, 4}.
Al realizar la segunda operación en la array {1, 4}, se modifica como {1^4} = {5}.
Después de realizar 2 operaciones, el tamaño de la array se reduce a 1. Esto implica que el índice K = 1 no existe después de 2 operaciones.
Por lo tanto, la entrada dada no es válida. Entonces la salida es -1.
Enfoque 1:
Observación:
Sea la array [1 ,2 ,3 ,4 5,6,7,8,9,10]
Después de una operación: [1^2, 2^3, 3^4, 4^5, 5^6, 6^7, 7^8, 8^9, 9^10]
Después de dos operaciones: [1^2^2^3, 2^3^3^4, 3^4^4^5, 4^5^5^6, ,5^6^6^7, 6^7^ 7^8 , 7^8^8^9 , 8^9 ^9^10] ==>[ 1^3, 2^4, 3^5, 4^6, 5^7 , 6^8 , 7^ 9, 8^10]
Después de tres operaciones: [1^3^2^4, 2^4^3^5, 3^5^4^6, 4^6^5^7, 5^7^6^8, 6^8^7 ^9, 7^9^8^10]
Después de cuatro operaciones: [1^3^2^4^2^4^3^5, 2^4^3^5^3^5^4^6, 3^5^4^6^4^6^5 ^7 , 4^6^5^7 ^5^7^6^8 , 5^7^6^8^6^8^7^9 , 6^8^7^9^7^9^8^10 ] ==> [ 1^5, 2^6 , 3^7 , 4^8 , 5^9 , 6^10 ]
Después de cinco operaciones: [1^5^2^6, 2^6^3^7, 3^7^4^8, 4^8^5^9, 5^9^6^10]
Después de la operación Six: [1^5^3^7, 2^6^4^8, 3^7^5^9, 4^8^6^10]
Después de la operación Siete: [1^5^3^7^2^6^4^8, 2^6^4^8^3^7^5^9, 3^7^5^9^4^8^6 ^ 10]
Después de ocho operaciones: [1^9, 2^10]
Entonces, a partir de la observación, podemos ver que en cada 2^k th operación a[i]=a[i]^a[i+(2^k)] para: i<n-2^k
- Compruebe si el número dado de operaciones se puede realizar en la array o no.
- Después de cada iteración, la longitud de la array se reduce en 1, lo que significa que después de la operación M, el tamaño de la array será NM, si el índice que necesitamos devolver es mayor o igual que el tamaño de la array después de la operación M (es decir, K> =NM ), por lo que no podemos realizar la operación y devolver -1 .
- Si es válido, necesitamos devolver el índice Kth en una array actualizada después de la operación M.
- Ahora necesitamos realizar la operación M veces
- Como sabemos la relación a[i]=a[i]^a[i+(2^k)] . Entonces, solo necesitamos hacer M como la suma de los números que están en forma de 2^k y salta a este número solamente
- Para hacer esto, podemos iterar en el bit que está configurado en M en su forma binaria y realizar la actualización de acuerdo con la relación anterior a todos los índices (índice < n-2^k).
- Ahora tenemos que devolver el elemento K-ésimo de la array actualizada.
C++
#include <iostream>
#include <vector>
using namespace std;
int m_step_xor(vector<int> a, int m, int k)
{
int n = a.size();
// the total number of element remain after m operation
// is n-m so the index that are greater than or equal to
// n-m in zero-based indexing will be not present
if (k >= n - m)
return -1;
// considering m<2^18
for (int i = 0; i < 18; i++) {
// check whether ith bit is on or not in m
if (m & (1 << i)) {
m -= (1 << i);
// as the bit is on
// Updating index that exist with the relation
// a[i]=a[i]^a[i+2^j]
for (int j = 0; j < n - (1 << i); j++) {
a[j] = a[j] ^ a[j + (1 << i)];
}
}
}
// returning the Kth index in updated array after M
// operation
return a[k];
}
int main()
{
vector<int> a = { 1, 4, 5, 6, 7 };
int m = 1, k = 2;
// Function call
int ans = m_step_xor(a, m, k);
cout << ans << "\n";
return 0;
}
// This code is contributed by swaraj jain
Java
// Java code to implement the above approach
import java.io.*;
class GFG {
static public int m_step_xor(int[] a, int m, int k)
{
int n = a.length;
// the total number of element remain after m operation
// is n-m so the index that are greater than or equal to
// n-m in zero-based indexing will be not present
if (k >= n - m)
return -1;
// considering m<2^18
for (int i = 0; i < 18; i++) {
// check whether ith bit is on or not in m
if ((m & (1 << i)) !=0) {
m -= (1 << i);
// as the bit is on
// Updating index that exist with the relation
// a[i]=a[i]^a[i+2^j]
for (int j = 0; j < n - (1 << i); j++) {
a[j] = a[j] ^ a[j + (1 << i)];
}
}
}
// returning the Kth index in updated array after M
// operation
return a[k];
}
public static void main (String[] args)
{
int[] a = { 1, 4, 5, 6, 7 };
int m = 1, k = 2;
// Function call
int ans = m_step_xor(a, m, k);
System.out.println(ans);
}
}
// This code is contributed by Shubham Singh
Python3
def m_step_xor(a, m, k): n = len(a) # the total number of element remain after m operation # is n-m so the index that are greater than or equal to # n-m in zero-based indexing will be not present if (k >= n - m): return -1 # considering m<2^18 for i in range(18): # check whether ith bit is on or not in m if (m & (1 << i)): m -= (1 << i) # as the bit is on # Updating index that exist with the relation # a[i]=a[i]^a[i+2^j] for j in range(n - (1 << i)): a[j] = a[j] ^ a[j + (1 << i)] # returning the Kth index in updated array after M # operation return a[k] a = [1, 4, 5, 6, 7] m = 1 k = 2 # Function call ans = m_step_xor(a, m, k) print(ans) # This code is contributed by Shubham Singh
C#
// C# code to implement the above approach
using System;
public class GFG{
static public int m_step_xor(int[] a, int m, int k)
{
int n = a.Length;
// the total number of element remain after m operation
// is n-m so the index that are greater than or equal to
// n-m in zero-based indexing will be not present
if (k >= n - m)
return -1;
// considering m<2^18
for (int i = 0; i < 18; i++) {
// check whether ith bit is on or not in m
if ((m & (1 << i)) !=0) {
m -= (1 << i);
// as the bit is on
// Updating index that exist with the relation
// a[i]=a[i]^a[i+2^j]
for (int j = 0; j < n - (1 << i); j++) {
a[j] = a[j] ^ a[j + (1 << i)];
}
}
}
// returning the Kth index in updated array after M
// operation
return a[k];
}
static public void Main ()
{
int[] a = { 1, 4, 5, 6, 7 };
int m = 1, k = 2;
// Function call
int ans = m_step_xor(a, m, k);
Console.WriteLine(ans);
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
function m_step_xor(a, m, k)
{
var n = a.length;
// the total number of element remain after m operation
// is n-m so the index that are greater than or equal to
// n-m in zero-based indexing will be not present
if (k >= n - m)
return -1;
// considering m<2^18
for (var i = 0; i < 18; i++) {
// check whether ith bit is on or not in m
if (m & (1 << i)) {
m -= (1 << i);
// as the bit is on
// Updating index that exist with the relation
// a[i]=a[i]^a[i+2^j]
for (var j = 0; j < n - (1 << i); j++) {
a[j] = a[j] ^ a[j + (1 << i)];
}
}
}
// returning the Kth index in updated array after M
// operation
return a[k];
}
//Driver code
var a = [ 1, 4, 5, 6, 7 ];
var m = 1, k = 2;
// Function call
var ans = m_step_xor(a, m, k);
document.write(ans + "<br>");
// This code is contributed by Shubham Singh
</script>
Producción
3
Complejidad de tiempo : O(N*log(M))
Espacio auxiliar : O(1)
Enfoque 2: la idea es generar la array después de cada operación y verificar en cada iteración si es posible continuar con la operación o no. Si no es posible, devuelva “-1” . A continuación se muestran los pasos:
- Compruebe si el número dado de operaciones se puede realizar en la array o no.
- Después de cada iteración, la longitud de la array se reduce en 1, lo que significa que si M es mayor o igual que N , entonces no es posible realizar la operación. Por lo tanto, imprima «-1» .
- Si el valor de M es válido, compruebe si el índice K dado es válido o no.
- Después de M operaciones, (N – M) elementos quedan en la array. Por lo tanto, si el valor del índice es mayor o igual que el valor de (N – M) , imprima “-1” .
- Si los valores M y K son válidos, itere un ciclo M veces y haga lo siguiente:
- En cada iteración, cree una array temporal temp[] que almacene los valores obtenidos al realizar operaciones en los valores adyacentes de la array original.
- Atraviese la array arr[] y calcule los valores Bitwise XOR de los elementos adyacentes y guarde estos valores calculados en la array temporal temp[] .
- Actualice la array actual arr[] con temp[] .
- Después de las iteraciones M , devuelva el valor de arr[K] , que es la salida requerida.
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;
// Method that returns the
// corresponding output by
// taking the given inputs.
int xor_operations(int N, int arr[],
int M, int K)
{
// If this condition is satisfied,
// value of M is invalid
if (M < 0 or M >= N)
return -1;
// Check if index K is valid
if (K < 0 or K >= N - M)
return -1;
// Loop to perform M operations
for(int p = 0; p < M; p++)
{
// Creating a temporary list
vector<int>temp;
// Traversing the array
for(int i = 0; i < N; i++)
{
// Calculate XOR values
// of adjacent elements
int value = arr[i] ^ arr[i + 1];
// Adding this value to
// the temporary list
temp.push_back(value);
// Update the original array
arr[i] = temp[i];
}
}
// Getting value at index K
int ans = arr[K];
return ans;
}
// Driver Code
int main()
{
// Number of elements
int N = 5;
// Given array arr[]
int arr[] = {1, 4, 5, 6, 7};
int M = 1, K = 2;
// Function call
cout << xor_operations(N, arr, M, K);
return 0;
}
// This code is contributed by gauravrajput1
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Method that returns the
// corresponding output by
// taking the given inputs.
static int xor_operations(int N, int arr[],
int M, int K)
{
// If this condition is satisfied,
// value of M is invalid
if (M < 0 || M >= N)
return -1;
// Check if index K is valid
if (K < 0 || K >= N - M)
return -1;
// Loop to perform M operations
for(int p = 0; p < M; p++)
{
// Creating a temporary list
Vector<Integer>temp = new Vector<Integer>();
// Traversing the array
for(int i = 0; i < N - 1; i++)
{
// Calculate XOR values
// of adjacent elements
int value = arr[i] ^ arr[i + 1];
// Adding this value to
// the temporary list
temp.add(value);
// Update the original array
arr[i] = temp.get(i);
}
}
// Getting value at index K
int ans = arr[K];
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Number of elements
int N = 5;
// Given array arr[]
int arr[] = { 1, 4, 5, 6, 7 };
int M = 1, K = 2;
// Function call
System.out.print(xor_operations(N, arr, M, K));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Method that returns the # corresponding output by # taking the given inputs. def xor_operations(N, arr, M, K): # If this condition is satisfied, # value of M is invalid if M < 0 or M >= N: return -1 # Check if index K is valid if K < 0 or K >= N-M: return -1 # Loop to perform M operations for _ in range(M): # Creating a temporary list temp = [] # Traversing the array for i in range(len(arr)-1): # Calculate XOR values # of adjacent elements value = arr[i]^arr[i + 1] # Adding this value to # the temporary list temp.append(value) # Update the original array arr = temp[:] # Getting value at index K ans = arr[K] return ans # Driver Code # Number of elements N = 5 # Given array arr[] arr = [1, 4, 5, 6, 7] M = 1 K = 2 # Function Call print(xor_operations(N, arr, M, K))
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Method that returns the
// corresponding output by
// taking the given inputs.
static int xor_operations(int N, int []arr,
int M, int K)
{
// If this condition is satisfied,
// value of M is invalid
if (M < 0 || M >= N)
return -1;
// Check if index K is valid
if (K < 0 || K >= N - M)
return -1;
// Loop to perform M operations
for(int p = 0; p < M; p++)
{
// Creating a temporary list
List<int>temp = new List<int>();
// Traversing the array
for(int i = 0; i < N - 1; i++)
{
// Calculate XOR values
// of adjacent elements
int value = arr[i] ^ arr[i + 1];
// Adding this value to
// the temporary list
temp.Add(value);
// Update the original array
arr[i] = temp[i];
}
}
// Getting value at index K
int ans = arr[K];
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Number of elements
int N = 5;
// Given array []arr
int []arr = {1, 4, 5, 6, 7};
int M = 1, K = 2;
// Function call
Console.Write(xor_operations(N, arr,
M, K));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Method that returns the
// corresponding output by
// taking the given inputs.
function xor_operations(N, arr, M, K)
{
// If this condition is satisfied,
// value of M is invalid
if (M < 0 || M >= N)
return -1;
// Check if index K is valid
if (K < 0 || K >= N - M)
return -1;
// Loop to perform M operations
for(let p = 0; p < M; p++)
{
// Creating a temporary list
let temp = [];
// Traversing the array
for(let i = 0; i < N; i++)
{
// Calculate XOR values
// of adjacent elements
let value = arr[i] ^ arr[i + 1];
// Adding this value to
// the temporary list
temp.push(value);
// Update the original array
arr[i] = temp[i];
}
}
// Getting value at index K
let ans = arr[K];
return ans;
}
// Number of elements
let N = 5;
// Given array arr[]
let arr = [1, 4, 5, 6, 7];
let M = 1, K = 2;
// Function call
document.write(xor_operations(N, arr, M, K));
</script>
Producción
3
Complejidad temporal: O(M * N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA