4092. Binary Digit Score - Easy Solution

The problem

You are given two integers a and b.

Let s1 and s2 be the number of set bits in the binary representations of a and b, respectively.

The score of these integers is defined as follows:

If s1 >= s2, the score is s1 * s2.
Otherwise, the score is s2 / s1 using integer division.

Return an integer representing the score of a and b.

A set bit refers to a bit in the binary representation of a number that has a value of 1.

Example 1:

Input: a = 14, b = 6

Output: 6

Explanation:

The binary representation of a = 14 is "1110", so s1 = 3.
The binary representation of b = 6 is "110", so s2 = 2.
Since s1 > s2, the score of a and b is s1 * s2 = 3 * 2 = 6.

Example 2:

Input: a = 5, b = 15

Output: 2

Explanation:

The binary representation of a = 5 is "101", so s1 = 2.
The binary representation of b = 15 is "1111", so s2 = 4.
Since s1 < s2, the score of a and b is s2 / s1 = 4 / 2 = 2.

Example 3:

Input: a = 10, b = 12

Output: 4

Explanation:

The binary representation of a = 10 is "1010", so s1 = 2.
The binary representation of b = 12 is "1100", so s2 = 2.
Since s1 == s2, the score of a and b is s1 * s2 = 2 * 2 = 4.

Constraints:

1 <= a, b <= 100

Approach overview

Problem Overview: Binary Digit Score asks you to work with the binary digits of the input numbers and compute a score from how many bits are set to 1. The core task is counting set bits efficiently, and the problem rewards choosing a bit-level method over string manipulation.

Approach 1: String Conversion and Count (O(log n) time, O(log n) space)

Convert the number to its binary string representation, then iterate through the characters and count every '1'. This is the most readable option and works in any language with a built-in base conversion. The cost is that you allocate a string whose length equals the number of binary digits, which is about log2(n). Use it to get a correct baseline quickly, then move on to bit operations.

Approach 2: Shift and Mask Loop (O(log n) time, O(1) space)

Check the lowest bit with n & 1, add it to the count, then shift right with n >>= 1. Repeat until n becomes 0. Every bit is inspected exactly once, so the loop runs once per binary digit. This removes the string allocation entirely and uses constant extra memory. It is the right choice when you want predictable O(1) space without relying on library functions.

Approach 3: Brian Kernighan's Trick (O(k) time, O(1) space)

The expression n & (n - 1) clears the lowest set bit of n. Loop while n is nonzero, increment a counter, and apply this operation each iteration. The loop runs exactly once per set bit, where k is the number of 1s, so it is faster than the shift loop when numbers are sparse. Prefer it when you want the fewest iterations and can explain why the trick works.

Approach 4: Built-in Bit Count (O(1) for fixed-width integers, O(1) space)

Languages expose population count directly: bin(n).count('1') in Python is the string method, while Integer.bitCount in Java, __builtin_popcount in C++, and bits.OnesCount in Go run on hardware instructions where available. Use this in production code. In an interview, state it, then show that you understand the manual bit loop underneath.

Recommended for interviews: Interviewers expect you to avoid string conversion and implement either the shift loop or Kernighan's trick. The string approach shows that you understand the problem, but a clean bit manipulation solution shows control of binary representation. Mention the built-in popcount as the production option after you write the manual loop. This is an bit manipulation problem at its core, and it touches math fundamentals when you reason about digit counts. If you convert to text first, you are doing string work the problem does not need.

Solution

Thinking

Both a and b are at most 100, so the number of 1s in their binary representations can be counted directly. The score depends only on how those two popcounts compare.

When s_1\ge s_2 the score is the product; otherwise it is the integer quotient of s_2 divided by s_1. Both inputs are at least 1, so s_1 is never 0.

Count the set bits of each number once, then return according to that comparison.

Let s_1 and s_2 be the number of 1s in the binary representations of a and b. If s_1\ge s_2, the score is s_1cdot s_2. Otherwise it is the integer quotient s_2/s_1.

The time complexity is O(1) and the space complexity is O(1).

Python

class Solution:
    def calculateScore(self, a: int, b: int) -> int:
        s1 = a.bit_count()
        s2 = b.bit_count()
        return s1 * s2 if s1 >= s2 else s2 // s1

Java

class Solution {
    public int calculateScore(int a, int b) {
        int s1 = Integer.bitCount(a);
        int s2 = Integer.bitCount(b);
        return s1 >= s2 ? s1 * s2 : s2 / s1;
    }
}

C++

class Solution {
public:
    int calculateScore(int a, int b) {
        int s1 = __builtin_popcount(a);
        int s2 = __builtin_popcount(b);
        return s1 >= s2 ? s1 * s2 : s2 / s1;
    }
};

TypeScript

function calculateScore(a: number, b: number): number {
    const s1 = a.toString(2).replace(/0/g, '').length;
    const s2 = b.toString(2).replace(/0/g, '').length;
    return s1 >= s2 ? s1 * s2 : Math.floor(s2 / s1);
}

func calculateScore(a int, b int) int {
	s1 := bits.OnesCount(uint(a))
	s2 := bits.OnesCount(uint(b))
	if s1 >= s2 {
		return s1 * s2
	}
	return s2 / s1
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
String Conversion and Count	O(log n)	O(log n)	Quick baseline or when readability matters most
Shift and Mask Loop	O(log n)	O(1)	General case with constant memory
Brian Kernighan's Trick	O(k), k = number of 1 bits	O(1)	Sparse bit patterns, fewest iterations
Built-in Bit Count	O(1) for fixed-width integers	O(1)	Production code, once you can explain the manual method

Frequently asked questions

Binary Digit Score Python solution?

In Python, the shortest approach is bin(n).count('1'), which converts the number to a binary string and counts the ones. For a no-string solution, loop while n is nonzero, add n & 1 to a counter, then apply n >>= 1. Both run in O(log n) time.

Is Binary Digit Score easy or hard?

Binary Digit Score is an easy problem with a 76.4% acceptance rate on FleetCode. The main challenge is knowing the bit manipulation operations, not the logic. Once you know shift or Kernighan's trick, the implementation takes only a few lines.

How to solve Binary Digit Score in O(n)?

Treat each number as a bit pattern and count set bits with a loop. Use while n is nonzero, add n & 1 to the count, then shift n right by one. The total work is proportional to the number of binary digits, which is the practical bound for this problem.

What is the best approach for Binary Digit Score?

The best approach is bit manipulation, either Brian Kernighan's trick with n & (n - 1) or a shift and mask loop. Both avoid string conversion and use O(1) extra space. For production code, the built-in popcount function is the cleanest option.

What data structure is used in Binary Digit Score?

No dedicated data structure is required. The solution uses integer bit operations such as AND, shift, and subtraction, plus a single counter variable. If you choose the string approach, you also create a temporary string of binary characters.

What is the time complexity of Binary Digit Score?

The shift loop runs in O(log n) time because it processes each binary digit once. Kernighan's trick runs in O(k) time, where k is the number of 1 bits, so it is faster for sparse inputs. Both use O(1) extra space, while the string approach uses O(log n) space.

Is Binary Digit Score asked at Google, Amazon, or Meta?

This problem is tagged General on FleetCode and is not listed as a frequently reported question at a specific company. It is best treated as a warm-up for bit manipulation fundamentals, which appear often in interviews at large tech companies.

Binary Digit Score solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments