Digit Permutations
National Olympiad — Municipal round
Submission name: perm.cpp
Problem summary
Count how many input numbers have a different input number with exactly the same multiset of decimal digits. Count numbers, not matching pairs.
Input
N, followed by N distinct natural numbers. Read the numbers as strings.
Output
The number of input entries belonging to a digit-multiset group of size at least two.
Constraints
3 ≤ N ≤ 1,000,000; every value is less than 2⁶⁴; all input values differ.
Worked example
An independently prepared example for this explanation.
Input
5 12 21 34 43 7
Output
4
Solution analysis
- A digit rearrangement preserves the count of each of the ten digits.
- Represent those counts by a compact 64-bit signature: reserve five bits for each digit. Each count is at most 20.
- Keep a hash-table frequency for each signature.
- When a group gains its second member, add 2 to the answer; for every later member add 1. The first member alone adds nothing.
Why it works
Two numbers share a signature exactly when each digit appears equally often, which is equivalent to one being a rearrangement of the other. The updates count a group of size 1 as zero and a group of size k≥2 as k.
Watch out. Do not parse the values as signed long long: the input can exceed its maximum. Reading strings also preserves all digits.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<unordered_map>
#include<cstdint>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
unordered_map<uint64_t,int>frequency;
frequency.reserve(n);
int answer=0;
for(int i=0;i<n;++i){
string number;
cin>>number;
uint64_t key=0;
// Each digit owns a five-bit counter inside key.
// At most 20 digits: no counter can overflow its five bits.
for(char c:number){
key+=uint64_t(1)<<(5*(c-'0'));
}
int&count=frequency[key];
if(count==1){
answer+=2; // First and second now both qualify.
}
else if(count>=2){
++answer; // Only the new member is uncounted.
}
++count;
}
cout<<answer<<'\n';
}