# Decrypt DSA Problem Solution

Decrypt DSA Problem Solution

In this post, we are going to solve Decrypt DSA Problem from Oracle, Online Assessments conducted on 13th October,2022. Let’s have a look at the problem statement first and then try to solve the problem.

## Decrypt DSA Problem Statement

Alice has an integer array

$A$$A$ of size

$N$$N$. Alice has saved these integers in her computer but due to a virus attack some of the digits of her integers changed to some character of uppercase English alphabets from ‘A’ to ‘J’, but it is known that a unique digit is changed with a unique character.

For example, Let us suppose an integer was “1221321” and due to the virus,it is changed to “B2AB3A1”, i.e., some of “1” is changed to the character ‘B’ and some of ‘2’ is changed to the character ‘A’. But it is not possible that this integer is changed to “BB21321” or “B22A321” because In “BB21321” two different digits are changed to a single character ‘B’ and in “B22A321” two same digits ‘1’ is changed to two different characters.

You have been given array

$A$$A$ after the virus attack, Alice asked you to decode integers in this array in such a way that after decoding, the summation of all integers of the array is minimum possible.

Note: You have to decode the integers in such a way that no integer contain leading zeroes like 001, 0123, 0 etc.

Input

The first line of input contains an integer

$t$$t$

$\left(1\le t\le {10}^{4}\right)$$(1 \le t \le 10^4)$ — the number of testcases.The description of

$t$$t$ testcases follows.

The first line of each testcase contains an integer

$N$$N$

$\left(1\le N\le {10}^{5}\right)$$(1 \le N \le 10^5)$ — the size of array

$A$$A$.

The second line of each testcase contains

$N$$N$ space separated alpha-numeric strings denoting the elements of array

$A$$A$. There will be atmost 10 characters in every element of array

$A$$A$.

It is guaranteed that sum of

$N$$N$ over all testcases does not exceed

${10}^{5}$$10^5$.

Output

For each testcase, print a single integer — the maximum possible sum of elements of array

$A$$A$.

Example
Input
3
2
A1A 2AB
3
CB BC BAB
3
A1A3 AAB BD1
Output
321
134
1426

Note

In sample test case 1, one of the optimal ways is to assign ‘A’ = 1 and ‘B’ = 0, then array

$A$$A$ will be

$\left[111,210\right]$$[111,210]$ and hence sum =

$111+210=321.$$111 + 210 = 321.$

In sample test case 2, one of the optimal ways is to assign ‘A’ = 0, ‘B’ = 1 and ‘C’ = 2, then array

$A$$A$ will be

$\left[21,12,101\right]$$[21,12,101]$ and hence sum =

$21+12+101=134.$$21+12+101 = 134.$

In sample test case 3, one of the optimal ways is to assign ‘A’ = 1, ‘B’ = 2 and ‘D’ = 0, then array

$A$$A$ will be

$\left[1113,112,201\right]$$[1113,112,201]$ and hence sum =

$1113+112+201=1426.$$1113+112+201 = 1426.$

## Problem Solution in C++

#include <bits/stdc++.h>
using namespace std;

bool cmp(pair<int, long long int> p1, pair<int, long long int> p2){
return p1.second > p2.second;
}
int main() {
int t;
cin>>t;
while(t){
int n;
cin>>n;
vector<string> v;
for(int i=0;i<n;i++){
string str;
cin>>str;
v.push_back(str);
}
vector<pair<int, long long int>> charCnt(10, {10, 0});
for(auto str: v){
int l = str.size();
for(int i=0;i<l;i++){
int ind = str[i]-'A';
if(ind>=0 && ind<10){
int minInd = charCnt[ind].first;
long long val = charCnt[ind].second;
minInd = min(minInd, i);
val += pow(10, l-1-i);
charCnt[ind].first = minInd;
charCnt[ind].second = val;
}
}
}
vector<int> charCode(10, -1);
int code = -1;
long long maxCnt = -1;
for(int i=0;i<10;i++){
if(charCnt[i].first != 0){
if(charCnt[i].second > maxCnt){
maxCnt = charCnt[i].second;
code = i;
}
}
}
charCode[code] = 0;
for(code=1;code<10;code++){
int c = -1;
maxCnt = -1;
for(int i=0;i<10;i++){
if(charCode[i] == -1){
if(charCnt[i].second > maxCnt){
maxCnt = charCnt[i].second;
c = i;
}
}
}
charCode[c] = code;
}
// for(int i=0;i<10;i++){
// cout<<charCode[i]<<endl;
// }
long long ans = 0;
for(auto str: v){
int l = str.size();
long long num = 0;
for(int i=0;i<l;i++){
int ind = str[i]-'A';
if(ind>=0 && ind<10){
num = num*10 + charCode[ind];
}
else{
num = num*10 + str[i]-'0';
}
}
ans += num;
}
cout<<ans<<endl;
t--;
}

return 0;

}