## The challenge

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

So 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`

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 allotted server time; a naive solution will probably time out.

### Constraints

1 <= n < m <= INT_MAX

### Examples

 ``````1 2 3 4 5 `````` ``````# 1 has strongness 0, 2 has strongness 1 [1, 2] --> 2 # 5, 7, 9 have strongness 0; 6, 10 have strongness 1; 8 has strongness 3 [5, 10] --> 8 [48, 56] --> 48 ``````

## The solution in Java code

Option 1:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 `````` ``````public class StrongestEvenNumber { public static int strongestEven(int n, int m) { int strong = Integer.highestOneBit(m), mask = strong; while (strong>= 1; strong |= mask; if(strong>m) strong ^= mask; } return strong; } } ``````

Option 2:

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````public class StrongestEvenNumber { public static int strongestEven(int n, int m) { while (m >= n) { if ((m & (m - 1)) < n) return m; m &= m - 1; } return 0; } } ``````

Option 3:

 ``````1 2 3 4 5 6 `````` ``````class StrongestEvenNumber { static int strongestEven(int n, int m) { for (; n <= (m & (m - 1)); m &= --m); return m; } } ``````

Option 4:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````public class StrongestEvenNumber { public static int strongestEven(int n, int m) { System.out.println(n + " " + m); int range = (m - n == 1)? 1 : m-n + 2; int exp = (int) Math.floor(Math.log(m) / Math.log(2)); while(exp >= 0){ int power = (int) Math.pow(2, exp); if(range >= power || ((n % power) > (m % power)) || (n % power) == 0){ return m - (m % power); } exp --; } return -1; } } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````import org.junit.Test; import static org.junit.Assert.assertEquals; import org.junit.runners.JUnit4; public class StrongestEvenNumberTest { @Test public void sampleTests() { assertEquals(2, StrongestEvenNumber.strongestEven(1,2)); assertEquals(8, StrongestEvenNumber.strongestEven(5,10)); assertEquals(48, StrongestEvenNumber.strongestEven(48,56)); assertEquals(192, StrongestEvenNumber.strongestEven(129,193)); } } ``````