Given an array arr[] of size N, the task is to find all the triplets (i, j, k) such that replacing the elements of the triplets with their Bitwise XOR values, i.e. replacing arr[i], arr[j], arr[k] with (arr[i] ^ arr[j] ^ arr[k]) makes all array elements equal. If more than one solution exists, print any of them. Otherwise, print -1.
Examples:
Input: arr[] = { 4, 2, 1, 7, 2 }Â
Output: { (0, 1, 2), (2, 3, 4), (0, 1, 4) }Â
Explanation:Â
Selecting a triplet (0, 1, 2) and replacing them with arr[0] ^ arr[1] ^ arr[2] modifies arr[] to { 7, 7, 7, 7, 2 }Â
Selecting a triplet (2, 3, 4) and replacing them with arr[2] ^ arr[3] ^ arr[4] modifies arr[] to { 7, 7, 2, 2, 2 }Â
Selecting a triplet (0, 1, 4) and replacing them with arr[0] ^ arr[1] ^ arr[2] modifies arr[] to { 2, 2, 2, 2, 2 }Input: arr[] = { 1, 3, 2, 2 }Â
Output: -1
Approach: The problem can be solved based on the following observation:
x ^ X ^ Y = YÂ
X ^ Y ^ Y = XÂ
If any two elements of a triplet are equal, then replacing all the elements of the triplet with their Bitwise XOR makes all elements of the triplet equal to the third element of the triplet.Â
Â
Follow the steps below to solve the problem:
- Selecting the triplets of the form { (0, 1, 2), (2, 3, 4) …} makes the elements of the pairs { (arr[0], arr[1]), (arr[2], arr[3])… } equal.
- From the above observations, selecting the triplets of the form { (0, 1, N – 1), (2, 3, N -1), … } make all the array elements equal to the last element of the array.
- Finally, print the triplets.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
Â
// Function to find triplets such that// replacing them with their XOR make // all array elements equalvoid checkXOR(int arr[], int N){    // If N is even    if (N % 2 == 0) {             // Calculate xor of        // array elements        int xro = 0;                          // Traverse the array        for (int i = 0; i < N; i++) {                         // Update xor            xro ^= arr[i];        }Â
        // If xor is not equal to 0        if (xro != 0) {            cout << -1 << endl;            return;        }                          // Selecting the triplets such that        // elements of the pairs (arr[0], arr[1]),        // (arr[2], arr[3])... can be made equal         for (int i = 0; i < N - 3; i += 2) {            cout << i << " " << i + 1                  << " " << i + 2 << endl;        }Â
        // Selecting the triplets such that        // all array elements can be made        // equal to arr[N - 1]        for (int i = 0; i < N - 3; i += 2) {            cout << i << " " << i + 1                 << " " << N - 1 << endl;        }    }    else {Â
        // Selecting the triplets such that        // elements of the pairs (arr[0], arr[1]),        // (arr[2], arr[3])... can be made equal        for (int i = 0; i < N - 2; i += 2) {            cout << i << " " << i + 1 << " "                 << i + 2 << endl;        }                                   // Selecting the triplets such that        // all array elements can be made        // equal to arr[N - 1]        for (int i = 0; i < N - 2; i += 2) {            cout << i << " " << i + 1                    << " " << N - 1 << endl;        }    }}Â
Â
// Driver Codeint main(){    // Given array    int arr[] = { 4, 2, 1, 7, 2 };Â
    // Size of array    int N = sizeof(arr) / sizeof(arr[0]);Â
    // Function call    checkXOR(arr, N);} |
Java
// Java program to implement // the above approach import java.util.*;  class GFG{      // Function to find triplets such that// replacing them with their XOR make // all array elements equalstatic void checkXOR(int arr[], int N){         // If N is even    if (N % 2 == 0)     {                 // Calculate xor of        // array elements        int xro = 0;                 // Traverse the array        for(int i = 0; i < N; i++)         {                         // Update xor            xro ^= arr[i];        }          // If xor is not equal to 0        if (xro != 0)         {            System.out.println(-1);            return;        }                 // Selecting the triplets such that        // elements of the pairs (arr[0], arr[1]),        // (arr[2], arr[3])... can be made equal         for(int i = 0; i < N - 3; i += 2)        {            System.out.println(i + " " + (i + 1) +                                    " " + (i + 2));        }          // Selecting the triplets such that        // all array elements can be made        // equal to arr[N - 1]        for(int i = 0; i < N - 3; i += 2)         {            System.out.println(i + " " + (i + 1) +                                   " " + (N - 1));        }    }    else    {                 // Selecting the triplets such that        // elements of the pairs (arr[0], arr[1]),        // (arr[2], arr[3])... can be made equal        for(int i = 0; i < N - 2; i += 2)         {            System.out.println(i + " " + (i + 1) +                                    " " + (i + 2));        }                 // Selecting the triplets such that        // all array elements can be made        // equal to arr[N - 1]        for(int i = 0; i < N - 2; i += 2)        {            System.out.println(i + " " + (i + 1) +                                   " " + (N - 1));        }    }}  // Driver codepublic static void main(String[] args){         // Given array    int arr[] = { 4, 2, 1, 7, 2 };      // Size of array    int N = arr.length;      // Function call    checkXOR(arr, N);}}Â
// This code is contributed by susmitakundugoaldanga |
Python3
# Python program to implement# the above approachÂ
# Function to find triplets such that# replacing them with their XOR make# all array elements equaldef checkXOR(arr, N):       # If N is even    if (N % 2 == 0):Â
        # Calculate xor of        # array elements        xro = 0;Â
        # Traverse the array        for i in range(N):                       # Update xor            xro ^= arr[i];Â
        # If xor is not equal to 0        if (xro != 0):            print(-1);            return;Â
        # Selecting the triplets such that        # elements of the pairs (arr[0], arr[1]),        # (arr[2], arr[3])... can be made equal        for i in range(0, N - 3, 2):            print(i, " ", (i + 1), " ", (i + 2), end=" ");Â
        # Selecting the triplets such that        # all array elements can be made        # equal to arr[N - 1]        for i in range(0, N - 3, 2):            print(i, " ", (i + 1), " ", (N - 1), end=" ");Â
    else:Â
        # Selecting the triplets such that        # elements of the pairs (arr[0], arr[1]),        # (arr[2], arr[3])... can be made equal        for i in range(0, N - 2, 2):            print(i, " ", (i + 1), " ", (i + 2));Â
        # Selecting the triplets such that        # all array elements can be made        # equal to arr[N - 1]        for i in range(0, N - 2, 2):            print(i, " ", (i + 1), " ", (N - 1));Â
Â
# Driver codeif __name__ == '__main__':       # Given array    arr = [4, 2, 1, 7, 2];Â
    # Size of array    N = len(arr);Â
    # Function call    checkXOR(arr, N);Â
# This code is contributed by 29AjayKumar |
C#
// C# program to implement// the above approach using System;   class GFG{       // Function to find triplets such that// replacing them with their XOR make // all array elements equalstatic void checkXOR(int[] arr, int N){         // If N is even    if (N % 2 == 0)     {                 // Calculate xor of        // array elements        int xro = 0;                  // Traverse the array        for(int i = 0; i < N; i++)         {                         // Update xor            xro ^= arr[i];        }           // If xor is not equal to 0        if (xro != 0)         {            Console.WriteLine(-1);            return;        }                  // Selecting the triplets such that        // elements of the pairs (arr[0], arr[1]),        // (arr[2], arr[3])... can be made equal         for(int i = 0; i < N - 3; i += 2)        {            Console.WriteLine(i + " " + (i + 1) +                                   " " + (i + 2));        }           // Selecting the triplets such that        // all array elements can be made        // equal to arr[N - 1]        for(int i = 0; i < N - 3; i += 2)         {            Console.WriteLine(i + " " + (i + 1) +                                  " " + (N - 1));        }    }    else    {                  // Selecting the triplets such that        // elements of the pairs (arr[0], arr[1]),        // (arr[2], arr[3])... can be made equal        for(int i = 0; i < N - 2; i += 2)         {            Console.WriteLine(i + " " + (i + 1) +                                   " " + (i + 2));        }                  // Selecting the triplets such that        // all array elements can be made        // equal to arr[N - 1]        for(int i = 0; i < N - 2; i += 2)        {            Console.WriteLine(i + " " + (i + 1) +                                  " " + (N - 1));        }    }}   // Driver codepublic static void Main(){         // Given array    int[] arr = { 4, 2, 1, 7, 2 };       // Size of array    int N = arr.Length;       // Function call    checkXOR(arr, N);}}Â
// This code is contributed by sanjoy_62 |
Javascript
<script>Â
// Javascript program to implement// the above approachÂ
Â
// Function to find triplets such that// replacing them with their XOR make // all array elements equalfunction checkXOR(arr, N){    // If N is even    if (N % 2 == 0) {             // Calculate xor of        // array elements        let xro = 0;                          // Traverse the array        for (let i = 0; i < N; i++) {                         // Update xor            xro ^= arr[i];        }Â
        // If xor is not equal to 0        if (xro != 0) {            document.write(-1 + "<br>");            return;        }                          // Selecting the triplets such that        // elements of the pairs (arr[0], arr[1]),        // (arr[2], arr[3])... can be made equal         for (let i = 0; i < N - 3; i += 2) {            document.write(i + " " + (i + 1)                  + " " + (i + 2) + "<br>");        }Â
        // Selecting the triplets such that        // all array elements can be made        // equal to arr[N - 1]        for (let i = 0; i < N - 3; i += 2) {            document.write(i + " " + (i + 1)                 + " " + (N - 1) + "<br>");        }    }    else {Â
        // Selecting the triplets such that        // elements of the pairs (arr[0], arr[1]),        // (arr[2], arr[3])... can be made equal        for (let i = 0; i < N - 2; i += 2) {            document.write(i + " " + (i + 1) + " "                 + (i + 2) + "<br>");        }                                   // Selecting the triplets such that        // all array elements can be made        // equal to arr[N - 1]        for (let i = 0; i < N - 2; i += 2) {            document.write(i + " " + (i + 1)                    + " " + (N - 1) + "<br>");        }    }}Â
Â
// Driver Code    // Given array    let arr = [ 4, 2, 1, 7, 2 ];Â
    // Size of array    let N = arr.length;Â
    // Function call    checkXOR(arr, N);Â
</script> |
Â
Â
0 1 2 2 3 4 0 1 4 2 3 4
Â
Time Complexity: O(N)
Auxiliary Space: O(1)
Â
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Read More on that Topic: geeksforgeeks.org/make-all-array-elements-equal-by-replacing-triplets-with-their-bitwise-xor/ […]
… [Trackback]
[…] Read More on that Topic: geeksforgeeks.org/make-all-array-elements-equal-by-replacing-triplets-with-their-bitwise-xor/ […]
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/make-all-array-elements-equal-by-replacing-triplets-with-their-bitwise-xor/ […]
… [Trackback]
[…] Information to that Topic: geeksforgeeks.org/make-all-array-elements-equal-by-replacing-triplets-with-their-bitwise-xor/ […]