Largest Combination With Bitwise AND Greater Than Zero
Updated
Problem statement
You are given an array nums of positive integers. Choose some of its elements (at least one, each index at most once) so that the bitwise AND of all chosen elements is greater than 0.
Return the largest number of elements you can choose. Equal values at different indices are different elements.
Function
largestCombination(nums: int[]) → intExamples
Example 1
nums = [12,5,9,6,3]return = 3In binary the numbers are 1100, 101, 1001, 110 and 11. Three of them, 5, 9 and 3, have the lowest bit set, so 5 & 9 & 3 = 1, which is greater than 0. Three numbers (12, 5 and 6) also share the bit worth 4. No bit is set in four or more of the numbers, so no group of four or five has an AND above 0. The answer is 3.
Example 2
nums = [1,2,4,8]return = 1Each number has a different single bit set, so any two of them AND to 0. A single number on its own has AND equal to itself, so the answer is 1.
Example 3
nums = [7,7,7]return = 3The three 7s are separate elements, and 7 & 7 & 7 = 7, so all three can be chosen. The answer is 3.
Constraints
1 <= nums.length <= 10^41 <= nums[i] <= 10^9
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Bitwise XOR SubsequencesJP Morgan Chase · OAJP Morgan Chase interview questions
- Count Valid Bitwise PairsStripe · OAStripe interview questions
- Find the Unpaired NumbersAdobe · PHONE SCREENAdobe interview questions
- Bitwise XOR SubsequencesGoldman Sachs · OAGoldman Sachs interview questions
- Wildcard Address-Book QueriesGoogle · PHONE SCREENGoogle interview questions
- Count Subarrays With Given XORInMobi · OAInMobi interview questions
- Optimize Discount Selection Under a Point BudgetPalantir · OAPalantir interview questions
- Find the Unique Element Among PairsChubb · PHONE SCREENChubb interview questions
- Palindrome-Rearrangeable PairsExpedia · OAExpedia interview questions
- Random Dasher Set OperationsDoorDash · ONSITE INTERVIEWDoorDash interview questions