# Day 29: Bitwise AND

# Day 29: Bitwise AND

Jekus + 16 comments ### A solution in Python 3:

T = int(input().strip()) for _ in range(T): n , k = map(int , input().split()) print(k-1 if ((k-1) | k) <= n else k-2)

**NOTE**:Before reading the explanation below , try to find the pattern using a brute force solution.

Tleilaxi + 1 comment By far the best solution here. I would be curious to know what is the tought process that brought you there ?

el71Gato + 1 comment What would you say for this? https://www.hackerrank.com/challenges/30-bitwise-and/forum/comments/542990

torayeff + 0 comments it is explicitly given that 2 <= K <= N

mkr_raju1991 + 2 comments It will be really helpful if you could explain the idea behind this solution..

Jekus + 0 comments [deleted]Jekus + 9 comments When

**k**is**ODD**,**k-1**is**EVEN**,**k-1**can always be reached by`(k-1) & k`

.In binary form: k = 11 k-1 = 10 k-1 == (k-1) & k

## That is ,

`((k-1) | k)`

is always`k`

. And`((k-1) | k) <= n`

is always TRUE.

When

**k**is**EVEN**,**k-1**is**ODD**,**k-1**can only be reached if and only if`((k-1) | k) <= n`

is**TRUE**# Why?

In binary form: k = 10110 k-1 = 10101 pos = 10111 k-1 == (k-1) & pos

You can get

**k-1**if`pos <= n`

is**TRUE**. And you can get**pos**by`((k-1) | (k-1+1))`

, that is ,`((k-1) | k)`

. Otherwise , you just need to follow the process above when**k**is**ODD**(because**k-1**is**ODD**) , then you get the answer**k-2**.

## In brief , you can just do the test

`((k-1) | k) <= n`

to determine the answer.SalahAssana + 1 comment So does this solution only work when we know that the set of number we're working with are consecutive, non-repeating postive intgegers that will go up to n?

dimm_ddr + 0 comments For this solution you need only non-repeating k and k-1 in set. With possible repeating case you need only check if there more then one k-1. This solution will not work only if you don't have k and k-1 in set. Yes, as far as I understand, this solution has restrictions, just not as strong as you say.

nimmumanoj + 0 comments **AMAZING SOLUTION. It took some time for me to understand this. GREAT WORK**garyzhang2681 + 8 comments Great answer! Here is the code

public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int k = in.nextInt(); if(((k-1)|k) > n && k%2==0){ System.out.println(k-2); }else{ System.out.println(k-1); } } } }

bijina_pv + 1 comment yeah! simple code

Divyesh_Patel + 0 comments [deleted]

404hunter + 0 comments OMG you so genius! it doesn't need to calculate remainder and mod things for each cases... Thanks a lot!!

kallolds + 0 comments It's really a piece of code with elegance. Thanks bro!!

P1zzAdr0hn3 + 0 comments for a in range(int(input())): n , k = map(int , input().split()) print(k-1 if ((k-1) | k) <= n else k-2)

xD

Divyesh_Patel + 1 comment brute force also works....

lsloan + 1 comment It may produce the correct answer, but always exceeds the execution time limit.

shiftmaker + 0 comments Thats precisely what happened to my code (Python 3) before I gave up and came here:

if

**name**== '**main**': t = int(input())`for t_itr in range(t): nk = input().split() #Set of numbers up 1 -> n n = int(nk[0]) #One more than valid maximum value A&B can be k = int(nk[1]) maxk = 0 for i in range(0,n-1): for j in range(i+1,n): curk = i&j if curk > maxk and curk < k: maxk = curk if maxk == (k - 1): break if maxk == (k - 1): break print (maxk)`

As a complete beginner; I do find it queer that you need to use bitwise OR to solve an exercise titled "bitwise AND"

sumba101 + 1 comment i dont understand this code. what is the logic here?

gvandam + 15 comments Let me try to explain.

Consider the following Given the task "A&B is the maximum possible and also

*less*than a given integer, K", the highest possible value to achieve is K-1So, let's try to achieve that highest value.

Also consider that, when using the AND-operation with a pair of values you can never get a value higher than the lowest value of that pair. Because to get a value higher than the lowest value, you would have to turn a zero-bit out of the lowest value into a one-bit, and it's impossible to turn zero-bits into one-bits by using AND.

So to achieve that highest value K-1, you need to find an even higher value, that in an AND-operation with K-1 results in K-1.

You want that higher value to be as close to K-1 as possible, so that you have the biggest chance of that higher value being within the limits of N. (remember, both values of A and B had to be from the set {1,2,3,...,N})

So, let's start with K-1 and turn that into a bits.

The lowest, higher number that gives K-1 in an AND operation is K-1 with the least-significant zero turned into a one.

*This is the key to this elegant solution.*Let's explain it with a few examples.

1001001 1001011 -------AND 1001001 1011111 1111111 -------AND 1011111 1011000 1011001 -------AND 1011000

So in cases where K-1 is even this leaves us with a very simple answer. Because K-1 is even, the last bit of K-1 is zero. Turning the least-significant zero turned into a one, is the same as adding one, and K-1+1 = K. So K-1 & K = K-1 in cases where K-1 is even. K is <= N by definition so you have an answer.

But when K-1 is odd, things start to get more complicated. Now you don't know at which position a zero will turn into a 1, so you don't know how big the lowest, higher number (that gives K-1 in an AND operation) will be. It can be 2 higher (with 0 at the 2nd place from the right) or 4 higher (with 0 at the 3nd place from the right) or 8, or 16, etc.

So you need to check if this lowest, higher number is still smaller or as big as N. If

*it is than K-1 is your answer*, if*it isn't than K-2 is your answer*.Why K-2? Well if K-1 is odd, than K-2 is even. Because K-2 is even, the last bit of K-2 is zero. Turning the least-significant zero turned into a one, is the same as adding one, and K-2+1 = K-1. So K-2 & K-1 = K-2 in cases where K-1 is odd K-1 is <= N by definition so you have an answer.

But how to get the lowest higher number? Well, as said, by turning least-significant zero into a one. And how do you do that? By using the OR-operation on K and K-1

Let's take the above examples and show that OR-ing the first value (K-1) with K, results in the second value, the value with the least significant zero turned into a one, being the lowest higher number that gives K-1 in and AND-operation

1001001 (K-1) 1001010 (K) -------OR 1001011 1011111 (K-1) 1100000 (K) -------OR 1111111 1011000 (K-1) 1011001 (K) -------OR 1011001 (K)

Note, that in the case where K-1 is even K-1 OR K = K

Because K <= N the condition (K-1 OR K <= N) is always true in cases where K-1

*is even*.In cases where K-1 is odd, the condition (K-1 OR K <= N) sometimes evaluates to false (the lowest higher number is bigger than N), in which case the answer is K-2. When it evaluates to true, the answer is K-1.

sumanthbalaji751 + 0 comments this is the best ever. thank you so much sir.

peg2191 + 0 comments Thank you! You explained it very well, and I think I get it (or most of it)

charliemeers + 0 comments Thanks for taking the time to explain that. It took some time but I finally get it. Cheers!

raghav_prakash + 0 comments Thanks a lot @gvandam! Your explanation was articulate and amazingly clear.

codertoaster + 0 comments Damn. If only I was good enough to understand your explanation. Time to get some pen and paper and do things manually.

rospvar + 1 comment Thank you for the explaination. I had to read twice to understand the concept completely. But now its clear.

rak_1225 + 2 comments I didnot understand. please explain me in detail with examples. Having known the fact that i am clear with the following truths.

when we perform AND operation between two integers, the result would be definitely less than or equal to the lowest number among the pair.

when we perform OR operation between two integers, the result would be definitely greater than or equal to the highest number among the pair.

please avoid using the variable k. instead use numbers to explain.

rospvar + 0 comments [deleted]rospvar + 11 comments Iâ€™ll try to explain this to my understanding and capacity.

S â€“ Set of numbers from 1 to N [Eg: 1,2,3â€¦N]

N â€“ The last number in the set

K â€“ Threshold number [i.e limit for the answer to be obtained] and this value can be K <= N

Since our answer should be < K, the possible answer would be <= K-1.

We know that while doing an AND operation between 2 numbers, the answer would be <= LOWEST NUMBER of those 2 numbers. And we need to find this LOWEST NUMBER which is <= K-1

So we need to find an AND pair which would result with our required answer.

**STEP 1:**Since K-1 is the**highest possible answer**, we will take it as one of the 2 numbers. The other number should be > K-1 due to the AND property and it would be >= K. Itâ€™s best to take a number whose binary equivalent is similar to K-1â€™s binary value. So K would be the best choice.Note: By doing an OR operation between 2 numbers, the answer would be >= HIGHEST NUMBER of the 2 numbers.

**STEP 2:**To find the other number we perform OR operation between the**highest possible answer**and the immediate larger number to it.i.e [(K-1) OR (K-1)+1] which is nothing but [(K-1) OR K] and its result would be >= K.

**STEP 3:**Now we got the AND pair which are K-1 and K (minimum possible result of the above OR operation) and our AND result would be <= K-1.For most cases we will get the final answer as K-1 itself but not for all cases.

**a)**When K is odd, the final answer will definitely be K-1 because if K is odd, K-1 will be even. Here only the LSB of the binary equivalent will be different. Eg: K=5(0101) ; K-1=4(0100)**b)**When K is even, K-1 will be odd and both number's binary values might not be similar. Eg: K=8(1000) ; K-1=7(0111)**c)**K-1 will be the answer only when the result of OR operation is <= N. If its > N, we would end up using a number which is not in the given number set for the AND operation which might result in a wrong final answer.So these cases occur when {(K-1 OR K) > N} and when K is even.

For these scenarios, the

**highest possible answer**would not be K-1 and it'll be the next lesser number K-2. The AND pairs for such scenarios would be K-2 and K-1 resulting with a final answer K-2.For the above cases, K-1 cannot be the

**highest possible answer**so we take next the lesser number K-2 as the**highest possible answer**and we start again from**STEP 1**replacing K-1 with K-2 and K with K-1.1.N=5, K=2 ; K-1 = 1 0010 2(K) 0001 1(K-1) -----OR---- 0011 3(OR result) 3 < N 0011 3(OR result) 0001 1(K-1) -----AND---- 0001 1(final answer) 2.N=8, K=5 ; K-1 = 4 0101 5(K) 0100 4(K-1) -----OR---- 0101 5(OR result) 5 < N 0101 5(OR result) 0100 4(K-1) -----AND---- 0100 4(final answer) 3.N=2, K=2 ; K-1 = 1 ; K-2 = 0 0010 2(K) 0001 1(K-1) -----OR---- 0011 3(OR result) 3 > N 0001 1(K-1) 0000 0(K-2) -----OR---- 0001 1(OR result) 0001 1(OR result) 0000 0(K-2) -----AND---- 0000 0(final answer) 4.N=21, K=20 ; K-1 = 19 ; K-2 = 18 10100 20(K) 10011 19(K-1) -----OR---- 10111 23(OR result) 23 > N 10011 19(K-1) 10010 18(K-2) -----OR---- 10011 19(OR result) 10011 19(OR result) 10010 18(K-2) -----AND---- 10010 18(final answer)

akashsuper2000 + 0 comments [deleted]kaustabh_sinha97 + 0 comments Really precise explanation. Thanks a lot!

amanpunethagehu + 0 comments thanks a lot . it helped me a lot

saikatd397 + 0 comments Awsm.

naik2191 + 0 comments Amazing explaination!!!!

Gokula_Prasanna + 0 comments Hello @rospvar, This is a beautifull explanation. Anyway I could able to understand after trying some handson in the problem. :)

rob_lounsbury + 1 comment Thanks for the detailed explaination, rospvar. I was able to implement this in Java and get test case 5 to pass in addition to 0 and 1 but cases 2, 3, and 4 still fail for me. The method below is the implementation which is given a score of 7.5. What I don't understand is why I get the correct answers for the other tests in my IDE but they won't pass on HackerRank. If there is a max time then, why doesn't HackerRank identify that as a requirement?

int minOr = (k - 1) | k;

`if (k % 2 != 0) { System.out.println(k-1); } else if (minOr < n) { System.out.println(k-1); } else { minOr = (k - 2) | (k - 1); if (minOr < n) { System.out.println(k - 2); } else { System.out.println(0); } }`

pavol_szegheo + 0 comments # Replace your code with this line:

System.out.println((((k - 1) | k) > n && k % 2 == 0) ? k - 2 : k - 1);

narasimhamurthy9 + 0 comments Good explaination! , Thank you

MrFantastic05 + 0 comments thanks your piece of info was even more accurate

priyanshi1142ag1 + 0 comments Great Explanation. Thank you so much.

lovedampeter + 0 comments Wow! This is mind-blowing. Thank you for the explanation.

mmughees_bscs161 + 0 comments I still don't understand the question. What does it mean by highest number of A&B and why do you want to put the least significant digit to be equal to 1 not zero as by adding 1 to k-1 or 1 with k-2

M_salam + 0 comments Nice and systematic explanation. your spending time in typing so much is appreciated!

embahsi + 0 comments Best explanation! Thank you for your time.

Jophins + 0 comments Thank you so much. :)

deepak21mudila11 + 0 comments detailed and nice explanation...

sauravsahu2009 + 0 comments Excellent explanation. Thanks for sharing !

MrFantastic05 + 0 comments thanks man

Sonu_22 + 0 comments Thankyou very much sir . you made it too easy.

lincolndu + 0 comments PHP simple solution

<?php $handle = fopen ("php://stdin","r"); fscanf($handle,"%d",$t); for($a0 = 0; $a0 < $t; $a0++){ fscanf($handle,"%d %d",$n,$k); $res = ( (($k-1)|$k) > $n && $k%2 == 0) ? $k-2 : $k-1; echo $res. "\n"; }

sravyarangavajj1 + 1 comment Can you plss explain me this code?

lincolndu + 0 comments You can see the explanation

https://www.hackerrank.com/challenges/30-bitwise-and/forum/comments/307234

tuyendev + 0 comments thanks bro . Your solution is best :)

sagarpant74 + 0 comments best soln. best soln

meonly336 + 0 comments such a beauty...

keithyjohnson + 0 comments [deleted]malayhalder70 + 0 comments just Brilliant when i understand

tianpeida_cuhk + 0 comments How can we show that if (k-1) | k > n, then there is no way to obtain k-1?

cedarmora + 0 comments BF solution == Basic Feasible Solution

Please describe acronyms when you use them so that beginners can understand what you are saying. Thank you for the excellent solution.

Vonfock + 1 comment I love that each challenge is opening me up to new concepts I hadn't encountered before. This was my brute force attempt but times out on 2, 3 and 4

from itertools import combinations for a0 in range(t): n,k = input().strip().split(' ') n,k = [int(n),int(k)] print (max([a&b for a,b in combinations(range(1,n+1), 2) if a&b < k]))

dm_dubovitsky + 0 comments you forgot the case this 'k' returning

MaxNRG + 0 comments Brilliant! So elegant :)

jafkm7 + 0 comments The whole point of this was to use bitwise AND, but I don't see any bitwise operations in your solution at all.

def getAnswer(n, k): power = int(log(n, 2)) - 1 floor = 2**power maxNum = 0 for i in range(floor+1, n+1): for j in range(1, i): test = i&j if test > maxNum and test < k: maxNum = test if maxNum == k-1: break return maxNum

This is ugly and I hate it, but it does at least match the requirements of the problem and arrives at the solution within the allotted time for all test cases.

maxvetrov555 + 0 comments We can use print without if:

print(k-1-int((k-1|k)>n))

shantanu_dwvd + 0 comments Brute force solutions works here.

el71Gato + 2 comments Your solution passes all the tests. But it would fail on

`k > n`

, for example`k = 8, n = 5`

must end up in 4, but in 7 it does. Moderators should add such a test. So the better solution is:for _ in range(int(input())): n, k = map(int, input().split()) print( (k-1 if (k-1)|k <= n else k-2) if k <= n else (n-1) & -2 )

lsloan + 0 comments Or, on the line before the print statement, put:

k = k if (k <= n) else n

joshi_niraj1996 + 0 comments Have another look at problem constraints. It clearly states that k is always less than or equal to n.

karlo_ijc + 0 comments I spent several hours concocting my solution. It worked; howerver, whean I saw this solution I was taken aback in awe. So much beauty! Kudows on that!

Spleen + 0 comments Wow really impressive !

rahultiwari_2011 + 0 comments Beautiful ! Nice Brain..

lsloan + 0 comments While this solution works and this forum has good explanations of why it works, the results don't make sense if the value entered for

`k`

is greater than the value for`n`

.Of course, many will say the constraints include "2 â‰¤

`k`

â‰¤`n`

". That's what we should expect in the input. So that's what the solutions are designed to work with. But what should the code do when`k`

>`n`

?I think the code should check that the values are within reason and either give an error or do something appropriate. In the case of this specific problem,

`k`

is supposed to be the upper limit of the number to be found. I think it's acceptable to set`k`

equal to`n`

and continue the program as before.I wonder why HackerRank doesn't include bad data in its tests. The ability to code a solution to a problem isn't an accurate representation of real world coding. Solutions should be able to handle bad data as well. I think that by not including this in challenges, new coders may not learn to write fault-tolerant code.

90ramamca + 0 comments I tried in brute force , some testcases failed to due to timeout, your solution made my job easier.

my bruteforce solution: from itertools import combinations

def print_max_bitwise_and(n, k): result = 0 max_ = 0 for i, j in combinations(range(1, n+1),2): result = i&j if result < k and max_<result: max_ = result print(max_)

saiyanPride + 3 comments Instead of having to test various combinations of A & B, once can simply determine the result with knowledge of the value of the last digit of k.

*Thought Process: Always strive to see if k-1 can be achieved, if not then try k-2 and so on. This is because the maximum value less than k is k-1, but (k-1) will only be valid if it can be formed via A&B*### Here it goes:

`(I) If k ends with 1, then the result is (k-1) In this case k-1 can always be formed by switching off the last digit of k, where k is .......1`

(II) If k ends with 0, and is of form 2^m i.e. a power of 2 then result is (k-1) or (k-2). Let k=2^m If (2^{m+1})-1 is in the range, then result is (k-1). In this case B=(2^{m+1})-1 and A=k-1

`else, result is (k-2). (k-2) is always guaranteed as it is the precursor of a binary number that ends with a 1, see (I)`

(III) The last possible case is where k ends with 0, and is not a power of 2. Again the result is either (k-1) or (k-2)

If the number obtained by switching on the rightmost 0 of (k-1) is the range, then that number can be bitwise multiplied by k-1 to give (k-1). Otherwise result is (k-2). (k-2) is always guaranteed as it is the precursor of a binary number that ends with a 1, see (I) & (II)

see code: https://github.com/niranfor1/superQuantHackerrank/blob/master/30DaysOfCodeBitwiseAND.cpp

jmjiru + 4 comments Could you put this into regular code or even pseudocode because I don't understand it

saiyanPride + 0 comments [deleted]saiyanPride + 0 comments [deleted]saiyanPride + 0 comments [deleted]saiyanPride + 1 comment see my code, not sure I intended it for public viewing when initially written. However, I've included a clearer explanation: https://github.com/saiyanPride/superQuantHackerrank

lordoflords + 0 comments awesome. your github explanation is very neat. Good job.

lordoflords + 1 comment nice explanation. Thanks. But in no III it should be swiitching on the rightmost 0 to 1 of (k-1) and not 'SWITCHING ON RIGHTMOST 1'

saiyanPride + 0 comments You're absolutely right, I made a typo

_Tatsu + 0 comments For me it is the best straightforward explanation among the theads. Thank you.

lemmings125 + 1 comment i solved this problemi in O(n^2) but on reading the editorial the problem setters code solved this in constant time using the bitwise NOT and bitwise OR operator.

It works and solves correctly when a set contains the numbers as detailed in the constraints {1,2,3 ... N} but how do coders come up with these algorithms.

I want to advance my coding skills but I would never have found a solution like that, it makes sense when I code it or put it on pen and paper and use binary but how are these algorithms found ???

coding_rj + 0 comments An advanced understanding of binary arithmetic, I would think. Unfortunately, such cannot be imparted by coding exercises.

surendermca04 + 4 comments My Answer is :

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int k = in.nextInt(); int finalResult = 0; for(int i = 1; i < n ; i++){ for(int j = i+1; j <= n ; j++){ int amp = i&j; if(amp < k && amp > finalResult) finalResult = amp; } } System.out.println(finalResult); } }`

bhuvanshukla + 3 comments I did the same code in c++ but my answer isn't accepted for case 2,3,4.

bhuvanshukla + 1 comment and when i downloaded case 4 answer after spending 5 hackos and run with custom output it gives correct output but yet its saying it as wrong answer

Phyma + 0 comments Hey! This is way old. But dont forget that n is also part of the solution so you have <= n and not < n.

jpoff + 1 comment Same is happening for me with Java code. My code matches surendermca04's code almost completely and I'm still getting it "wrong" on cases 2 3 and 4 - even though output has been checked line-for-line for correctness.

andyjungyang + 0 comments I got it wrong on case 2,3, and 4 too but I had "for (int i = 0" instead of "for (int i = 1"

arunchavan89 + 1 comment c++

void max_possible_value(int n , int k) { int temp = 0; for (int i = 1; i < n; i++) { for (int j = (i+1); j <= n; j++) { int result = i&j; if((result > temp)&&(result < k)) { temp = result; } } } std::cout<< temp<<std::endl; }

pavol_szegheo + 0 comments # Or replace your code with this line:

void max_possible_value(int n , int k) { std::cout << ((((k - 1) | k) > n && k % 2 == 0) ? k - 2 : k - 1) << std::endl; }

bryon_nicoson + 4 comments hmmm. this code passes all five tests and looks nearly identical to yours?

Scanner in = new Scanner(System.in); int t = in.nextInt(); for (int i = 0; i < t; i++) { int max = 0; int n = in.nextInt(); int k = in.nextInt(); for (int a = 1; a < n-1; a++) { for (int b = a+1; b <= n; b++) { int val = a&b; if (val > max && val < k) max = val; } } System.out.println(max); }

bryon_nicoson + 1 comment But, thanks to Jekus' post above, here's a much more efficient solution:

Scanner in = new Scanner(System.in); int t = in.nextInt(); for (int i = 0; i < t; i++) { int n = in.nextInt(); int k = in.nextInt(); if ((k-1 | k) <= n) { System.out.println(k-1); } else { System.out.println(k-2); } }

Dishant_ + 0 comments Thanks... bryon_nicoson

abhaynayar + 0 comments [deleted]abhaynayar + 0 comments Shouldn't it be

for (int a = 1; a < n; a++)

Instead of

for (int a = 1; a < n-1; a++)

pavol_szegheo + 0 comments # Or replace your code with this:

Scanner in = new Scanner(System.in); int t = in.nextInt(); for (int i = 0; i < t; i++) { int max = 0; int n = in.nextInt(); int k = in.nextInt(); std::cout << ((((k - 1) | k) > n && k % 2 == 0) ? k - 2 : k - 1) << std::endl; }

Coderaulix + 0 comments [deleted]ruwhan1 + 0 comments seems happened with me as well, I've download case #4 for 5 hackos.

dgodfrey + 1 comment I just did a stupid sloppy brute-force solution that goes through every pair of (A,B). I know there are better solutions that use a bunch of subtraction/addition/and bitwise and hex codes. But this is the best I could do:

for (int p = 0; p < t; ++p) { int max = 0; cin >> n >> k; for (int i = 1; i < n; ++i) { for (int j = i+1; j <= n; ++j) { if ((i&j) > max && (i&j) < k) max = (i&j); } } cout << max << '\n'; }

n_panev + 1 comment Your first loop can be changed to:

for(int i = 1; i < k; i++)

because A&B <= min(A,B)

b170030114 + 0 comments i want code in c

Sort 201 Discussions, By:

Please Login in order to post a comment