The solution to 1st Problem : Let's figure out all the bits of X individually.
Q1) The following observations help us solve the problem. Consider the numbers A, B and C in their binary representation
A naive way to solve the problem would be to try every assignment of the digits 0-9 to the characters A-Z. Since there are 10! such ways, the solution would be way too slow and hence would TLE. A better solution would be to find the weight(or contribution) of each character in the sum of the numbers and decide the assignment accordingly. To find the contribution of each character we can scan the numbers and note that if some character appears at position
i in some number (indexed from the least significant position to the most significant position), then it would contribute
10^i to the sum of numbers. Thus we can find the weight associated with each character and assign the digits to characters greedily as per their weights. It makes sense to assign a small digit to a character having a large weight and a large digit to a character having a small digit. Here, we need to keep one thing in mind that we cannot assign 0 to some character that appears as the first digit in some number as the resultant number will then have leading zeros which is not valid. Hence we first assign 0 to some character that does not appear as the first digit in any number and then assign the digits 1-9 greedily to the remaining characters based on their weight.
solve(numbers): contributions = *10 //Initialise contributions array with zeroes initially first = [false]*10 //auxilliary array to track if some char has appeared as first digit in some number ans = 0 for number in numbers: string_rep = string(number) //Converting to string to access each digit if(string_rep.ischar()): first[string_rep-'A'] = true string_rep.reverse() for i from 0 to string_rep.length(): if(string_rep[i].ischar()): contributions[string_rep[i]-'A'] += 10**i //add 10^i contribution to character at i-th position else: ans += (string_rep[i]-'0')*(10**i) mx = 0 //finding the character with max contribution such that it for i from 0 to 9: //does not appear as the first digit in any number if(!first[i]): mx = max(mx,contributions[i]) contributions.erase(mx) //assigning 0 separately to the such character. contributions.sort(reverse=True) //sort the contributions for i from 0 to 8: //assign smaller digits to characters having greater contribution and vice versa ans += (i+1)*contributions[i] return ans
@Shanu Rajmaniar-2831 Your solution seems correct for the problem, the same problem was asked in Google OA on 8th October . You can also validate your solution by submitting your code here