LeetCode Entry

3133. Minimum Array End

09.11.2024 medium 2024 kotlin rust

nth of increasing sequence with AND[..]=x manipulation

3133. Minimum Array End medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/795

Problem TLDR

nth of increasing sequence with AND[..]=x #medium #bit_manipulation

Intuition

Let’s observe how we can form that sequence of increasing numbers:

    //       x = 5
    // 0     101
    // 1     111
    // 2    1101 *
    // 3    1111
    // 4   10101
    // 5   10111
    // 6   11101
    // 7   11111
    // 8  100101 -> bit + x
    // 9  100111
    // 10 101101 *      n=10, first zero = 10 % 2 = 0, second zero = (10 / 2) % 2 = 1
    // 11 101111              third zero = (10 / 4) % 4
    // 12 110101
    //        ^ every other
    //      ^ every 2
    //     ^ every 4
    //    ^ every 8

Some observations:

• to AND operation resulting to x, all bits of x must be set in each number
• the minimum number is x
• we can only modify the vacant positions with 0 bits
• to form the next number we must alterate the vacant bit skipping the 1 bits
• in the n‘th position each vacant bit is a period % 2, where period is a 1 << bit
• another way to look at this: we have to add (n-1) inside the 0 bit positions of x

Approach

• one small optimization is to skip 1-set bits with trailing_ones()

Complexity

• Time complexity: \(O(log(n + x))\)

• Space complexity: \(O(1)\)

Code

    fun minEnd(n: Int, x: Int): Long {
        var period = n - 1; var a = x.toLong()
        for (b in 0..63) {
            if (period % 2 > 0) a = a or (1L shl b)
            if (b > 31 || (x shr b) % 2 < 1) period /= 2
        }
        return a
    }

    pub fn min_end(n: i32, x: i32) -> i64 {
        let (mut a, mut period, mut x, mut b) =
            (x as i64, (n - 1) as i64, x as i64, 0);
        while period > 0 {
            a |= (period & 1) << b;
            period >>= 1 - x & 1;
            let s = 1 + (x / 2).trailing_ones();
            x >>= s; b += s
        }
        a
    }

    long long minEnd(int n, int x) {
        long long a = x, y = x, period = (n - 1);
        for (int b = 0; period;) {
            a |= (period & 1LL) << b;
            period >>= 1 - y & 1;
            int s = 1 + __builtin_ctz(~(y / 2));
            y >>= s; b += s;
        }
        return a;
    }