2275. Largest Combination with bitwise and greater than zero

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1. Also, for nums = [7], the bitwise AND is 7. You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

Return the size of the largest combination of candidates with a bitwise AND greater than 0.

## code

import os
import logging
import traceback
import datetime
from typing import List


def get_logger(LEVEL: str = "INFO") -> logging.Logger:
    logger = logging.getLogger("custom_logger")
    logger.setLevel(getattr(logging, LEVEL.upper(), logging.INFO))
    stream_handler = logging.StreamHandler()
    formatter = logging.Formatter(
        fmt="[%(asctime)s %(levelname)s] %(message)s", datefmt="%Y/%m/%d %H:%M:%S"
    )
    stream_handler.setFormatter(formatter)
    if logger.hasHandlers():
        logger.handlers.clear()
    logger.addHandler(stream_handler)
    return logger


def sol(problem_num, func):
    script_dir = os.getcwd()  # os.path.dirname(os.path.abspath(__file__))
    path = script_dir + f"\\txt\\{problem_num}" + ".txt"

    try:
        with open(path, "r") as getter:
            line_count = 1
            while True:
                line = getter.readline()
                if not line:
                    logger.info("EOF")
                    break
                try:
                    inp, oup = line.strip().split()

                    ############## WARNING :input output fitti
                    inp = list(map(int, inp.split(",")))
                    oup = int(oup.strip())
                    ##############

                    if not func(inp) == oup:
                        raise ValueError(f"wrong output in line : {line}")
                    logger.info(f"{line_count} : {inp} : {oup == func(inp)}")
                    line_count += 1

                except Exception as e:
                    logger.error(traceback.format_exc())
                    logger.info(f"FINISHED WITH ERROR IN {line_count}")
                    line_count += 1

    except FileNotFoundError:
        logger.error(f"File not found: {path}")
    except Exception as e:
        logger.error(f"Error opening file: {e}")
        logger.error(traceback.format_exc())


class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        max_number = 10**7
        bit_len = max_number.bit_length()
        bit_counts = [0] * (bit_len)

        for num in candidates:
            for i in range(24):
                if num & (1 << i):
                    bit_counts[i] += 1
        return max(bit_counts)


problem_num = 2275
global logger
logger = get_logger("info")
sol(problem_num, Solution().largestCombination)

[2024/11/07 13:40:18 ERROR] Traceback (most recent call last):
  File "C:\Users\WAI\AppData\Local\Temp\ipykernel_49372\407775703.py", line 45, in sol
    raise ValueError(f"wrong output in line : {line}")
ValueError: wrong output in line : 16,17,71,62,12,24,14 3


[2024/11/07 13:40:18 INFO] FINISHED WITH ERROR IN 1
[2024/11/07 13:40:18 ERROR] Traceback (most recent call last):
  File "C:\Users\WAI\AppData\Local\Temp\ipykernel_49372\407775703.py", line 45, in sol
    raise ValueError(f"wrong output in line : {line}")
ValueError: wrong output in line : 8,8 1

[2024/11/07 13:40:18 INFO] FINISHED WITH ERROR IN 2
[2024/11/07 13:40:18 INFO] EOF

bitsiwe counting

Biotmask, counting을 개념을 결합해서 푸는 문제라고 볼 수 있다. bitwise 연산을 활용해 부분집합이나 조합을 빠르게 계산해야하는 경우에 유용한 접근이다.

비트마스크 활용 : 비트마스크는 각 숫자를 비트 단위로 다루어 효율적으로 정보(특정 비트가 1 0) 저장하고, 연산을 수행한다.

카운팅 최적화 : 비트 위치별로 1의 빈도를 카운팅함으로써, 전체 조합을 계산하지 않고도 가장 큰 조합의 크기를 찾는 방식이다. 각 비트가 어떤 숫자에서 1로 설정되는지 카운팅하여, 최대 조합크기를 결정한다. 직접 계산하지 않고 다른 것을 하면 결론적으로 해당 계산이 되는 방식으로 푸는 방식…!