Day 29: Bitwise AND

Task 
Given set . Find two integers,  and  (where ), from set  such that the value of is the maximum possible and also less than a given integer, . In this case,  represents the bitwise ANDoperator.

Input Format

The first line contains an integer, , the number of test cases. 
Each of the  subsequent lines defines a test case as  space-separated integers,  and , respectively.

Constraints

Output Format

For each test case, print the maximum possible value of  on a new line.

Sample Input

3
5 2
8 5
2 2

Sample Output

1
4
0

Explanation

 

All possible values of  and  are:

The maximum possible value of  that is also  is , so we print  on a new line.

풀이

처음에 문제가 이해가 안되었는데 '비트단위 연산자' 라고 검색해보면 좀 더 기본적인 설명이 나오니 참고해보자.

시간복잡도로 봤을 때 문제를 풀긴했지만 그리 좋은 풀이는 아닌 거 같다.

dicussion 에 나와있는 코드는 아직 온전히 이해가 안되서 다 이해하면 풀이글을 써봐야 할 듯...

package Day29;

import java.util.Scanner;

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 max = 0;
            int n = in.nextInt();
            int k = in.nextInt();
            for (int i = 1; i < n - 1; i++) {
                for (int j = i + 1; j <= n; j++) {
                    int newVal = i & j;
                    if (newVal > max && newVal < k)
                        max = newVal;
                }
            }
            System.out.println(max);
        }
    }
}

다른 사람 풀이

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);               
            }
        }
    }
}

어찌되었건 30일간의 여정?이 끝났다 ㅎㅎㅎ

Hacker Rank의 경우 알고리즘이나 자료구조뿐 아니라 FP(Fuctional Programming)이나 AI, 그리고 통계 등 괜찮은 자료들이 많기 때문에 계속해서 풀어볼 생각이다.