Prev   Next

TRIPLETS-1







Decide what you want, decide what you are willing to exchange for it.

TRIPLETS-1

Howdy coder. We start with a new question, "Triplets-1". Be attentive.

We want you to go through the problem first to understand its outline and syntax.


Important Links : Problem Link, Solution Video


  • You are given an array (arr) of N numbers.
  • You have to select three indices i, j, k following this condition :
    0 <= i < j <= k < arr.length
  • Two numbers X and Y as defined as :
    X = arr[i] ^ arr[i+1] ^ ... ^ arr[j - 1]
    Y = arr[j] ^ arr[j+1] ^ ... ^ arr[k]
  • You have to print the number of triplets where X is equal to Y.
Approach :

Reader, we discuss the approach by considering the following scenario.

We are given the input array as [a,b,c,d,e,f]. Two pointers p1 and p2 are taken. This p1 moves in the outer loop and p2 moves in the inner loop.

img

We assume that at the current instance, p1 points to b and p2 points to e. We calculate b^c^d^e. Let this value come out to be 0 i.e. b^c^d^e=0.

Now we place 'i' at b and 'k' at e. We see that since i< j<=k,therefore, j can be placed at either 'c' or 'd' or 'e'.

We represent the elements in sets X and Y as X-Y. So, the sets are as follows if j is placed on:

  • c : b-cde
  • d : bc-de
  • e : bcd-e

Reader, meditate on the fact that since b^c^d^e=0 and XOR cancels out duplicate elements, therefore in the above 3 cases, b=cde , bc=de and bcd=e.

If you are not able to understand this fact, we prove it using the example given below.

img

In this example, the array given to us is [5,6,2,3,3,5,3,2,5,3,8,9].

We place 'i' on 2 and 'k' on 3 and get 2^3^3^5^3^2^5^3=0. Since, i< j< =k, therefore, j can point to any of the bulleted elements.

In figure 2, the sets X-Y can be seen for all the elements 'j' can point on.

If 'j' pointed to the element at index 3, with a value of 3, then the set would been:

2-3353253

Remember that we cancel all the duplicates when we apply XOR as shown in figure 2, which is why we are left with 2-2 is. Here X=Y. Hence we obtain one of our desired answers.

Reader, we want you to try this for the other sets too. They all fulfill X=Y.

CODE

If you have understood the approach, then writing its code is quite simple.

import java.io.*; import java.util.*; public class Main { public static void solution(int[] arr){ int c=0; //1 for(int i=0;i< arr.length;i++){ //2 int val=arr[i]; for(int k=i+1;k< arr.length;k++){ //3 val=val^arr[k]; if(val==0){ //4 c+=(k-i); } } } System.out.println(c); //5 } public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int[] arr = new int[n]; for(int i = 0 ; i < arr.length; i++){ arr[i] = scn.nextInt(); } solution(arr); } }
java; true";
  1. We initialize count variable 'c' with 0.
  2. Then for 'i', we run an outer loop for every element of the array and initialize the 'val' variable with the current element's value.
  3. Next, an inner loop is run for 'k' from i+1 to the end of the array as i< k. The 'val' variable is updated applying XOR to it with every element at the position k.
  4. If we find out that at an instance, the XOR of all the elements between 'k' and 'i' is equal to 0 (as discussed in the approach), then we add the number of all the sets that can be formed between the value of 'k' and 'i' at that moment (k-i sets) to the count.
  5. The final value of count is printed.
Analysis
Time Complexity:

O(n2)

Space Complexity:

O(1)

Here we conclude our discussion. You may watch the solution video too if you have any gaps in your understanding.

Triplets
Bit Manipulation
Author: Shreeya Gupta
 
Run
Id Name