loading...

re: Daily Challenge #152 - Strongest Number in an Interval VIEW POST

FULL DISCUSSION
 

The optimization of using bit operations to find the "strength" of a number is a low hanging fruit, but the relationship between the number's strength and its binary representation can be taken much farther than that - to the point of solving this in logarithmic(!) time:

fn strongest_number(min: usize, max: usize) -> usize {
    assert!(min <= max);
    if min == max {
        // Otherwise the second `while` loop will not end
        return min;
    }
    let mut prefix_mask = !0usize;
    while 0 != (prefix_mask & max) {
        prefix_mask <<= 1;
    }
    while (prefix_mask & max) == (prefix_mask & min) {
        prefix_mask |= prefix_mask >> 1;
    }
    if (prefix_mask & min) == min {
        min
    } else {
        prefix_mask & max
    }
}

fn main() {
    assert_eq!(strongest_number(1, 2), 2);
    assert_eq!(strongest_number(5, 10), 8);
    assert_eq!(strongest_number(48, 56), 48);
    assert_eq!(strongest_number(129, 193), 192);
}

Explanation:

You can compare two numbers, padded to the same length, by finding their longest common prefix and then looking at the highest digit that's different. This work in any base, but farther ahead we'll use some properties unique to binary so let's stick with that.

For example, if we take 129 and 193 and convert them to binary:

129: 0000000010000001
193: 0000000011000001

We can see that both start with 000000001, and then 129 has 0000001 while 193 has 1000001. So the highest nonshared digit is 0 for 129 and 1 for 193 - which is why 193 is higher (yup - that's the direction the causation works here. Though this is math, so one can twist it to be the other way around...)

Lemma: Any number between the lower and higher bounds will share that same prefix with them.
Proof: If it doesn't, then at least one digit is different. Take the most significant digit where the number is different than the shared prefix. If it's 0 for the number and 1 for the prefix - this means the number is lower than the lower bound. If it's 1 for the number and 0 for the prefix - this means the number is higher than the higher bound.

So, the strongest number, being in the range, must also have that prefix. The strongest number with that prefix is just the prefix with only zeroes after it (remember - the number of digits is fixed!). That's also the lowest number in that range, so if it's equal to the lower bound - that's the strongest number in the range. Otherwise - the next strongest number is the prefix, a single one after it, and after that only zeroes. This number is guaranteed to not be higher than the higher bound, because they share the original common prefix plus a single one after it - and that number is the lowest in that prefix, since after that it's all zeroes.

 

That is just so clean, well thought and well explained! Congrats!

code of conduct - report abuse