Day 29: Bitwise AND
Day 29: Bitwise AND
+ 28 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.
+ 3 comments And we conclude this challenge with expecting people to know yet another algorithm in order to pass the time constraints, with a useless tutorial covering only the basic concept and no direction on where to go to learn what's needed to accomplish the complex aspect, other than cheating by looking in the discussion. Between that and the chaotic order of complexity in the other tutorial sections, it's no wonder people suggest other coding challenge websites instead. If I were a beginner, I would have been lost a long time ago.
+ 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
+ 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 ???
+ 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); } }
Sort 365 Discussions, By:
Please Login in order to post a comment