2 days ago

John 760

Hyderabad

Question 1

Find X

Question 2

Decrypt

5 months ago

Edsger Dijkstra • 20

Patna

The solution to 1st Problem : Let's figure out all the bits of X individually.

1. If the ith bit of C is 0 then the ith bit of A and/ or B must be 0 else return -1. Because if ith bit of both A and B is 1 then that bit will be 1 in ((A | X) & (B | X)) which is not equal to C. Simply put this bit of X to 0.
2. Now if the ith bit of C is 1, then the ith bit of both (A | X) and (B | X) must be 1. If A and B both already have that bit as set, then the ith bit of X equals 0 because we are required to find the least value of X. If either of A or B has that bit as unset then ith bit of X must be 1.

18 months ago

Sumeet Kumar Mishra • 10

Q1) The following observations help us solve the problem. Consider the numbers A, B and C in their binary representation

1. The set bits in (A|X) will be the same as the set bits in A, and the set bits in X which were not set in A
   1. Hence (A|X)&(B|X) will be at least (A&B)
   2. Therefore the set bits in (A&B) have to be a subset of the set bits in C, if not it is not possible to find an answer
   3. Else let X be C - (A&B), the set bits in this number are those that are set in C but not in (A&B), this is the minimum answer as these bits are not set in (A&B) and hence, have to be set in X

7 weeks ago

Ayush Gangwani 1.1k

Navi Mumbai

Solution to Problem 2

Analysis

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.

Implementation

• We can first calculate the contribution of each character by scanning the numbers as explained.
• We can then sort the contributions and assign digits greedily to minimise the sum after assigning 0 separately as explained.

PseudoCode

solve(numbers):
    contributions = [0]*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[0].ischar()):
            first[string_rep[0]-'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