How does the greedy approach work in the Maximum OR problem?

The greedy approach applies all k operations to a single element to maximize its value, which contributes most to the final OR result.

What is the optimal solution for the Maximum OR problem?

The optimal solution focuses all k operations on a single element, maximizing its value and subsequently the bitwise OR result.

Can the Maximum OR problem be solved without bitwise operations?

No, bitwise OR is central to the problem, as it determines the final value after applying operations on the elements.

What is the time complexity of the Maximum OR problem?

The time complexity can range from O(n * k) to O(n log(max(nums))) depending on the approach and optimizations applied.

How does GhostInterview help with the Maximum OR problem?

GhostInterview provides insights into the greedy approach and helps refine time complexity analysis, offering structured hints and solutions.

#2680

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

最大或值

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。 a | b 表示两个整数 a 和 b 的按位或 …

数组贪心位运算前缀和

题目描述

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 15

lightbulb

解题思路

方法一：贪心 + 预处理

我们注意到，为了使得答案最大，我们应该将 $k$ 次乘 $2$ 作用于同一个数。

我们先预处理出数组 $nums$ 的后缀或值数组 $suf$ ，其中 $suf[i]$ 表示 $nums[i], nums[i + 1], \cdots, nums[n - 1]$ 的按位或值。

接下来，我们从左到右遍历数组 $nums$ ，同时维护当前的前缀或值 $pre$ 。对于当前遍历到的位置 $i$ ，我们将 $nums[i]$ 乘 $2$ 的 $k$ 次方，即 $nums[i] \times 2^k$ ，与 $pre$ 进行按位或运算，得到的结果再与 $suf[i + 1]$ 进行按位或运算，即可得到以 $nums[i]$ 为最后一个数的最大或值。枚举所有的 $i$ ，即可得到答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maximumOr(self, nums: List[int], k: int) -> int:
        n = len(nums)
        suf = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suf[i] = suf[i + 1] | nums[i]
        ans = pre = 0
        for i, x in enumerate(nums):
            ans = max(ans, pre | (x << k) | suf[i + 1])
            pre |= x
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should demonstrate understanding of bitwise operations and greedy algorithms.
question_mark
Look for efficient handling of the k operations on a single element to maximize OR.
question_mark
Candidate may struggle if they fail to prioritize which element to operate on.

warning

常见陷阱

外企场景

error
Failing to apply all k operations on a single element, leading to suboptimal OR values.
error
Not recognizing the importance of bitwise OR and how each operation doubles the value of an element.
error
Inefficient brute-force approaches that involve recalculating the OR too often.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing operations on multiple elements, not just one.
arrow_right_alt
Changing the type of operation (e.g., multiplying by a factor other than 2).
arrow_right_alt
Considering a scenario where the OR operation also involves other bit manipulations (e.g., XOR).

help

常见问题

外企场景

继续练习

#2708 一个小组的最大实力值 #2588 统计美丽子数组数目 #2587 重排数组以得到最大前缀分数