• + 13 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)
    
    • + 0 comments

      Really precise explanation. Thanks a lot!

    • + 0 comments

      thanks a lot . it helped me a lot

    • + 0 comments

      Awsm.

    • + 0 comments

      Amazing explaination!!!!

    • + 0 comments

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

    • + 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);
      
              }
      
          }
      
      • + 1 comment

        Replace your code with this line:

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

        • + 0 comments

          Awsome!

    • + 0 comments

      Good explaination! , Thank you

    • + 0 comments

      thanks your piece of info was even more accurate

    • + 0 comments

      Great Explanation. Thank you so much.

    • + 0 comments

      Wow! This is mind-blowing. Thank you for the explanation.

    • + 0 comments

      thank you for the explanation helped a lot

    • + 0 comments

      Thank you for such fantastic explanation.