3133. 数组最后一个元素的最小值

Powered by:NEFU AB-IN

Link

3133. 数组最后一个元素的最小值

题意

给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。

返回 nums[n - 1] 可能的 最小 值。

思路

可以说，如果都 AND 操作为 x，那么 x 的二进制位为 1 的地方，所有数都必须有，那么最优的情况就是最小值为 x
进而就是枚举 x 中二进制为 0 的位置，将 0 的位置进行塞 0 或 1 的操作
由于要严格递增，那么就要按照如，000,001,010的顺序塞

比如
x = “0b10010”
n = “0b11”

那么第一个数为 10010，第二个为10011，第三个为10110，所以第三个也就是把 10 填进了 x 的 0 的二进制位中，10 恰好就是 n - 1
所以思路就是枚举 x 的每一位，当为 0 的时候，开始填 n 的第一位，然后 n 右移，直到 n = 0

代码

'''
Author: NEFU AB-IN
Date: 2024-07-09 23:35:08
FilePath: \LeetCode\3133\3133.py
LastEditTime: 2024-07-11 16:14:56
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)

# Set recursion limit
setrecursionlimit(INF)


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])

    @staticmethod
    def to_1_indexed(data: Union[List, str, List[List]]):
        """Adds a zero prefix to the data and returns the modified data and its length."""
        if isinstance(data, list):
            if all(isinstance(item, list) for item in data):  # Check if it's a 2D array
                new_data = [[0] * (len(data[0]) + 1)] + [[0] + row for row in data]
                return new_data, len(new_data) - 1, len(new_data[0]) - 1
            else:
                new_data = [0] + data
                return new_data, len(new_data) - 1
        elif isinstance(data, str):
            new_data = '0' + data
            return new_data, len(new_data) - 1
        else:
            raise TypeError("Input must be a list, a 2D list, or a string")


class Str:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    removeprefix = staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)
    removesuffix = staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def minEnd(self, n: int, x: int) -> int:
        n -= 1
        # x = "10010"
        # n - 1 = "10"
        for j in range(64):
            if x >> j & 1:
                continue
            x |= (n & 1) << j
            n >>= 1
            if not n:
                break

        return x


print(Solution().minEnd(3, 18))