Log | Problem Solving >

# Problem: Panda and XOR

## URI for problem

https://www.hackerearth.com/tracks/pledge-2015-easy/panda-and-xor

## Problem Statement (copied as it is, formatted)

Little Black Panda is mad about XOR operation.

Presently he has gone mad and he won’t stop performing XOR operation on various numbers.Given an array of N numbers, for each subset of the array Little Panda

performs MAXOR operation for the subset. MAXOR operation means that he finds XOR of all elements in that subset (if the subset is [1,2,3]

then MAXOR is 1^2^3=0) .

Little Panda is now exhausted and wants to do something else. Little Panda wants to pick any two subsets the MAXOR of whose are same.

Little Panda needs to find the number of selections that he can make.

He is very very weak in programming so he wants the answer from you.

Please help little panda in finding out his query.Since the output can be very large output it modulo 1000000007.

Input Format

The first line contains N i.e. the length of the array.

N lines follow, each containing a non-negative integer.Output Format

Output Little Panda’s Query in a single line.Constraints

1 <= N <= 100000

0 <= A[i] <= 100

where A[i] denotes the value of array elementSample Input

3 1 2 3

Sample Output

3Explanation

Little Panda can pick the subsets:

1. {1,3} and {2} whose MAXOR is 2.

2. {1,2} and {3} whose MAXOR is 3.

3. {2,3} and {1} whose MAXOR is 1.Time Limit: 1 sec(s) for each input file. Memory Limit: 256 MB

Source Limit: 1024 KB

Marking Scheme: Marks are awarded if any testcase passes.

Allowed languages: C, CPP, CLOJURE, CSHARP, GO, HASKELL, JAVA,

JAVASCRIPT, JAVASCRIPT_NODE, LISP, OBJECTIVEC, PASCAL, PERL, PHP,

PYTHON, RUBY, R, RUST, SCALAProblem Author: Akash Agrawall Problem

Tester: Deepankar Anil Kumar

## Few problems with problem statement

There are a few problems with this problem statement:

- Input Format says that ‘N lines follow’, that’s not the case in the sample input.

- nothing to worry though;

- Empty sub-sets are not allowed; not mentioned.

Anyway, moving on to the solving problem.

## I do not know how to solve this problem. No clue at all.

Well, then I moved to editorial. Poorly written editorial. I understand that a hacker mindset is behind all this, but clarity is elusive to the point that it might be an alien concept to the author at that time. Still maybe. Hackers don’t learn to code clearer until they stop hacking and think for a moment.

So, I am going to learn from the editorial and the given link and solve the problem myself, but first.

I found this code presented as the code that was used to solve the problem.

```
/*******************
Akash Agrawall
IIIT HYDERABAD
***********************/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<functional>
#include<numeric>
using namespace std;
#define FOR(i,a,b) for(i= a ; i < b ; ++i)
#define rep(i,n) FOR(i,0,n)
#define INF INT_MAX
#define ALL(x) x.begin(),x.end()
#define LET(x,a) __typeof(a) x(a)
#define IFOR(i,a,b) for(LET(i,a);i!=(b);++i)
#define EACH(it,v) IFOR(it,v.begin(),v.end())
#define pb push_back
#define sz(x) int(x.size())
#define mp make_pair
#define fill(x,v) memset(x,v,sizeof(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define si(n) scanf("%d",&n)
#define pi(n) printf("%d ",n)
#define pd(n) printf("%lf ",n);
#define pdl(n) printf("%lf\n",n);
#define pin(n) printf("%d\n",n)
#define pln(n) printf("%lld\n",n)
#define pl(n) printf("%lld ",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define scan(v,n) vector<int> v;rep(i,n){ int j;si(j);v.pb(j);}
#define mod (int)(1e9 + 7)
#define ll long long int
#define F first
#define S second
ll modpow(ll a,ll n,ll temp){ll res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;}
ll arr[100006],flagit[134],flg[134];
inline ll checkit(ll calc)
{
if(calc>=mod)
calc%=mod;
return calc;
}
inline ll chck(ll calc)
{
while(calc<0)
calc+=mod;
calc%=mod;
return calc;
}
int main()
{
ll n,calc,calc1,i,j,sz,c1,c2,ans=0;
sl(n);
rep(i,n)
{
sl(arr[i]);
}
rep(i,135)
flagit[i]=0;
rep(i,n)
{
rep(j,135)
flg[j]=0;
rep(j,129)
{
if(flagit[j]!=0)
{
calc=j^arr[i];
//printf("i=%d j=%d calc=%d\n",i,j,calc);
flg[calc]+=flagit[j];
flg[calc]=checkit(flg[calc]);
}
}
rep(j,129)
{
//printf("i=%d calc=%d calc1=%d\n",i,calc,calc1);
flagit[j]+=flg[j];
flagit[j]=checkit(flagit[j]);
}
flagit[arr[i]]++;
flagit[arr[i]]=checkit(flagit[arr[i]]);
}
c2=modpow(2,mod-2,mod);
//pln(c2);
rep(i,129)
{
//printf("i=%d flagit=%d\n",i,flagit[i]);
calc=flagit[i];
c1=calc*(calc-1);
c1=chck(c1);
c1=c1*c2;
c1=checkit(c1);
ans+=c1;
ans=checkit(ans);
}
pln(ans);
return 0;
}
```

Now, this code is hideous as shit. Poorly named macro to unused code. Hmm, I ought to clear the mess.

So I did clear the mess.

This is code looks like after a half hour clean up.

```
#include<iostream>
using namespace std;
#define MOD (int)(1e9 + 7)
long long int modpow(long long int a, long long int n, long long int temp)
{
long long int res = 1, y = a;
while (n > 0) {
if (n & 1){
res = (res*y) % temp;
}
y = (y*y) % temp;
n /= 2;
}
return res % temp;
}
long long int arr[100006], flagit[134], flg[134];
inline long long int chck(long long int calc)
{
while (calc < 0)
calc += MOD;
calc %= MOD;
return calc;
}
int main()
{
long long int n, calc, calc1, i, j, c1, c2, ans = 0;
scanf("%lld", &n);
for (i = 0; i < n; i++)
{
scanf("%lld", &arr[i]);
}
for (i = 0; i < 135; i++)
flagit[i] = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < 135; j++)
flg[j] = 0;
for (j = 0; j < 129; j++)
{
if (flagit[j] != 0)
{
calc = j^arr[i];
flg[calc] += flagit[j];
flg[calc] = flg[calc] % MOD;
}
}
for (j = 0; j < 129; j++)
{
flagit[j] += flg[j];
flagit[j] = flagit[j] % MOD;
}
flagit[arr[i]]++;
flagit[arr[i]] = flagit[arr[i]] % MOD;
}
c2 = modpow(2, MOD - 2, MOD);
for (i = 0; i < 129; i++)
{
calc = flagit[i];
c1 = calc*(calc - 1);
c1 = chck(c1);
c1 = c1*c2;
c1 = c1 % MOD;
ans += c1;
ans %= MOD;
}
printf("%lld\n", ans);
return 0;
}
```

Looks almost half the lines now.

## These many include directives deleted.

```
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<functional>
#include<numeric>
```

That’s just too many.

There are other things that I have deleted like unused macros etc.

I can refactor more. Wait I’ll show you the refactored code. No tests though.

[This is a live post. Timestamp: 11:22 July 27, 2015]

Okay, at 11:51 AM, after half an hour of refactoring and making sure that code works, here’s my submission.

## Refactored code

```
#include<iostream>
using namespace std;
#define MOD (int)(1e9 + 7)
long long int CalculateC2(long long int a, long long int n, long long int temp)
{
long long int res = 1, y = a;
while (n > 0) {
if (n & 1){
res = (res*y) % temp;
}
y = (y*y) % temp;
n /= 2;
}
return res % temp;
}
long long int arr[100006], flagit[134], flg[134];
inline long long int Sanitize(long long int calc)
{
while (calc < 0)
calc += MOD;
calc %= MOD;
return calc;
}
long long int GetInputs(){
long long int numberOfInputs, i;
scanf("%lld", &numberOfInputs);
for (i = 0; i < numberOfInputs; i++)
{
scanf("%lld", &arr[i]);
}
return numberOfInputs;
}
void SetArrayToZero(long long int arr[], long long int count)
{
long long int i = 0;
for (i = 0; i < count; i++) {
arr[i] = 0;
}
}
long long int CalculateC1(long long int index, long long int c2)
{
long long int c1 = Sanitize(flagit[index] * (flagit[index] - 1));
return (c1*c2) % MOD;
}
long long int CalculateNumberOfSetsWithEqualXOR(void)
{
long long int i = 0, ans = 0, c2 = CalculateC2(2, MOD - 2, MOD);
for (i = 0; i < 129; i++)
{
ans = (ans + CalculateC1(i, c2)) % MOD;
}
return ans;
}
void ProcessInput(long long int i)
{
long long int j = 0, calc = 0;
SetArrayToZero(flg, 135);
for (j = 0; j < 129; j++)
{
if (flagit[j] != 0)
{
calc = j^arr[i];
flg[calc] += flagit[j];
flg[calc] = flg[calc] % MOD;
}
}
for (j = 0; j < 129; j++)
{
flagit[j] += flg[j];
flagit[j] = flagit[j] % MOD;
}
flagit[arr[i]]++;
flagit[arr[i]] = flagit[arr[i]] % MOD;
}
void ProcessAllInputs(long long int numberOfInputs)
{
long long int i = 0;
for (i = 0; i < numberOfInputs; i++)
{
ProcessInput(i);
}
}
long long int CalculateNumberOfMatchingXORSets(){
long long int numberOfInputs = GetInputs();
SetArrayToZero(flagit, 135);
ProcessAllInputs(numberOfInputs);
return CalculateNumberOfSetsWithEqualXOR();
}
int main()
{
long long int numberOfMatchingXORSets = CalculateNumberOfMatchingXORSets();
printf("%lld\n", numberOfMatchingXORSets);
return 0;
}
```

Notice that I have created a ton of functions and broke the code in little pieces. I have not renamed much variables or functions. I’ll tell you why? It was really a bad piece of code.

When you write code, other should be able to read and understand the problem that you are trying to solve. Disclaimer: I have been guilty of writing unreadable code. I strive to clean the code as much as possible these days,

Anyway, still do not understand the code or problem or solution. Going to read up on it.

11:55 AM.

Come to think about it, this code is C code. Hmm. Also, I am going to rename the `long long int`

to `HugeInt`

via define directive.

Let me check if it works.

Yes it does! It’s C code.

So this was another thing that was wrong; but this time with the given code.

Now, I want to convert this code to C#.

So here’s the C# code.

## C#

```
using System;
namespace HackerEarthProblemSolving
{
class PandaAndXorSolution
{
long MOD = (long)(1e9 + 7);
long [] arr = new long[100006];
long [] flagit = new long[134];
long [] flg = new long[134];
long CalculateC2(long a, long n, long temp)
{
long res = 1, y = a;
while (n > 0) {
if (n % 2 == 1){
res = (res*y) % temp;
}
y = (y*y) % temp;
n /= 2;
}
return res % temp;
}
long Sanitize(long calc)
{
while (calc < 0)
calc += MOD;
calc %= MOD;
return calc;
}
long GetInputs(){
long numberOfInputs = long.Parse(Console.ReadLine());
for (long i = 0; i < numberOfInputs; i++)
{
arr[i] = long.Parse(Console.ReadLine());
}
return numberOfInputs;
}
void SetArrayToZero(long [] arr)
{
for (long i = 0; i < arr.Length; i++)
arr[i] = 0;
}
long CalculateC1(long index, long c2)
{
long c1 = Sanitize(flagit[index] * (flagit[index] - 1));
return (c1*c2) % MOD;
}
long CalculateNumberOfSetsWithEqualXOR()
{
long i = 0, ans = 0, c2 = CalculateC2(2, MOD - 2, MOD);
for (i = 0; i < 129; i++)
{
ans = (ans + CalculateC1(i, c2)) % MOD;
}
return ans;
}
void ProcessInput(long i)
{
SetArrayToZero(flg);
for (long j = 0; j < 129; j++)
{
if (flagit[j] != 0)
{
long calc = j^arr[i];
flg[calc] += flagit[j];
flg[calc] = flg[calc] % MOD;
}
}
for (long j = 0; j < 129; j++)
{
flagit[j] += flg[j];
flagit[j] = flagit[j] % MOD;
}
flagit[arr[i]]++;
flagit[arr[i]] = flagit[arr[i]] % MOD;
}
void ProcessAllInputs(long numberOfInputs)
{
for (long i = 0; i < numberOfInputs; i++)
{
ProcessInput(i);
}
}
long CalculateNumberOfMatchingXORSets(){
long numberOfInputs = GetInputs();
SetArrayToZero(flagit);
ProcessAllInputs(numberOfInputs);
return CalculateNumberOfSetsWithEqualXOR();
}
public long Solve()
{
return CalculateNumberOfMatchingXORSets();
}
}
class PandaAndXorRunner
{
static void Main(){
PandaAndXorSolution paxs = new PandaAndXorSolution();
Console.WriteLine(paxs.Solve());
}
}
}
```

So, C# is done.

[Next Day - 7:40 AM 7/28/2015]

Today I am going to solve the problem on my own in C# first. I am going to use the logic provided in the editorial.

## Logic provided in Editorial

```
freq[]={0} //initially
for i = 1 to n //Traversing the array:
temp[] = {0}
for j = 0 to 127
//Finding the values which are computed as MAXOR of some subset:
if freq[j] not equal to 0:
//Means this value is computed as MAXOR of some subset
//Now arr[i] can also be XORed with it
temp[j^arr[i]]+=freq[j]
for j = 0 to 127
freq[j]+=temp[j]
freq[arr[i]] += 1
```

Let’s see how it comes out.

I have understood problem:

So, for those who haven’t got the problem or who are new to the

problem, the problem boils down to two statements.1) Find the XOR of every element in every subset for a given set; except null and set itself.

example: For a given set {1, 2, 3}: Calculate XOR of {1}, {1, 2}, {1,

3}, {2}, {2, 3}, {3}. {1} = 1; {2} = 2; {3} = 3; {1, 2} = 3; {2, 3} =

1; {1, 3} = 2;2) Then find the number of ways you can pick two such subsets that their XOR values are equal.

example:

(continuing from above)

Now, pick two subsets:

{1} and {2, 3} = 1 way to pick.

{2} and {1, 3} = 1 way to pick.

{3} and {1, 2} = 1 way to pick.Total ways: 3. And that’s the answer.

I’ll try to solve the problem myself next month. This problem is reflection of the reason why I hate online code submission platforms.