Maximum Without 3 Consecutive Set Bits

Problem Overview

The only allowed change is turning a 1 into a 0, and the result must not contain three 1s in a row.

Intuition

The only allowed change is turning a 1 into a 0, and the result must not contain three 1s in a row. A bit is worth more than all the bits below it put together, so the best answer keeps every high bit it possibly can. Reading from the most significant bit down, a set bit only has to go when the two bits just above it are both kept 1s. Clearing it breaks the run, and nothing lower down can make up for losing a higher bit instead.

Algorithm

1Start a run counter at 0 and walk the bits from position 30 down to 0.
2If the bit is 0, reset the run to 0.
3If the bit is 1 and the run is already 2, clear that bit in n and reset the run to 0.
4Otherwise the bit is 1 and is kept, so increase the run.
5Return n after the last bit.

Example Walkthrough

Input: n = 15, which is 1111 in binary

1. Bits 3 and 2 are kept, so the run reaches 2.
2. Bit 1 would make three in a row, so it is cleared and the run resets.
3. Bit 0 is kept, giving 1101 in binary.

Output: 13

Common Pitfalls

• Clear the lowest bit of a run of three, not the highest. Dropping a higher bit loses more value.
• After clearing a bit, the run starts over, so a long run of 1s keeps two and drops one repeatedly.
• Only bits can be cleared. Setting a 0 to 1 is not allowed, even if it would give a larger value.
• An input of 0 or one with no three 1s in a row is returned unchanged.

Maximum Without 3 Consecutive Set Bits.java

Java

// Approach: Bits can only be cleared, and a higher bit is worth more than all
// lower bits together, so decide greedily from the most significant bit down.
// Keep a set bit unless the two bits just above it were both kept as 1s; in
// that case clear it, which also resets the run. A 0 bit resets the run too.
// Complexity: O(1) time (at most 31 bits), O(1) space.
class Solution {
    public int maxValue(int n) {
        int run = 0;
        for (int b = 30; b >= 0; b--) {
            if ((n >> b & 1) == 0) {
                run = 0;
            } else if (run == 2) {
                n &= ~(1 << b);
                run = 0;
            } else {
                run++;
            }
        }
        return n;
    }
}

Was this solution helpful?