Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using bit manipulation strategy.
You are given two integers n and x. You have to construct an array of positive integers nums of size n where for every 0 <= i < n - 1, nums[i + 1] is greater than nums[i], and the result of the bitwise AND operation between all elements of nums is x.
Return the minimum possible value of nums[n - 1].
Example 1:
Input: n = 3, x = 4
Output: 6
Explanation:
nums can be [4,5,6] and its last element is 6.
Example 2:
Input: n = 2, x = 7
Output: 15
Explanation:
nums can be [7,15] and its last element is 15.
Constraints:
1 <= n, x <= 108Problem summary: You are given two integers n and x. You have to construct an array of positive integers nums of size n where for every 0 <= i < n - 1, nums[i + 1] is greater than nums[i], and the result of the bitwise AND operation between all elements of nums is x. Return the minimum possible value of nums[n - 1].
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Bit Manipulation
3 4
2 7
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3133: Minimum Array End
class Solution {
public long minEnd(int n, int x) {
--n;
long ans = x;
for (int i = 0; i < 31; ++i) {
if ((x >> i & 1) == 0) {
ans |= (n & 1) << i;
n >>= 1;
}
}
ans |= (long) n << 31;
return ans;
}
}
// Accepted solution for LeetCode #3133: Minimum Array End
func minEnd(n int, x int) (ans int64) {
n--
ans = int64(x)
for i := 0; i < 31; i++ {
if x>>i&1 == 0 {
ans |= int64((n & 1) << i)
n >>= 1
}
}
ans |= int64(n) << 31
return
}
# Accepted solution for LeetCode #3133: Minimum Array End
class Solution:
def minEnd(self, n: int, x: int) -> int:
n -= 1
ans = x
for i in range(31):
if x >> i & 1 ^ 1:
ans |= (n & 1) << i
n >>= 1
ans |= n << 31
return ans
// Accepted solution for LeetCode #3133: Minimum Array End
/**
* [3133] Minimum Array End
*/
pub struct Solution {}
// submission codes start here
impl Solution {
pub fn min_end(n: i32, x: i32) -> i64 {
let (n, x) = (n as i64, x as i64);
let mut result = x;
let bit_count = 128 - n.leading_zeros() - x.leading_zeros();
let mut pos = 0;
for i in 0..bit_count {
if (result >> i) & 1 == 0 {
if ((n - 1) >> pos) & 1 == 1 {
result |= 1 << i;
}
pos += 1;
}
}
result
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_3133() {
assert_eq!(6, Solution::min_end(3, 4));
assert_eq!(15, Solution::min_end(2, 7));
}
}
// Accepted solution for LeetCode #3133: Minimum Array End
function minEnd(n: number, x: number): number {
--n;
let ans: bigint = BigInt(x);
for (let i = 0; i < 31; ++i) {
if (((x >> i) & 1) ^ 1) {
ans |= BigInt(n & 1) << BigInt(i);
n >>= 1;
}
}
ans |= BigInt(n) << BigInt(31);
return Number(ans);
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.