# PALIXOR - Editorial

Author: saksham441
Tester & Editorialist: iceknight1093

2014

# PREREQUISITES:

Familiarity with bitwise XOR, frequency tables, observation

# PROBLEM:

Given an array A, count the number of pairs (i, j) such that 1 \leq i \leq j \leq N and A_i \oplus A_j is a palindrome.
It’s known that A_i \lt 2^{15}.

# EXPLANATION:

A brute force algorithm would be to check for each (i, j) pair whether their XOR forms a palindrome; of course, this is too slow.

Notice that the number of distinct palindromes we care about is really quite small.
In particular, there are only about \mathcal{O}(10^{\frac{\log_{10}X}{2}}) (which is about \mathcal{O}( \sqrt X)) palindromes below X, because fixing one half of the palindrome fixes the other half as well.
In particular, only 427 of the numbers upto 2^{15} are palindromes.

Further, recall that XOR is an involution, i.e, x\oplus y = z also means that x = z\oplus y.

So, instead of fixing i and j and checking if A_i\oplus A_j is a palindrome, we can fix i and the target palindrome; which then uniquely fixes A_j; after which we only need to count the number of valid j.

That is,

• Let \text{Pal} be a list of palindromes upto 2^{15}. This can be precomputed, and has length 427.
• Then, for each i from 1 to N, and each x in \text{Pal},
• Let y = A_i \oplus x.
• We then want to know the number of indices j such that A_j = y.
This can be found in \mathcal{O}(1) using a frequency table.

Make sure not to overcount pairs of indices, since the above algorithm didn’t account for the i \leq j condition.
That’s not too hard: all pairs except (i, i) will be counted twice, so divide by 2 appropriately.

The complexity is something like \mathcal{O}(430\cdot N) (more formally, \mathcal{O}(N\cdot \sqrt{\max A})), which is good enough to get AC.

Note that the frequency table can be implemented using either an array or a hashmap (std::unordered_map, dict, HashMap) and should run in time without much issue.
Using std::map will likely be too slow because of the extra \log factor.

# TIME COMPLEXITY

\mathcal{O}(N\cdot P) per test case, where P is the number of palindromes not exceeding 2^{15} (approximately 430).

# CODE:

Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
vector<int>allPalindrome;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
bool isPalindrome(int num){
int rev=0;
int temp=num;
while (num>0){
rev=rev*10 + (num%10);
num/=10;
}
return (rev==temp);
}
void solve(){
long long int n;
cin>>n;
long long int v[n];
long long int freq[(1<<17)];
memset(freq,0,sizeof(freq));
for (int i=0;i<n;i++){
cin>>v[i];
freq[v[i]]++;
}
long long int ans=0;
for (int i=0;i<allPalindrome.size();i++){
long long int num=allPalindrome[i];
for (int j=0;j<n;j++){
ans+=freq[v[j]^num];
}
}

//Divide ans by 2 as each pair will be calculated twice
ans/=2;
//add all pairs such that A[i]^A[j] = 0 means A[i] and A[j] are same
for (int i=0;i<(1<<17);i++){
ans = ans + (freq[i] * (freq[i]+1))/2;

}
cout<<ans<<endl;
}

void generatePalindromes(){
for (int i=1;i<=(1<<17);i++){
if (isPalindrome(i)){
allPalindrome.push_back(i);
}
}
}

int main(){
int t;
fast;
cin>>t;
generatePalindromes();
while (t--){
solve();
}
}

Editorialist's code (Python)
mx = 1 << 15
palindromes = []
for i in range(mx):
if str(i) == str(i)[::-1]: palindromes.append(i)

for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
freq = {}
ans = 0
for x in a:
if x in freq: freq[x] += 1
else: freq[x] = 1
for x in a:
for y in palindromes:
if x^y <= x: continue
if x^y in freq: ans += freq[x^y]
for x in freq.values(): ans += x*(x+1)//2
print(ans)

1 Like

Can anyone explain this part:
ans = ans + (freq[i] * (freq[i]+1))/2;

1 Like

This to count the palindromes made by same element. Like see the second test case given in the problem statement [2,2,2] here we can pick any two indices{0,1,2} and XORing them will give us a palindrome (2 XOR 2 =0 which is a palindrome ) so the total number of such cases is Number of occurrences of 2 * (Number of occurrences of 2 +1 ) /2 which comes from nC2 as we can choose any two indices.

If you have frequency of an element as 4, how many i,j pairs are possible… let the indices be 1,2,3,4…
So 1 has 4 options, 2 has 3 options, 3 has 2 options and 4 has 1…

1,1
1,2
1,3
1,4

2,2
2,3
2,4

3,3
3,4

4,4

So the ans will be sum of 1 till N… hence it is N*(N+1)/2

Will it not be counted in the this part:

for (int i=0;i<allPalindrome.size();i++){
long long int num=allPalindrome[i];
for (int j=0;j<n;j++){
ans+=freq[v[j]^num];
}
}

//Divide ans by 2 as each pair will be calculated twice
ans/=2;


how we are ensuring that Ai ^ Aj will not exceed (1<<15) ? Is there any mathematical proof or property of xor?

A_i and A_j are themselves \lt 2^{15}, which is a way of saying they’re both (at most) 15-bit integers.
The XOR of two 15-bit integers will of course also be a 15-bit integer, since all higher bits are off in both numbers and so will also be off in their XOR.

1 Like

Why am i getting TLE . The time complexity is same as you defined .
https://www.codechef.com/viewsolution/97832326
Anyone ?

The editorialist’s code is getting TLE.
https://www.codechef.com/viewsolution/97944069

It’s in PYPY3.

As mentioned in the editorial,

which is what your code does.

admin mentioned this above, but when using Python for competitive programming, it’s almost always better to submit in PyPy rather than plain Python - the code is the exact same but it runs much faster.
My code will AC comfortably if submitted under PYPY3.

1 Like

Can someone tell me, what’s wrong in this? It gives the wrong answer for second testcase, my solution