DEV Community

Daily Challenge #152 - Strongest Number in an Interval

dev.to staff on January 02, 2020

Setup The strength of an even number is determined by the amount of times we can successfully divide by 2 until we reach an odd number. ...
Read full post
Collapse
 
dangerontheranger profile image
Kermit Alexander II • • Edited

One way to be sneaky about solving this problem comes from realizing what the problem is asking for when it says to "divide by 2 until we reach an odd number." If you think about the binary representation of an integer, there's only one way for it to be odd - that is, for its lowest/least-significant bit to be set to 1. Also recalling that dividing by two is equivalent to a single bitshift to the right, we can find a neat trick.

With 12 as an example, we can see that in binary it is 1100, so it would take two bitshifts right for it to be odd - that is, to turn it into 11 (3). So we don't need to actually divide 12 until we get 3, but simply count the number of trailing zeroes in 12 and use that as its strength - which would be 2, in this case. From there, we just need to keep track of the largest-strength-with-smallest-number combo and we'll be fine. With all that said, here's that strategy implemented in Python:

#!/usr/bin/env python3


def trailing_zeroes(num):
    num_trailing = 0
    while num & 1 == 0:
        # loop/bitshift right until we find a nonzero bit
        num_trailing += 1
        num = num >> 1
    return num_trailing


def find_strongest(start, stop):
    """Return the strongest number in a closed interval as per dev.to challenge #152
    """
    max_strength = 0
    best_num = 0
    # add 1 to halt the loop at the value of stop, not stop - 1
    for i in range(start, stop + 1):
        if i % 2 == 1:
            # don't bother with odd numbers
            continue
        # the strength given in the spec can be expressed
        # as the number of trailing zeroes in the number
        strength = trailing_zeroes(i)
        if strength > max_strength:
            max_strength = strength
            best_num = i
        elif strength == max_strength:
            # as per the spec, choose the lower number
            best_num = min(best_num, i)
    return best_num


if __name__ == "__main__":
    print(find_strongest(1, 2))
    print(find_strongest(5, 10))
    print(find_strongest(48, 56))
    print(find_strongest(129, 193))

edit/take #2: I tried to think about a way to optimize the trailing zero calculation for a while, but couldn't come up with anything; so I gave up and decided to search around a little bit to find if anyone came up with an O(1) method to calculate the trailing-zero problem instead of the naive linear solution I posted. Turns out someone did, and the link can probably explain better than I. The result of integrating that solution with the code I posted earlier is below:

#!/usr/bin/env python3


# the below function is adapted from https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup
def trailing_zeroes_fast(num):
    lookup = [32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30,
              28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15,
              29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18]
    num_trailing = lookup[(-num & num) % 37]
    return num_trailing


def find_strongest(start, stop):
    """Return the strongest number in a closed interval as per dev.to challenge #152
    """
    max_strength = 0
    best_num = 0
    # add 1 to halt the loop at the value of stop, not stop - 1
    for i in range(start, stop + 1):
        if i % 2 == 1:
            # don't bother with odd numbers
            continue
        # the strength given in the spec can be expressed
        # as the number of trailing zeroes in the number
        strength = trailing_zeroes_fast(i)
        if strength > max_strength:
            max_strength = strength
            best_num = i
        elif strength == max_strength:
            # as per the spec, choose the lower number
            best_num = min(best_num, i)
    return best_num


if __name__ == "__main__":
    print(find_strongest(1, 2))
    print(find_strongest(5, 10))
    print(find_strongest(48, 56))
    print(find_strongest(129, 193))

As a sidenote, an alternative method to count trailing zeroes to is to use the base 2 log of (-num & num), i.e, math.log2(num & -num) - in essence, this is asking how many bitshifts left starting from 1 are needed to hit the first set bit of num - but while it's clearly shorter and definitely more understandable, I don't believe this is faster than the lookup table route.

Collapse
 
idanarye profile image
Idan Arye • • Edited

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.

Collapse
 
ynndvn profile image
La blatte •

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

Collapse
 
ynndvn profile image
La blatte •

Some JS oneliners!

g=n=>(n>>>0).toString(2).split`1`.pop().length

f=n=>{i=n[0],m=0;while(i<=n[1]){m=Math.max(m,g(i));++i}return m}

The g method takes a number, converts it to binary, and return the number of trailing zeroes. Then, the f method loops through the input interval in order to return the maximum power

Collapse
 
nickholmesde profile image
Nick Holmes • • Edited

Don't write functions that already exist...

let strongestIn (n:int) (m:int) =
    seq {n..m} |> Seq.maxBy BitOperations.TrailingZeroCount

(F#)

Collapse
 
andreasjakof profile image
Andreas Jakof •

Available since .NET Core 3.0 ... nice touch! Also in F# the Sequence generation is SO MUCH easier.
In C# you'd be better off with a simple for-loop.

public static long StrongestNumber(long start, long end)
{
   long strongestNum = 0;
   int bitCount = -1;
   for (long i = start; i<=end; ++i)
   {
       int currentBitCount = BitOperations.TrailingZeroCount(i);
       if (currentBitCount > bitCount)
       {
           bitCount = currentBitCount;
           strongestNum = i;
       }
   }
   return strongestNum;
}
Collapse
 
nickholmesde profile image
Nick Holmes •

Well, my F# solution translated to C# would be something like this;

static int StrongestIn(int n, int m)
{
    return Enumerable.Range(n, (m-n))
        .Aggregate((a,b) => BitOperations.TrailingZeroCount(a) > BitOperations.TrailingZeroCount(b)
            ? a : b);
}

There is no built in "MaxBy" in the C#, so here I replaced it with an Aggregate. (The TrailingZeroCount method will use intrinsics (e.g. a CPU instruction) if its available, so I'm not worried about calling it repeatedly for the accumulator.)

Collapse
 
pranshukhandal profile image
PranshuKhandal • • Edited

Hello guys, this is my first time here, and this is my recursive approach:

function strongest(from, to, times = 0) {
    if (from > to) return false;
    if (to - from < 1) return from * (2 ** times);
    if (to - from < 2) return (from + (from % 2)) * (2 ** times);
    return strongest((from + (from % 2)) / 2, (to - (to % 2)) / 2, times + 1);
}

EDIT without times:

function strongest(from, to) {
    if (from > to) return false;
    if (to - from < 1) return from;
    if (to - from < 2) return from + (from % 2);
    return 2 * strongest((from + (from % 2)) / 2, (to - (to % 2)) / 2);
}
Collapse
 
bamartindev profile image
Brett Martin •

Inefficient Python w/ tail recursion:

def strongness_tail(n, a):
    return a if n % 2 == 1 else strongness_tail(n/2, 1 + a)

def strongness(n):
    return strongness_tail(n, 0)

def strongest_even(n, m):
    strongest = [-1, -1]
    for i in range(n, m+1):
        strength = strongness(i)
        if strength > strongest[0]:
            strongest = [strength, i]

    return strongest[1]
Collapse
 
centanomics profile image
Cent •

Not the most efficient answer, but it is!


const findStrongestNumber = () => {
 let interval = [
   parseInt(document.querySelector("#num1").value),
   parseInt(document.querySelector("#num2").value)
 ];

  let numStrength = [0, 0];

  for(let i = 0; i < interval.length; i++) {
    let num = interval[i];

    while ((num % 2) !== 1) {
      num/=2;
      numStrength[i]++;
    }
  }

  let answer = 0;
  if(numStrength[0] > numStrength[1]) {
    answer = interval[0];
  } else if (numStrength[1] > numStrength[0]) {
    answer = interval[1]
  } else {
    if(interval[0] < interval[1]) {
      answer = interval[0];
    } else {
      answer = interval[1];
    }
  }

  document.querySelector("#answer").innerHTML = answer;
}

CodePen

Collapse
 
aminnairi profile image
Amin •

Haskell

strongest :: (Int, Int) -> (Int, Int) -> (Int, Int)
strongest (strongestIndex, strongestValue) (index, value)
    | value > strongestValue = (index, value)
    | value == strongestValue && index < strongestIndex = (index, value)
    | otherwise = (strongestIndex, strongestValue)


strength :: Int -> Int
strength 0 = 0
strength number 
    | odd number = 0
    | otherwise = 1 + strength (div number 2)


strongestBetween :: Int -> Int -> Int
strongestBetween lowerbound upperbound =
    fst $ foldl1 strongest $ zip interval $ map strength interval

    where
        interval :: [Int]
        interval =
            [lowerbound..upperbound]


main :: IO ()
main = do
    print $ strongestBetween 1 2        -- 2
    print $ strongestBetween 5 10       -- 8
    print $ strongestBetween 48 56      -- 48
    print $ strongestBetween 129 193    -- 192

Try it.

Collapse
 
vitornogueira profile image
Vitor Nogueira • • Edited 
const calcMaxStrength = (numbers) => {
  const divider = 2;

  const isOdd = number => number % 2 === 0;

  const calcStrength = (dividend, strength = 0) => {
    if (isOdd(dividend)) {
      return calcStrength(dividend / divider, strength += 1);
    }

    return strength;
  };

  return Math.max(...numbers.map(number => calcStrength(number)));
};

console.log(calcMaxStrength([48, 56])); // 4
console.log(calcMaxStrength([129, 193])); // 0
Collapse
 
mckkaleb profile image
Kaleb McKinney •

Probably not a very efficient way to do it, but it works:

def strongest_number(interval):
  counter = interval[0]
  numbers = []
  while counter <= interval[1]:
    if counter % 2 == 0: numbers.append(counter) 
    counter += 1
  strengths = {}
  for i in range(len(numbers)):
    result = numbers[i]
    count = 0
    while result % 2 == 0:
      result = result / 2
      count += 1
    strengths[i] = count
  largest = 0
  k = ""
  for key in strengths:
    if strengths[key] > largest:
      largest = strengths[key]
      k = key
  return numbers[k]
Collapse
 
elvezpablo profile image
Paul •

Did it long hand in js. Great puzzle!

const strength = num => {
  let count = 0;
  if (num === 0) {
    return 0;
  }
  while (num % 2 == 0) {
    num = num / 2;
    count++;
  }
  return count;
};

const strongestNumber = interval => {
  const [start, end] = interval;
  let strongest = start;

  for (let i = start; i <= end; i++) {
    if (strength(i) > strength(strongest)) {
      strongest = i;
    }
  }
  return strongest;
};

console.log(strongestNumber([1, 2]));
console.log(strongestNumber([5, 10]));
console.log(strongestNumber([48, 56]));
console.log(strongestNumber([129, 193]));
Collapse
 
rburmorrison profile image
Ryan Burmeister-Morrison • • Edited

Here's a Nim submission!

proc even(i: int): bool {.inline.} = i mod 2 == 0

proc numStrength(i: int): int =
  ## Calculate the strength of a number.
  ##
  ## A number's strength is determined by the number of times
  ## it can divided in half until it reaches an odd number.
  var i = i
  while i.even:
    i = i div 2
    inc(result)

proc strongestNum(n, m: int): int =
  ## Given the closed interval [n, m], calculate the strongest number.
  var topStrength = 0
  for i in n..m:
    let strength = numStrength(i)
    if strength > topStrength:
      topStrength = strength
      result = i

assert strongestNum(1, 2) == 2
assert strongestNum(5, 10) == 8
assert strongestNum(48, 56) == 48
assert strongestNum(129, 193 == 192

There's definitely room to improve this, but I'm just starting to look into Nim's standard library, and I don't know all that's available to me yet.

Collapse
 
rdandekarslb profile image
Rashmin Dandekar •

Ruby

def get_strength(num)
  strength=0
  while !num.odd?
      num /= 2
      strength += 1
  end
  strength
end

def get_num_of_lowest_strength(nums)
  strength=Array.new
  nums.each do 
    |x| 
    strength.push [x, get_strength(x)]
  end  
  strength.sort_by{|k,v| [v,k]}.reverse
end

nums=[5..10,48..56,129..193]

nums.each do
  |num|
  x= get_num_of_lowest_strength(num)
  p x[0][0]
end
Collapse
 
vaibhavyadav1998 profile image
Vaibhav Yadav •

In Go.

func strongest(start, stop int) int {
    power := func(num int) int {
        numSlice := strings.Split(fmt.Sprintf("%b", num), "1")
        return len(numSlice[len(numSlice)-1])
    }

    hp := 0
    var result int

    for i := start; i <= stop; i++ {
        if hp < power(i) {
            hp = power(i)
            result = i
        }
    }

    return result
}