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;
}2220. Minimum Bit Flips to Convert Number
주어진 값 start를 몇번 비트플립해야 goal이 되는지 구하기
Input: start = 10, goal = 7
Output: 3
https://leetcode.com/problems/minimum-bit-flips-to-convert-number/
O(n)
int minBitFlips(int start, int goal){
int ret = 0;
while (start > 0 || goal > 0) {
if ((start & 1) != (goal & 1))
ret++;
start >>= 1;
goal >>= 1;
}
return ret;
}476. Number Complement
주어진 값의 비트를 반대로 플립하여 출력
For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.https://leetcode.com/problems/number-complement/
int findComplement(int num){
int cnt = (num >> 1);
unsigned int bit_mask = 1;
while (cnt != 0) {
bit_mask <<= 1;
bit_mask += 1;
cnt >>= 1;
}
return ~num & bit_mask;
}762. Prime Number of Set Bits in Binary Representation
left부터 right 까지의 각 값들의 이진수 1의 갯수가 소수인것들의 총 갯수.
Input: left = 6, right = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
8 -> 1000 (1 set bit, 1 is not prime)
9 -> 1001 (2 set bits, 2 is prime)
10 -> 1010 (2 set bits, 2 is prime)
4 numbers have a prime number of set bits.https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/
1 <= left <= right <= 10^6 이므로 각 값의 비트수는 최대 25개.
bool is_prime(int a)
{
if (a == 2 || a == 3 || a == 5 || a == 7 ||
a == 11 || a == 13 || a == 17 || a == 19 || a == 23)
return true;
return false;
}
int count_one(int a)
{
int ret = 0;
while (a != 0) {
if ((a & 1) == 1)
ret++;
a >>= 1;
}
return ret;
}
int countPrimeSetBits(int left, int right){
int ret = 0;
for (int i = left; i <= right; i++) {
if (is_prime(count_one(i)))
ret++;
}
return ret;
}868. Binary Gap
주어진 값의 이진수에서 1과 1의 사이가 가장 큰 값 리턴.
Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.https://leetcode.com/problems/binary-gap/
int binaryGap(int n){
int max = 0, cnt = 0;
int prev = -1, next = 0;
while (n != 0) {
if (n & 1 == 1) {
if (prev == -1) {
prev = cnt;
next = cnt;
} else {
prev = next;
next = cnt;
}
if (next - prev > max)
max = next - prev;
}
cnt++;
n >>= 1;
}
return max;
}191. Number of 1 Bits
주어진 수에서 비트 1세기
https://leetcode.com/problems/number-of-1-bits/
int hammingWeight(uint32_t n) {
int ret = 0;
while (n != 0) {
if ((n & 1) == 1)
ret++;
n >>= 1;
}
return ret;
}67. Add Binary
두 이진수 문자열을 더하고 문자열로 리턴하는 프로그램을 작성하기
Input: a = "1010", b = "1011"
Output: "10101"https://leetcode.com/problems/add-binary/
char * addBinary(char * a, char * b){
int idxa = strlen(a) - 1;
int idxb = strlen(b) - 1;
int lcnt = idxa > idxb ? idxa: idxb;
char *r = (char *)malloc(sizeof(char) * (lcnt + 3));
char *f = (char *)malloc(sizeof(char) * (lcnt + 3));
int bita, bitb;
int ret = 0;
r[0] = '\0';
r[1] = '0';
int retcnt = 1;
while (lcnt-- >= 0) {
bita = idxa >= 0 ? a[idxa--] - '0': 0;
bitb = idxb >= 0 ? b[idxb--] - '0': 0;
ret = bita ^ bitb ^ (r[retcnt] - '0');
if ((bita + bitb + (r[retcnt] - '0')) > 1)
r[retcnt + 1] = (1 + '0');
else
r[retcnt + 1] = '0';
r[retcnt++] = (ret + '0');
}
if (r[retcnt] == '0')
retcnt--;
int fcnt = retcnt;
for (int i = 0; i < retcnt + 1; i++)
f[fcnt--] = r[i];
return f;
}693. Binary Number with Alternating Bits
인접한 두 비트가 모두 서로 다르면 true 같으면 false
https://leetcode.com/problems/binary-number-with-alternating-bits/
bool hasAlternatingBits(int n){
if (n == 1) return true;
int curr;
int prev = n & 1;
n >>= 1;
while (n != 0) {
curr = n & 1;
if (prev == curr)
return false;
prev = n & 1;
n >>= 1;
}
return true;
}231. Power of Two
주어진 값이 2의 배수이면 true 아니면 false리턴.
https://leetcode.com/problems/power-of-two/
Input: n = 16
Output: true
Explanation: 24 = 16bool isPowerOfTwo(int n){
unsigned int cmp = 1;
if (n < 1)
return false;
for (int i = 0; i < 32; i++) {
if (cmp == n)
return true;
cmp <<= 1;
}
return false;
}342. Power of Four
주어진 값이 4의 배수이면 true 아니면 false리턴.
https://leetcode.com/problems/power-of-four/
위 문제에서 cmp <<= 1; 를 cmp <<= 2;로만 변경.
bool isPowerOfFour(int n){
unsigned int cmp = 1;
if (n < 1)
return false;
for (int i = 0; i < 32; i++) {
if (cmp == n)
return true;
cmp <<= 2;
}
return false;
}