Minimum One Bit Operations to Make Integers Zero

Minimum One Bit Operations to Make Integers Zero

Minimum One Bit Operations to Make Integers Zero - LeetCode

- 문제 내용 : 주어진 숫자를 0으로 만들어라. 단 다음 Rule에 따른다.

1. Binary로 가장 우측의 자리만 1또는 0으로 변화 시킬 수 있다.
2. i번째 자리를 변화 시키기 위해서는 i+1번째 자리가 1이여야 하고, i+2번째 부터 그 뒤 모든 값은 0이어야 한다.

- 접근 방법

주어진 Rule에 따라 하기 값에서는 몇번의 변환에 따라 0이 가능한지 점검해 보자.

n = 1

1. 01
2. 00 -> 1번 룰 사용

n = 2

1. 10
2. 11 -> 1번
3. 01 -> 2번
4. 00 -> 1번

n = 3

1. 11
2. 01 -> 2번
3. 00 -> 1번

n = 4

1. 100
2. 101 -> 1번
3. 111 -> 2번
4. 110 -> 1번
5. 010 -> 2번
6. 011 -> 1번
7. 001 -> 2번
8. 000 -> 1번

n = 8

1. 1000
2. 1001 => 1번
3. 1011 => 2번
4. 1010 => 1번
5. 1110 => 2번
6. 1111 => 1번
7. 1101 => 2번
8. 1100 => 1번
9. 0100 => 2번
10. 101 -> 1번
11. 111 -> 2번
12. 110 -> 1번
13. 010 -> 2번
14. 011 -> 1번
15. 001 -> 2번
16. 000 -> 1번

상기 n == 8의 경우는 9번 부터 16번까지는 n == 4인 경우의 수를 그대로 사용하고 있다.

이를 바탕으로 1 + 0000 형태의 값은 다음과 같은 횟수로 나타낼 수 있음을 알 수있다.

• (2^length) -1

즉 8은 길이가 4임으로 16 - 1 15가지 경우의 수가 나올 수 있다.

4인 경우는 길이가 3임으로 8 - 1 7가지 경우의 수가 가능하다.

2인 경우는 4-1 3가지 경우의 수가 가능하다.

그럼 만약에 1+000 형태가 아니라 1+XXX 형태는 어떻게 처리 해야하는가?

아래 경우를 보자.

n = 2

1. 10
2. 11 -> 1번
3. 01 -> 2번
4. 00 -> 1번

n = 3

1. 11
2. 01 -> 2번
3. 00 -> 1번

비록 3이 2보단 크지만 변화 횟수로는 3이 2보다 하위이다. 즉 2는 3번의 변화기 필요 하지만 3은 2번의 변화만 필요하다.

1. 11 -> 1번
2. 01 -> 2번
3. 00 -> 1번

2가 0으로 변해가는데 있어서 3은 지나가는 순서인 것이다.

이 순서의 값을 빼는 방법은 다음과 같다.

n=3으로 주어졌을 경우

10 과 01로값을 분리 할 수있다.

10은 3번의 변화가 필요하고

01은 1번의 변화만 처리 하면된다.

즉 3번 - 1번 = 2번

의 변화로 처리 가능하다. 

n이 10인 경우를 한번더 생각해 보자.

10은 '1010'으로 표시가 가능하다.

이는

1000 과 10으로 분리가 가능하다

1000이 0이 되기 위한 수는 2^4 - 1 = 15회

10은 2^2 -1 = 3회

정답은 15회 - 3회이다.

만약 1011이라면 어떨까?

1000과 10 그리고 1로 구성이 된다.

1000이 되기 위한 수는 15회

10이 되기 위한 수는 3회

1이 되기 위한 수는 1회이다.

이때는 뒤에서 부터 생각해야 한다.

11이 0이 되기 위한 횟수는 10과 1임으로 3-1로 2회이다.

15 - (3 - 1) = 13회이다.

즉 '큰값 - (다음 작은값 - (그다음작은값 - 그다음 작은값))' 이런 식으로 계산을 처리 해줘야한다.

이를 풀어보면 '큰값 - 다음작은값 + 그다음 작은값 - 그다음 작은값' 식으로 기호를 변화 시켜줘야 한다.

이를 코드로 나타내면 다음과 같다.

var minimumOneBitOperations = function(n) {
    let bits = n.toString(2).split('');

    if(bits.length === 0) return 0;
    if(bits.length === 1){
        if(bits[0] === '0') return 0;
        else return 1;
    }

    let motherNum = getCount(bits.length);

    let childNum = 0;
    let swit = true;
    for(let i = 1; i < bits.length; i++){
        if(bits[i] === '1' && swit){
            childNum += getCount(bits.length - i);
            swit = !swit;
        } else if(bits[i] === '1' && !swit){
            childNum -= getCount(bits.length - i);
            swit = !swit;
        }
    }

    return motherNum - childNum;

    function getCount(len){
        return Math.pow(2,len) - 1;
    }

};

상기와 같은 코드는 bit Operator를 사용해서 다음과 같이 변화 시킬 수 있다.

• 대상 : 10000의 횟수는?
• 일반식 : 2^length - 1
• Bitopertator : 입력값 xor 입력값 -1 = 10000 xor 10000 - 1 = 10000 xor 01111 

Bitoperator를 사용할 경우 이점은 '11000'과 같은 경우도 가장 우측에 있는 1000에 대한 횟수만 얻어 낼 수 있다는 것이다.

• 11000 xor 10111 = 01111 = 15 = 2^4 - 1

해당 계산을 완료 한후 1000을 삭제하는 Bitoperator는 다음과 같다.

• 입력값 and 입력값 -1 = 11000 and 10111 = 10000

상기와 같은 방법으로 코드를 수정할 경우 다음과 같이 짧아 질 수 있다.

var minimumOneBitOperations = function(n) {
    let result = 0;
    let sign = +1;

    while (0 < n) {
        result += (n ^ (n-1)) * sign;
        n = n & (n-1);
        sign = sign * -1;
    }
    return Math.abs(result);

};

마지막의 abs의 이유는 1의 갯수가 홀 수개이면 가장 큰 값이 마이너스가 되는데 이를 방지하기 위한 용도다.