Kth array element after M replacements of array elements by XOR of adjacent pairs
Given an array arr[] of size N and two integers M and K, the task is to find the array element at the Kth index after performing following M operations on the given array.
In a single operation, a new array is formed whose elements have the Bitwise XOR values of the adjacent elements of the current array.
If the number of operations M or the value of K after M operations is invalid then print -1.
Examples:
Input: arr[] = {1, 4, 5, 6, 7}, M = 1, K = 2
Output: 3
Explanation:
Since M = 1, therefore, the operation has to be performed only once on the array.
The array is modified to {1^4, 4^5, 5^6, 6^7} = {5, 1, 3, 1}.
The value of the element at index K = 2 in the updated array is 3.Input: arr[] = {3, 2, 6}, M = 2, K = 1
Output: -1
Explanation:
Since M = 2, operation has be performed twice.
On performing 1st operation on the array {3, 2, 6} it is modified as {3^2, 2^6} = {1, 4}.
On performing 2nd operation on the array {1, 4}, it is modified as {1^4} = {5}.
After performing 2 operations, the size of the array is reduced to 1. This implies that the index K = 1 doesn’t exist after 2 operations.
Hence, the given input is invalid. So the output is -1.
Approach 1:
Observation:
Let the Array be [1 ,2 ,3 ,4 5,6,7,8,9,10]
After One operation : [1^2, 2^3, 3^4, 4^5, 5^6, 6^7, 7^8 , 8^9 , 9^10]
After Two operation : [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 ]
After Three operation: [ 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 ]
After Four operation : [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 ]
After Five operation : [1^5^2^6 , 2^6^3^7 , 3^7^4^8 , 4^8^5^9 , 5^9^6^10 ]
After Six operation : [1^5^3^7 , 2^6^4^8 , 3^7^5^9 , 4^8^6^10]
After Seven operation : [1^5^3^7^2^6^4^8 , 2^6^4^8^3^7^5^9 , 3^7^5^9^4^8^6^10]
After eight operation : [1^9 , 2^10]
So from Observation we can see that on ever 2^k th operation a[i]=a[i]^a[i+(2^k)] for : i<n-2^k
- Check if the given number of operations can be performed on the array or not.
- After every iteration, the length of the array is reduced by 1 which means after M operation size of array will be N-M, if the index which we need to return is greater than or equal to size of the array after M operation (ie K>=N-M) ,hence we cannot perform operation and return -1.
- If it is valid than we need to return the Kth index in updated array after M operation.
- Now we need to perform operation M times
- As we know the relation a[i]=a[i]^a[i+(2^k)] .So, Just we need to Make M as sum of number which are in form of 2^k and makes jumps to this number only.
- To do this we can iterate on the Bit that is set in M in its binary form and perform update according to Above relation to all index ( index < n-2^k) .
- Now we have to return the Kth element of the updated array .
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> |
3
Time Complexity: O(N*log(M))
Auxiliary Space: O(1)
Approach 2: The idea is to generate the array after every operation and check-in each iteration whether it is possible to do the operation further or not. If it is not possible, then return “-1”. Below are the steps:
- Check if the given number of operations can be performed on the array or not.
- After every iteration, the length of the array is reduced by 1 which means if M is greater than or equal to N, then it is not possible to perform the operation. Hence, print “-1”.
- If the value of M is valid then check if the given index K is valid or not.
- After M operations, (N – M) elements are left in the array. So, if the index value is greater than or equal to the value of (N – M), then print “-1”.
- If both M and K values are valid, then iterate a loop M times and do the following:
- In each iteration, create a temporary array temp[] which stores the values obtained by performing operation on the adjacent values of the original array.
- Traverse the array arr[] and calculate the Bitwise XOR values of adjacent elements and save these calculated values in the temporary array temp[].
- Update the current array arr[] with temp[].
- After the M iterations, return the value of arr[K], which is the required output.
Below is the implementation of the above approach:
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> |
3
Time Complexity: O(M * N)
Auxiliary Space: O(N)