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
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 allotted server time; a naive solution will probably time out.
Constraints
1 <= n < m <= INT_MAX
Examples
# 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:
public class StrongestEvenNumber {
public static int strongestEven(int n, int m) {
int strong = Integer.highestOneBit(m),
mask = strong;
while (strong<n) {
mask >>= 1;
strong |= mask;
if(strong>m) strong ^= mask;
}
return strong;
}
}
Option 2:
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:
class StrongestEvenNumber {
static int strongestEven(int n, int m) {
for (; n <= (m & (m - 1)); m &= --m);
return m;
}
}
Option 4:
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
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));
}
}
