How could we get within a certain range, the maximum number of times, an int is divisible by 2

Question

I am doing the following programming exercise: Strongest even number in an interval. The statement is:

A strongness of an even number is the number of times we can successively divide by 2 until we reach an odd number starting with an even number n.

For example, if n = 12, then

12 / 2 = 6

6 / 2 = 3

we divided successively 2 times and we reached 3, so the strongness of 12 is 2.

If n = 16 then

16 / 2 = 8

8 / 2 = 4

4 / 2 = 2

2 / 2 = 1

we divided successively 4 times and we reached 1, so the strongness of 16 is 4 Task

Given a closed interval [n, m], return the even number that is the strongest in the interval. If multiple solutions exist return the smallest strongest even number.

Note that programs must run within the alloted server time; a naive solution will probably time out. Constraints

1 <= n < m <= INT_MAX Examples

for the input [1, 2] return 2 (1 has strongness 0, 2 has strongness 1)

for the input [5, 10] return 8 (5, 7, 9 have strongness 0; 6, 10 have strongness 1; 8 has strongness 2)

for the input [48, 56] return 48

First I thought to store in a map each number as a key, and the number of times it is divisible by 2, as a value:

import java.util.*;

public class StrongestEvenNumber {
  public static int strongestEven/**/(int n, int m) {
    System.out.println("n: "+n);
    System.out.println("m: "+m);
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();    
    for(int i = n, number = 0, strongness = 0; i <= m; i++){
      for(number = i, strongness = 0; number % 2 == 0; strongness++){
        number /= 2;
      }
      map.put(i, strongness);
    }
      Map.Entry<Integer, Integer> maxEntry = null;
      for(Map.Entry<Integer,Integer> entry : map.entrySet()){
        if(maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0){
          maxEntry = entry;
        }
      }
      return maxEntry.getKey();
  }
}

However, with large numbers, it runs out of heap memory space, or execution time runs out. For example with:

n: 1180381085
m: 2074186600

Java heap space runs out.

And with:

n: 324243
m: 897653214

Execution time runs out. The execution time exceeds 16000 ms

Then I tried to just store the number which is the most times divisible by 2:

import java.util.*;

public class StrongestEvenNumber {
  public static int strongestEven/**/(int n, int m) {
    System.out.println("n: "+n);
    System.out.println("m: "+m);
    int maxStrongness = 0, maxNumber = 0;
    for(int i = n, number = 0, strongness = 0; i <= m; i++){
      for(number = i, strongness = 0; number % 2 == 0; strongness++){
        number /= 2;
      }
      if(strongness > maxStrongness){
        maxStrongness = strongness;
        maxNumber = i;
      }
    }
      return maxNumber;
  }
}

Indeed it solves the heap space difficulty, however the execution time runs out behaviour stills happening.

For example with:

n: 200275492
m: 1590463313

The execution time exceeds 16000 ms

I have also read:

@Aggragoth: logarithm is a possible solution but you have to fight with *rounding errors* (`Math.log` is `double`) — Dmitry Bychenko, Dec 24 '19 at 08:32

Dmitry Bychenko · Accepted Answer · 2019-12-24T08:33:29.313

Well, the strongness of a value x is n when x is represented as

x = k * 2**n

knowing this we can check all powers of 2 (i.e. 1, 2, 4, 8, ...) if we can find any k such that

from <= k * 2**n <= to

Code:

private static int strongestEven(int from, int to) {
  if (to < from)
    return -1; // Or throw exception

  // best power of 2 we can insert between [to..from] as k * best
  int best = 1;

  while (true) {
    int ceiling = from / best + (from % best == 0 ? 0 : 1);
    int floor = to / best;

    if (ceiling > floor) {
      best = best / 2;

      return best * (to / best);
    }

    best *= 2;
  }
}

Tests:

  [ 1,   2] =>   2
  [ 5,  10] =>   8
  [48,  56] =>  48
  [80, 100] =>  96
  [97, 100] => 100

Finally,

  [1180381085, 1590463313] => 1342177280

we have 1342177280 == 5 * 268435456 == 5 * 2**28 so the strongest number within [1180381085, 1590463313] range has strongness 28

Please, note, that the algorithm has O(log(to)) time complexity that's why will do even if we turn all int into long

score 1 · Answer 2 · answered Dec 24 '19 at 08:25

1

The strongness is actually the number of trailing zeros in the binary representation of the number. You can use the java.lang.Integer.numberOfTrailingZeros to get it.

And as you want to test the even numbers, you can skipp the odd numbers in your loop.

public class StrongestEvenNumber {

  public static int strongestEven(int n, int m) {
    int maxStrongness = 0, maxNumber = 0;
    for(int i = n%2==0?n:n+1, strongness = 0; i <= m; i=i+2){
    strongness = Integer.numberOfTrailingZeros(i);
      if(strongness > maxStrongness){
        maxStrongness = strongness;
        maxNumber = i;
      }
    }
      return maxNumber;
  }

This runs in the allocated time:

Completed in 13190ms

answered Dec 24 '19 at 08:25

StephaneM

4,779
1
16
33

If `m` is *large* (e.g. n = `1` and m = `1_000_000_000`) looping over `n..m` interval can be *slow*; your own demosntration take `13` seconds to complete: `Completed in 13190ms` – Dmitry Bychenko Dec 24 '19 at 08:30
OP wants to run this code on the codewars site. The duration is taken from a run on codewars, this just means the test succeeds. Your answer may run much faster but what I've posted passes witb only minor optimizations from the OP's code. – StephaneM Dec 24 '19 at 08:34

How could we get within a certain range, the maximum number of times, an int is divisible by 2

2 Answers2