Skip to content

3133. Minimum Array End 👍

  • Time: $O(\log n + \log x)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  long long minEnd(int n, int x) {
    // Set x's 0s with (n - 1)'s LSb-to-MSb bits, preserving x's 1s. This
    // operation increase x for (n - 1) iterations while preserving x's 1s.
    const int kMaxBit = log2(n) + log2(x) + 2;
    const long k = n - 1;
    long ans = x;
    int kBinaryIndex = 0;

    for (int i = 0; i < kMaxBit; ++i) {
      if ((ans >> i & 1) == 0) {
        // Set x's 0 with k's bit if the running bit of k is 1.
        if (k >> kBinaryIndex & 1)
          ans |= 1L << i;
        ++kBinaryIndex;
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public long minEnd(int n, int x) {
    // Set x's 0s with (n - 1)'s LSb-to-MSb bits, preserving x's 1s. This
    // operation increase x for (n - 1) iterations while preserving x's 1s.
    final int kMaxBit = bitLength(n) + bitLength(x);
    final long k = n - 1;
    long ans = x;
    int kBinaryIndex = 0;

    for (int i = 0; i < kMaxBit; ++i) {
      if ((ans >> i & 1) == 0) {
        // Set x's 0 with k's bit if the running bit of k is 1.
        if ((k >> kBinaryIndex & 1) == 1)
          ans |= 1L << i;
        ++kBinaryIndex;
      }
    }

    return ans;
  }

  private int bitLength(int n) {
    return 32 - Integer.numberOfLeadingZeros(n);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def minEnd(self, n: int, x: int) -> int:
    # Set x's 0s with (n - 1)'s LSb-to-MSb bits, preserving x's 1s. This
    # operation increase x for (n - 1) iterations while preserving x's 1s.
    kMaxBit = n.bit_length() + x.bit_length()
    k = n - 1
    kBinaryIndex = 0

    for i in range(kMaxBit):
      if x >> i & 1 == 0:
        # Set x's 0 with k's bit if the running bit of k is 1.
        if k >> kBinaryIndex & 1:
          x |= 1 << i
        kBinaryIndex += 1

    return x