KS1 - Guddu and his Mother

u can use a pair to store the numbers and the corresponding positions, then sort the array and maintain a frequency array. Now while counting the pairs to get all the permutations u will get a series (the positions need to be in ascending order for this).
My approach: https://www.codechef.com/viewsolution/25851329

why you have done
ans +=v[i][j] for i=0
@sid1091999

Because when i==0 the value in the vector at 0 is 0 and the expression for calculating distance becomes 0 as we are doing multiplication with 0 . Hence to avoid that i guess.

See EG : 5 2 7
PREFIX ARRAY : 5 7 0
Now no elements are repeating so is answer 0 ? No right .
Thus if in prefix array we encouter 0 that means from index 0 till that index subarray is 0.( Length of subarray will be 3 hence ans+=v[i][j]{which is the index of 0 i.e 2 in this case}) . Final answer 2.
Hope this helps :slight_smile:
@rakesh_54

2 Likes

Thanks a lot man ! understood it completely.

1 Like

In order to calculate the distance between the all pair you can keep track of index of last same element to find the current distance and the occurance of that element till now.
With basic hashing
It will go in just O (N) :stuck_out_tongue_winking_eye:

1 Like

I am describing tha same approach in different manner using Hashing in O (N) ; P

Firstly create the prefix XOR (let say A) and after that see the zero and the same elements in the array A and create a count variable equal to zero and increment the count variable by the number at which the zero comes and also increment the count variable for each equal elements.
Let say A = [1,2,0,3,1,4,0,1]
Count = 0
Count = (Count + 2 + 6)…(for the zero at index i ( as a first index equal to 0)
Now 1 and 0 are repeated
So first time the repeated element 1 is at the index 0 and second time is 4 so increment count variable by
Count = Count + absolute value of (4-(0+1))
Now for the third time 1 repeat so increment the count variable by seen from the starting time repetition
For ex
Count = Count + (7-(0+1))+(7-(4+1))
As the no of times number repeat the no of times the number add for addition in count variable this can be solved by dynamic programming, Same for the other repeated elements
Create an dictionary in which the keys are the repeated elements and their data is the array of 3 elements which is updated every time
So the first element is the index of that element , second element is the number of time it repeats and the third element is the number of the previous increment in the count variable…
This is little bit confusing
So see my solution in python in O(n)
https://www.codechef.com/viewsolution/25828488

Solution here

can u please tell how did u get to that conclusion if xor=0 then no of triples =size of subarray -1 or was that merely an observation??

It’s a property of xor that a xor a = 0 , so from this you know first thing you got to do is find subarrays having xor 0. Now for such subarrays if xor is 0 that means there are i , j and ks such that xor i to j-1 = xor j to k only then we are getting final xor as 0. Now coming to your question how we can conclude length - 1. Take the example 4 3 5 2.
What all groups you can make going from left => 4=3^5^2 ; 4^3= 2^5 ; 4^3^5=2 (total 3)
Everytime you will be able to make only length -1 groups.

A(i) ^ A(I+1) ^ … ^ A(j-1) = A(j) ^…^A(k) .
Consider L.H.S as X , A(j) as Y, rest as Z
XOR X to both sides we get A(i) ^ … ^ A(k) =0
Now to get zero two elements must be same, if u get two elements at positions say i and k equal(k>i) …how many j can u choose i<j<=k?
Hope this helps. :grinning:

1 Like

thankx bro really helped a lot : )

was really helpfull : )

Could you please explain what is prefix xor array?

Prefix XOR array is same as prefix sum array.
In that we just need to calculate the prefix XOR in which every element represent the value
If we have an array A and want to calculate the prefix array.

Prefix [i] = XOR (A [0], A [1].... A [i])

This expression represend the actual value of each index but we can optimally build it something like that.

Prefix [i] = XOR (Prefix [i -1], A[i])

If you still don’t understand what to do , then Sum of Absolute Difference Pair might help you :slight_smile:

It was a very interesting question in this LONG:
I’ll give you three methods of how I solved (and also approached the problem):

The beginning(Pure brute force):
#include<bits/stdc++.h>
using namespace std;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
for(int p=0; p<t; p++){
int n;
cin>>n;
vector v;
for(int q=0; q<n; q++){
long int num;
cin>>num;
v.push_back(num);
}
int count=0;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
for(int k=j; k<n; k++){
int x1=0, x2=0;
for(int m=i; m<j; m++){
x1=x1^v[m];
}
for(int n=j; n<=k; n++){
x2=x2^v[n];
}
if(x1==x2) count++;
}
}
}
cout<<count<<endl;
}
return 0;
}

Points awarded: 20

Some THINKING:
So I thought about the problem and came to the conclusion that the number of triples is equal to the summation of (len-1) where len is the size of subarray having zero XOR.

#include<bits/stdc++.h>

using namespace std;

int main(){
int t;
long int n;
cin>>t;
vector v(t, 0);
for(int p=0; p<t; p++){
cin>>n;
long int A[n];
for(int m=0; m<n; m++){
cin>>A[m];
}
for(int i=0; i<n; i++){
long int x=0;
int count=0;
for(int j=i; j<n; j++){
x=x^A[j];
count++;
if(x==0) v[p]+=(count-1);
}
}
}
for(int i=0; i<t; i++){
cout<<v[i]<<endl;
}
return 0;
}

Points awarded: 50

OPTIMIZATION:
This one was a real pain for me: had to learn and read about hashmaps (I was previously unaware of this topic) for optimization of the logic I applied previously. I also had to go over multiple pages of gfg for this.

#include<bits/stdc++.h>

using namespace std;

int main(){
long long int t;
long long int n;
cin>>t;
for(long long int p=0; p<t; p++){
long int count=0;
cin>>n;
long long int A[n], xorPrefix[n];
unordered_map<long int, vector> mp;
for(long long int q=0; q<n; q++){
cin>>A[q];
}
long long int x=0;
xorPrefix[0]=A[0];
for(long long int i=1; i<n; i++){
xorPrefix[i]=xorPrefix[i-1]^A[i];
}
for(long long int i=0; i<n; i++){
mp[xorPrefix[i]].emplace_back(i);
if(xorPrefix[i]==0) count+=i;
}
for(auto it=mp.begin(); it!=mp.end(); it++){
vector v= it->second;
long long int n=v.size();
long long int sum=0;
for(long long int i=n-1; i>=0; i–){
sum+=i*v[i]-(n-i-1)v[i];
}
sum-=n
(n-1)/2;
count+=sum;
}
cout<<count<<endl;
}
}

Points awarded: 100(AC)

can someone tell me whats wrong with my ans
import java.util.;
import java.io.
;
import java.lang.*;

class p176
{
public static void main(String args[])throws IOException
{

 try{		
 //takign input through IO
 InputReader in = new InputReader(System.in);
 OutputWriter out = new OutputWriter(System.out);
 int T = in.readInt();
 while(T>0)
 {   
	 ArrayList<Integer> list = new ArrayList<>();
	 list.add(0);
	 int N = in.readInt(),ans = 0,xor_tn = 0,i;
	 int values[] = IOUtils.readIntArray(in,N);
	 for(i=0;i<values.length;i++)
	 {
		 xor_tn = xor_tn^values[i];
		 if(list.contains(xor_tn))
		 {
			 ans+=(i-list.lastIndexOf(xor_tn));
			 list.add(xor_tn);
		 }
	 }
	 
	 out.printLine(ans);
	 out.flush();
	 T--;
 }
 out.close();
}catch(Exception e){
 e.printStackTrace();
}

}

}

class InputReader
{
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream)
{
    this.stream = stream;
}

public int read()
{
    if (numChars == -1)
        throw new InputMismatchException();
    if (curChar >= numChars)
    {
        curChar = 0;
        try
        {
            numChars = stream.read(buf);
        }
		catch (IOException e)
        {
            throw new InputMismatchException();
        }
        if (numChars <= 0)
            return -1;
    }
    return buf[curChar++];
}

public int readInt()
{
    int c = read();
    while (isSpaceChar(c))
        c = read();
    int sgn = 1;
    if (c == '-')
    {
        sgn = -1;
        c = read();
    }
    int res = 0;
    do
    {
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = read();
    } while (!isSpaceChar(c));
    return res * sgn;
}

public String readString()
{
    int c = read();
    while (isSpaceChar(c))
        c = read();
    StringBuilder res = new StringBuilder();
    do
    {
        res.appendCodePoint(c);
        c = read();
    } while (!isSpaceChar(c));
    return res.toString();
}

public double readDouble() {
    int c = read();
    while (isSpaceChar(c))
        c = read();
    int sgn = 1;
    if (c == '-')
	{
        sgn = -1;
        c = read();
    }
    double res = 0;
    while (!isSpaceChar(c) && c != '.')
	{
        if (c == 'e' || c == 'E')
            return res * Math.pow(10, readInt());
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = read();
    }
    if (c == '.')
	{
        c = read();
        double m = 1;
        while (!isSpaceChar(c))
		{
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            m /= 10;
            res += (c - '0') * m;
            c = read();
        }
    }
    return res * sgn;
}

public long readLong()
{
    int c = read();
    while (isSpaceChar(c))
        c = read();
    int sgn = 1;
    if (c == '-')
	{
        sgn = -1;
        c = read();
    }
    long res = 0;
    do
	{
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = read();
    } while (!isSpaceChar(c));
    return res * sgn;
}

public boolean isSpaceChar(int c)
{
    if (filter != null)
        return filter.isSpaceChar(c);
    return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public String next()
{
    return readString();
}

public interface SpaceCharFilter
{
    public boolean isSpaceChar(int ch);
}

}

class OutputWriter
{
private final PrintWriter writer;

public OutputWriter(OutputStream outputStream)
{
    writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}

public OutputWriter(Writer writer)
{
    this.writer = new PrintWriter(writer);
}

public void print(Object... objects)
{
    for (int i = 0; i < objects.length; i++)
    {
        if (i != 0)
            writer.print(' ');
        writer.print(objects[i]);
    }
}

public void printLine(Object... objects)
{
    print(objects);
    writer.println();
}

public void close()
{
    writer.close();
}

public void flush()
{
    writer.flush();
}

}

/*

USAGE

//initialize
InputReader in = new InputReader(System.in);
OutputWriter out = new OutputWriter(System.out);

//read int
int i = in.readInt();
//read string
String s = in.readString();
//read int array of size N
int[] x = IOUtils.readIntArray(in,N);
//printline
out.printLine(“X”);

//flush output
out.flush();

//remember to close the
//outputstream, at the end
out.close();
*/

class IOUtils
{
public static int[] readIntArray(InputReader in, int size)
{
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = in.readInt();
return array;
}

}

@vs_gamb since lhs==rhs therby by property of xor u get subarray xor is o then len-1 will be one of the answers so ans+=(len-1) for all the subarrays…
But i wrong answer could u plz check my implementation