Join Us
@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
Entering edit mode
Question 1
Click here to Practice
Submit Problem to OJ
Find X
Question 2
Click here to Practice
Submit Problem to OJ
Decrypt
Entering edit mode
The solution to 1st Problem : Let's figure out all the bits of X individually.
- 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.
- 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.
Entering edit mode
Q1) The following observations help us solve the problem. Consider the numbers A, B and C in their binary representation
- 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
- Hence (A|X)&(B|X) will be at least (A&B)
- 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
- 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
Entering edit mode
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
Loading Similar Posts
int solve(int a,int b,int c){
int ans=0;
for(int i=0;i<31;i++){
if((c>>i)&1){
if((((a>>i)&1) == 1) && (((b>>i)&1) == 1)){
ans+=0;
}else{
ans+=(1ll<<i);
}
}else{
if((((a>>i)&1) == 1) && (((b>>i)&1) == 1)){
return -1;
}
}
}
return ans;
}