3915. Maximum Product of Two Integers With No Common Bits
My accepted Python solution to LeetCode problem 3915, Maximum Product of Two Integers With No Common Bits, running in 18898ms.
- Difficulty: Medium
- Python
- Runtime 18898ms
- Memory 40.9MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 18898ms, memory 40.9MB, accepted 2026-01-02.
class Solution:
def maxProduct(self, A: List[int]) -> int:
k = max(A).bit_length()
mask = 1 << k
dp = [0] * mask
for a in A:
dp[a] = a
for i in range(mask):
if dp[i]: continue
for j in range(k):
if i & (1 << j):
if dp[i ^ (1 << j)] > dp[i]:
dp[i] = dp[i ^ (1 << j)]
return max(a * dp[(mask - 1) ^ a] for a in A)