A number is beautiful if the xor sum of the digits of the number is strictly greater than the average of the minimum and maximum digit of the number.
 |
| Software Engineering Practical Coding Question |
Given A and B, find the count of beautiful numbers in the range [A, B].
Since the answer can be very large, output the remainder after dividing the answer by 109+7
Note : The xor sum of the digits of a number is the bitwise XOR of all its digits.
Problem Constraints
1 <= A <= B <= 1018
Input Format
First argument A is a number in form of a string.
Second argument B is a number in form of a string.
Output Format
Return an integer
Example Input
Input 1:
A = "10"
B = "12"
Input 2:
A = "32"
B = "35"
Example Output
Output 1:
2
Output 2:
2
Example Explanation
For Input 1:
For 10, xor sum = 1 , average of maximum and minimum digit is 0.5.
For 11, xor sum = 0 , average of maximum and minimum digit is 1.
For 12, xor sum = 3 , average of maximum and minimum digit is 1.5.
The beautiful numbers are 10 and 12.
For Input 2:
For 32, xor sum = 1 , average of maximum and minimum digit is 2.5.
For 33, xor sum = 0 , average of maximum and minimum digit is 3.
For 34, xor sum = 7 , average of maximum and minimum digit is 3.5.
For 35, xor sum = 6 , average of maximum and minimum digit is 4.
The beautiful numbers are 34 and 35.
Sol :-
To solve this problem, we can iterate through the numbers in the range [A, B] and check whether each number is beautiful. To check whether a number is beautiful, we can first find the xor sum of its digits, the minimum and maximum digits, and then compare the xor sum to the average of the minimum and maximum digits. If the xor sum is strictly greater, we can increment our count of beautiful numbers.
Here is some sample code in Python that demonstrates this approach:
| Python |
|---|
| def beautiful_numbers(A, B, mod): count = 0 for num in range(int(A), int(B)+1): # Convert the number to a string and split it into digits digits = [int(d) for d in str(num)] # Find the xor sum of the digits xor_sum = 0 for d in digits: xor_sum ^= d # Find the minimum and maximum digits min_digit = min(digits) max_digit = max(digits) # Check if the xor sum is strictly greater than the average of the minimum and maximum digits if xor_sum > (min_digit + max_digit) / 2: count += 1 # Return the count modulo mod return count % mod # Test the function print(beautiful_numbers("10", "12", 1000000007)) # Expected output: 2 print(beautiful_numbers("32", "35", 1000000007)) # Expected output: 2 |
