Largest Combination With Bitwise AND Greater Than Zero

MediumArrayHash TableBit ManipulationCounting

Solution

export function largestCombination(candidates: number[]): number {
  const MAX_SIZE = 10e7;
 
  let answer = 0;
  for (let bit = 1; bit < MAX_SIZE; bit <<= 1) {
    let count = 0;
    for (const candidate of candidates) {
      if ((candidate & bit) !== 0) {
        count += 1;
      }
    }
    answer = Math.max(answer, count);
  }
  return answer;
}

Complexity

  • Time: O(NlogM)
    • M: candidates가 가질 수 있는 가장 큰 값, 문제에서는 10^7
  • Space: O(1)