Data Modelling & AI Data Structure & Algorithm

Quadruplet pair with XOR zero in the given Array

23 June 2025

0

Given an array arr[] of N integers such that any two adjacent elements in the array differ at only one position in their binary representation. The task is to find whether there exists a quadruple (arr[i], arr[j], arr[k], arr[l]) such that arr[i] ^ arr[j] ^ arr[k] ^ arr[l] = 0. Here ^ denotes the bitwise xor operation and 1 ? i < j < k < l ? N.
Examples:

Input: arr[] = {1, 3, 7, 3}
Output: No
1 ^ 3 ^ 7 ^ 3 = 6
Input: arr[] = {1, 0, 2, 3, 7}
Output: Yes
1 ^ 0 ^ 2 ^ 3 = 0

Naive approach: Check for all possible quadruples whether their xor is zero or not. But the time complexity of such a solution would be N⁴, for all N.
Time Complexity:

Efficient Approach (O(N⁴), for N &leq; 130): We can Say that for array length more than or equal to 130 we can have at least 65 adjacent pairs each denoting xor of two elements. Here it is given that all adjacent elements differ at only one position in their binary form thus there would result in only one set bit. Since we have only 64 possible positions, we can say that at least two pairs will have the same xor. Thus, xor of these 4 integers will be 0. For N < 130 we can use the naive approach.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 130;
 
// Function that returns true if the array
// contains a valid quadruplet pair
bool validQuadruple(int arr[], int n)
{
 
    // We can always find a valid quadruplet pair
    // for array size greater than MAX
    if (n >= MAX)
        return true;
 
    // For smaller size arrays, perform brute force
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            for (int k = j + 1; k < n; k++)
                for (int l = k + 1; l < n; l++) {
                    if ((arr[i] ^ arr[j] ^ arr[k] ^ arr[l]) == 0) {
                        return true;
                    }
                }
    return false;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 0, 2, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    if (validQuadruple(arr, n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
 
static int MAX = 130; 
 
// Function that returns true if the array 
// contains a valid quadruplet pair 
static boolean validQuadruple(int arr[], int n) 
{ 
 
    // We can always find a valid quadruplet pair 
    // for array size greater than MAX 
    if (n >= MAX) 
        return true; 
 
    // For smaller size arrays, perform brute force 
    for (int i = 0; i < n; i++) 
        for (int j = i + 1; j < n; j++) 
            for (int k = j + 1; k < n; k++) 
                for (int l = k + 1; l < n; l++)
                { 
                    if ((arr[i] ^ arr[j] ^ 
                         arr[k] ^ arr[l]) == 0) 
                    { 
                        return true; 
                    } 
                } 
    return false; 
} 
 
// Driver code
public static void main (String[] args) 
              throws java.lang.Exception
{
    int arr[] = { 1, 0, 2, 3, 7 }; 
    int n = arr.length;
 
    if (validQuadruple(arr, n)) 
        System.out.println("Yes"); 
    else
        System.out.println("No"); 
}
}
 
// This code is contributed by nidhiva

Python3

# Python3 implementation of the approach
MAX = 130
 
# Function that returns true if the array
# contains a valid quadruplet pair
def validQuadruple(arr, n):
 
    # We can always find a valid quadruplet pair
    # for array size greater than MAX
    if (n >= MAX):
        return True
 
    # For smaller size arrays, 
    # perform brute force
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                for l in range(k + 1, n):
                    if ((arr[i] ^ arr[j] ^ 
                         arr[k] ^ arr[l]) == 0):
                        return True
 
    return False
 
# Driver code
arr = [1, 0, 2, 3, 7]
n = len(arr)
 
if (validQuadruple(arr, n)):
    print("Yes")
else:
    print("No")
 
#  This code is contributed
# by Mohit Kumar

C#

// C# implementation of the approach
using System;
     
class GFG
{
 
static int MAX = 130; 
 
// Function that returns true if the array 
// contains a valid quadruplet pair 
static Boolean validQuadruple(int []arr, int n) 
{ 
 
    // We can always find a valid quadruplet pair 
    // for array size greater than MAX 
    if (n >= MAX) 
        return true; 
 
    // For smaller size arrays, perform brute force 
    for (int i = 0; i < n; i++) 
        for (int j = i + 1; j < n; j++) 
            for (int k = j + 1; k < n; k++) 
                for (int l = k + 1; l < n; l++)
                { 
                    if ((arr[i] ^ arr[j] ^ 
                         arr[k] ^ arr[l]) == 0) 
                    { 
                        return true; 
                    } 
                } 
    return false; 
} 
 
// Driver code
public static void Main (String[] args)
{
    int []arr = { 1, 0, 2, 3, 7 }; 
    int n = arr.Length;
 
    if (validQuadruple(arr, n)) 
        Console.WriteLine("Yes"); 
    else
        Console.WriteLine("No"); 
}
}
 
// This code is contributed by 29AjayKumar

PHP

<?php
// PHP implementation of the approach 
const MAX = 130; 
 
// Function that returns true if the array 
// contains a valid quadruplet pair 
function validQuadruple($arr, $n) 
{ 
 
    // We can always find a valid quadruplet pair 
    // for array size greater than MAX 
    if ($n >= MAX) 
        return true; 
 
    // For smaller size arrays,
    // perform brute force 
    for ($i = 0; $i < $n; $i++) 
        for ($j = $i + 1; $j < $n; $j++) 
            for ($k = $j + 1; $k < $n; $k++) 
                for ($l = $k + 1; $l < $n; $l++) 
                { 
                    if (($arr[$i] ^ $arr[$j] ^ 
                         $arr[$k] ^ $arr[$l]) == 0) 
                    { 
                        return true; 
                    } 
                } 
    return false; 
} 
 
// Driver code 
$arr = array(1, 0, 2, 3, 7); 
$n = count($arr); 
 
if (validQuadruple($arr, $n)) 
    echo ("Yes"); 
else
    echo ("No"); 
 
// This code is contributed by Naman_Garg
?>

Javascript

<script>
 
// Javascript implementation 
// of the approach
 
const MAX = 130;
 
// Function that returns true if the array
// contains a valid quadruplet pair
function validQuadruple(arr, n)
{
 
    // We can always find a valid quadruplet pair
    // for array size greater than MAX
    if (n >= MAX)
        return true;
 
    // For smaller size arrays, perform brute force
    for (let i = 0; i < n; i++)
        for (let j = i + 1; j < n; j++)
            for (let k = j + 1; k < n; k++)
                for (let l = k + 1; l < n; l++) {
                    if ((arr[i] ^ arr[j] ^ arr[k] ^ 
                         arr[l]) == 0) {
                        return true;
                    }
                }
    return false;
}
 
// Driver code
    let arr = [ 1, 0, 2, 3, 7 ];
    let n = arr.length;
 
    if (validQuadruple(arr, n))
        document.write("Yes");
    else
        document.write("No");
 
</script>

Output:

Yes

Time Complexity:

Auxiliary Space: O(1)
Another Efficient Approach (O(N²log N), for N &leq; 130):
Compute Xor of all pairs and hash it. ie, store indexes i and j in a list and Hash it in form <xor, list>. If the same xor is found again for different i and j, then we have a Quadruplet pair.
Below is the implementation of the above approach :

C++

//C++ implementation of the approach
#include <bits/stdc++.h> 
using namespace std; 
 
bool check(int arr[], int n) 
{ 
    if (n < 4) 
        return false; 
    if (n >= 130) 
        return true; 
     
    map<int, vector<int> > map; 
 
    for (int i = 0; i < n - 1; i++) { 
        for (int j = i + 1; j < n; j++) { 
            int k = arr[i] ^ arr[j]; 
            if (map.find(k) == map.end()) 
                map[k] = { i, j }; 
            else { 
                vector<int> data = map[k]; 
                if (find(data.begin(), data.end(), i) == data.end() && 
                    find(data.begin(), data.end(), j) == data.end()) { 
                    data.push_back(i); 
                    data.push_back(j); 
                    if (data.size() >= 4) 
                        return true; 
                    map[k] = data; 
                } 
            } 
        } 
    } 
    return false; 
} 
 
// Driver code 
int main() 
{ 
    int arr[] = { 1, 0, 2, 3, 7 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    if (check(arr, n)) 
        cout << "Yes"; 
    else
        cout << "No"; 
    return 0; 
}

Java

// Java implementation of the approach
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
 
public class QuadrapuleXor {
 
    static boolean check(int arr[])
    {
        int n = arr.length;
         
        if(n < 4)
            return false;
        if(n >=130)
            return true;
             
        Map<Integer,List<Integer>> map = new HashMap<>();
         
        for(int i=0;i<n-1;i++)
        {    
            for(int j=i+1;j<n;j++)
            {
                int k = arr[i] ^ arr[j];
                if(!map.containsKey(k))
                    map.put(k,new LinkedList<>());
                 
                List<Integer> data = map.get(k);
                if(!data.contains(i) && !data.contains(j))
                {
                    data.add(i);
                    data.add(j);
                    if(data.size()>=4)
                        return true;
                    map.put(k, data);
                }
            }    
        }
        return false;
    }
     
    // Driver code
    public static void main (String[] args) 
                  throws java.lang.Exception
    {
        int arr[] = { 1, 0, 2, 3, 7 }; 
      
        if (check(arr)) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    }
}
 
//This code contributed by Pramod Hosahalli

Python3

# Python3 implementation of the approach
def check(arr):
 
    n = len(arr)
     
    # if n is less than 4, no quadruplet
    # can be possibly formed
    if(n < 4):
        return False
    # if n >= 130, there is guaranteed
    # to be a quadruplet
    if(n >=130):
        return True
              
    # initializing a dictionary
    map = dict()
     
    # building the map
    for i in range(n - 1):
        for j in range(i + 1, n):
            k = arr[i] ^ arr[j]
            if k not in map:
                map[k] = []
            data = map[k]
            if i not in data and j not in data:
                data.append(i)
                data.append(j)
                 
                # if a  quadruplet has been found
                # return true
                if (len(data) >= 4):
                    return True
                map[k] = data
 
    return False
 
# Driver code
arr=[ 1, 0, 2, 3, 7 ]
if (check(arr)):
    print("Yes")
else:
    print("No")
 
 
# This code is contributed by phasing17

Javascript

<script>
// Javascript implementation of the approach
 
function check(arr)
{
    let n = arr.length;
          
        if(n < 4)
            return false;
        if(n >=130)
            return true;
              
        let map = new Map();
          
        for(let i=0;i<n-1;i++)
        {   
            for(let j=i+1;j<n;j++)
            {
                let k = arr[i] ^ arr[j];
                if(!map.has(k))
                    map.set(k,[]);
                  
                let data = map.get(k);
                if(!data.includes(i) && !data.includes(j))
                {
                    data.push(i);
                    data.push(j);
                    if(data.length>=4)
                        return true;
                    map.set(k, data);
                }
            }   
        }
        return false;
}
 
// Driver code
let arr=[ 1, 0, 2, 3, 7 ];
if (check(arr))
    document.write("Yes<br>");
else
    document.write("No<br>");
 
 
// This code is contributed by rag2127
</script>

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
public class QuadrapuleXor {
 
  // Function to check whether a quadruplet with XOR 0
  // exists in the given array
  static bool check(int[] arr)
  {
    int n = arr.Length;
 
    if (n < 4)
      return false;
    if (n >= 130)
      return true;
 
    Dictionary<int, List<int> > map
      = new Dictionary<int, List<int> >();
 
    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        int k = arr[i] ^ arr[j];
        if (!map.ContainsKey(k))
          map[k] = new List<int>();
 
        List<int> data = map[k];
        if (!data.Contains(i)
            && !data.Contains(j)) {
          data.Add(i);
          data.Add(j);
          if (data.Count >= 4)
            return true;
          map[k] = data;
        }
      }
    }
    return false;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    int[] arr = { 1, 0, 2, 3, 7 };
 
    // Function Call
    if (check(arr))
      Console.WriteLine("Yes");
    else
      Console.WriteLine("No");
  }
}
 
// This code is contributed by phasing17

Output:

Yes

Time Complexity:

Auxiliary Space: O(N²)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

1 COMMENT

gates of olympus super scatter 1 July 2026 At 3:33 pm

… [Trackback]

[…] Read More Info here on that Topic: geeksforgeeks.org/quadruplet-pair-with-xor-zero-in-the-given-array/ […]

Log in to leave a comment

Quadruplet pair with XOR zero in the given Array

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

Javascript

C#

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

1 COMMENT

LEAVE A REPLY Cancel reply

Most Popular

Samsung’s Galaxy S27 Pro could finally fix what was wrong with the Plus

Your AI agent just got a lot more accessible with OpenClaw’s new Android app

We need to talk about this. [Video]

This is so much phone for the money. [Video]

EDITOR PICKS

Samsung’s Galaxy S27 Pro could finally fix what was wrong with the Plus

Your AI agent just got a lot more accessible with OpenClaw’s new Android app

We need to talk about this. [Video]

POPULAR POSTS

Samsung’s Galaxy S27 Pro could finally fix what was wrong with the Plus

Your AI agent just got a lot more accessible with OpenClaw’s new Android app

We need to talk about this. [Video]

POPULAR CATEGORY

ABOUT US

FOLLOW US