Skip to content

4092. Binary Digit Score

DifficultyEasy

Description

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

Solutions

Solution 1: Bit Count

Thinking

Both \(a\) and \(b\) are at most \(100\), so the number of \(1\)s 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 \(1\)s in the binary representations of \(a\) and \(b\). If \(s_1\ge s_2\), the score is \(s_1\cdot 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)\).

1
2
3
4
5
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

1
2
3
4
5
6
7
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;
    }
}

1
2
3
4
5
6
7
8
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;
    }
};

1
2
3
4
5
6
7
8
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
}

1
2
3
4
5
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);
}

Comments