Leetcode - Bit Manipulation 문제 및 풀이

Leetcode - Bit Manipulation 문제 난이도 순서대로 풀기. 문제와 풀이는 푸는대로 하단에 계속 업데이트.

1720. Decode XORed Array

https://leetcode.com/problems/decode-xored-array/
encoded[i] = arr[i] XOR arr[i + 1] 이렇게 계산된다고 할때 encoded[] 와 arr[0] 값이 주어졌을때, 오리지널 arr[] 배열을 구하라.

Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]

int* decode(int* encoded, int encodedSize, int first, int* returnSize){
    *returnSize = encodedSize + 1;
    int *ret = (int *)malloc(sizeof(int) * (*returnSize));
    ret[0] = first;
    
    for (int i = 0; i < encodedSize; i++)
        ret[i + 1] = encoded[i] ^ ret[i];
    
    return ret;
}

1342. Number of Steps to Reduce a Number to Zero

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/
주어진 값이 짝수면 2로 나누고 홀수면 -1 을 할때 몇단계를 거치면 0이 되는가?

int numberOfSteps(int num){
    int cnt = 0;
    while (num) {
        if ((num & 1) == 1)
            num = num - 1;
        else
            num = num >> 1;
        cnt++;
    }
    return cnt;
}

1486. XOR Operation in an Array

배열의 모든 값을 ^ 연산하라는 문제.

https://leetcode.com/problems/xor-operation-in-an-array/

int xorOperation(int n, int start){
    int ret = 0;
    for (int i = 0; i < n; i++)
        ret = ret ^ start + 2 * i;
    return ret;
}

1684. Count the Number of Consistent Strings

주어진 문자열 배열에서 허용된 문자로만 구성된 문자열은 몇개인지?
Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2

https://leetcode.com/problems/count-the-number-of-consistent-strings/

int countConsistentStrings(char * allowed, char ** words, int wordsSize){
    int ret = 0;
    int table[27] = {0,};
    int na = 0;
    
    while (*allowed != '\0') {
        table[*allowed++ - 97] = 1;
    }
    
    for (int i; i < wordsSize; i++) {
        na = 0;
        while (*words[i] != '\0') {
            if (table[*words[i]++ - 97] == 0)
                na = 1;
        }
        if (!na)
            ret++;
    }
    return ret;
}

461. Hamming Distance

주어진 두 값의 2진수에서 각 자리의 값이 서로다른 갯수 구하기
https://leetcode.com/problems/hamming-distance/

int hammingDistance(int x, int y){
    int diff = 0;
    for (int i = 0; i < 32; i++) {
        if ((x & 1) != (y & 1))
            diff++;
        x = x >> 1;
        y = y >> 1;
    }
    return diff;
}

338. Counting Bits

n 값이 주어졌을때, 0 ~ n 의 숫자의 2진수에서 1의 갯수를 구하고 배열로 리턴하기

Input: n = 5 Output: [0,1,1,2,1,2]
Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

https://leetcode.com/problems/counting-bits/

O(n log n)

int* countBits(int n, int* returnSize){
    *returnSize = n + 1;
    //int *ret = (int *)malloc(sizeof(int) * *returnSize);
    int *ret = (int *)calloc(*returnSize, sizeof(int));
    for (int i = 0; i <= n; i++) {
        int bitval = i;
        while (bitval != 0) {
            if ((bitval & 1) == 1)
                ret[i]++;
            bitval = bitval >> 1;
        }
    }
    return ret;
}

O(n)

DP로 해결 점화식 : ret[n] = 1 + ret[n - a]
아래와 같은 규칙을 통해서 점화식 도출 a는 2의 배수 값이고 2진수의 자릿수의 첫번째 수에 해당하는 값임 (1 10 100 1000 ...)
재미있는 문제였음. discussion보면 더 빠른 방법으로 점화식을 도출했던데 나는 다른방식으로 점화식을 세워봤음.

0000 ret[0] = 0
0001 ret[1] = 1 + ret[1 - 1]
0010 ret[2] = 1 + ret[2 - 2]
0011 ret[3] = 1 + ret[3 - 2]
0100 ret[4] = 1 + ret[4 - 4]
0101 ret[5] = 1 + ret[5 - 4]
0110 ret[6] = 1 + ret[6 - 4]
0111 ret[7] = 1 + ret[7 - 4]
1000 ret[8] = 1 + ret[8 - 8]
1001 ret[9] = 1 + ret[9 - 8]
1010 ret[10] = 1 + ret[10 - 8]
...
1111 ret[15] = 1 + ret[15 - 8]

int* countBits(int n, int* returnSize){
    *returnSize = n + 1;
    int *ret = (int *)calloc(*returnSize, sizeof(int));
    ret[0] = 0;
    if (n == 0)
        return ret;
    for (int i = 1; i <= n; i++) {
        int a = 1;
        for (int val = i; val > 1;) {
            val >>= 1;
            a <<= 1;
        }
        ret[i] = 1 + ret[i - a]; 
    }
    return ret;
}

1356. Sort Integers by The Number of 1 Bits

주어진 배열이 2진수에서 1의 갯수로 오름차순 정렬하기.
Input: arr = [0,1,2,3,4,5,6,7,8] Output: [0,1,2,4,8,3,5,6,7]
https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/

O(n log n)

qsort() 사용해 구현, integer 수가 크지 않기 때문에 비트연산하는 것은 상수시간이라 가정하면 퀵소트 n log n 의 시간복잡도를 갖음.

int count_bit(int val)
{
    int ret = 0;
    while (val != 0) {
        if (val & 1 == 1)
            ret++;
        val >>= 1;
    }
    return ret;
}

int cmp(const void *a, const void *b)
{
    int ca = count_bit(*(int *)a);
    int cb = count_bit(*(int *)b);
   
    if (ca == cb)
        return *(int *)a - *(int *)b;
    else 
        return  ca - cb;
}

int* sortByBits(int* arr, int arrSize, int* returnSize){
    *returnSize = arrSize;
    qsort(arr, arrSize, sizeof(int), cmp);
    return arr;
}

136. Single Number

주어진 배열의 요소가 같은값이 두개씩 있는데, 딱 한 값만 하나만 존재. 그 값을 찾아라.
https://leetcode.com/problems/single-number/

O(n)

답은간단한데 의외로 생각을 많이 한 문제. 재미있었다.
각 비트를 더할때 자릿수를 carry하지 않으면 중복된 수는 제거되고 독립된 수만 남게 되는 성질을 우선 발견했고.
모든 값의 각 비트를 자릿수 배열에 나눠서 저장하려고 했으나,
이 성질이 XOR 이라는 사실을 마침내 떠올리고 쉽게 해결.

int singleNumber(int* nums, int numsSize){
    int ret = 0;
    for (int i = 0; i < numsSize; i++)
        ret ^= nums[i];
    return ret;        
}