Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Problem Statement Euler's bloodline has a secret rule that all descendants must choose their favourite number once they turn 1 8 . But if you

Problem Statement
Euler's bloodline has a secret rule that all descendants must choose their favourite number once they turn 18. But if you are a descendant of one the world's greatest Mathermaticians, you are not allowed to choose any random number right?
Aleksandra is turning 18 next month, but the problem is she is very bad at Math. So she approaches you with the conditions to choose a favourite number for her. The secret rule is that the chosen number must be a Parent Mask or Child Mask of at least one of the numbers listed down in a secret scroll passed through generations. Parent Mask of number X is defined as a number that can be obtained by flipping zero or more unset bits of X. Similarly Child Mask of X can be obtained by flipping zero or more set bits of X. As a reminder, set bits refer to 1s in the binary representation of the number and unset bits refer to the Os in its binary representation.
For example 3(11 in binary) is a Parent Mask of 2(10 in binary) as we can change the Least Significant bit of 2 from 0 to 1. By similar logic, 2 is a Child Mask of 3.
Written more formally:
Parent Mask(X)&X=X
ChiMask (X) & X Child Mask(X)
where & represents bitwise AND operator Note that an integer X is both Parent Mask and Child Mask of itself.
As stated before, Aleksandra is bad at mathematics(her family's genes missed her) so she stole the secret scroll with the list of numbers and gave it to you. The scroll contains N numbers Az. Az
AN Aleksandra has Q queries, each containing a single integer X Your task is to determine if X can potentially be
Aleksandra's favourite number or not. In short, determine if X is either a Parent Mask or Child Mask of at least one of the numbers A1, A2,....., AN.
Input Format:
The first line contains two space separated integers N and Q. denoting the count of numbers in the secret scroll and the number of queries Aleksandra has respectively.
Second line contains N space separated integers A1, A2,....... AN, the numbers as mentioned in the secret scroll.
The next Q lines each contain a number X which Aleksandra wants to know if it can be her favourite number or not.
Constraints:
2<=N<=10 power 6
1<=Q<=10 power 5
0<=Ai<=10 power 6
0<=X<=10 power 6
Output:
Print "Yes" or "No"(case sensitive) depending on if X can be Aleksandra's favourite number or not.
Sample input:
23
13
2
4
5
Sample output:
Yes
No
Yes
Sample output explanation:
The scroll contains the numbers 1 and 3 here.
1 The first query, 2subscrit10 is a child mask of 3subacript10, since 3subscript10 in binary is 112 and we can flip the last bit to obtain 10, which is 2subscipt10 decimal.
2. It can similarly be seen that 4subscript10(1002 in binary) is neither parent mask nor a child mask of both 110 and 3subscripy10-
3.5subscript10(1012) on the other hand is a parent mask of 1subacript10(1subscript2).
Note that the subscript 2 means binary and subscript 10 mean decimal as usual.

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Concepts

Authors: David Kroenke

4th Edition

0136086535, 9780136086536

More Books

Students also viewed these Databases questions

Question

What could Jean do to break the Facebook habit?

Answered: 1 week ago