Rely the potential integer units of most dimension with the given situation

Given two integers L and R,   the duty is to search out the depend of the units of a most dimension such that every ingredient within the set is between L and R (inclusive), and for any two components within the set one among them is divisible by the opposite.

Examples:

Enter: L = 3, R = 19
Output: 4
Clarification: There will likely be 4 potential units – {3, 6, 12}, {3, 6, 18}, {3, 9, 18}, {4, 8, 16}

Enter: L = 4, R = 8
Output: 1

Method: This may be solved with the next concept:

• Let {S₁, S₂, S₃…… S_mx} be a set of most sizes satisfying the given circumstances. Let M_i = S_i+1/S_i. 
• It’s intuitive that for S_mx to be the minimal we have to select S₁ and M_i for all i as little as potential, the minimal worth of S₁ will be L and the minimal worth of M_i will be 2. 
• Nonetheless, we will select one of many M_i to be 3 in order that S_mx will likely be (3/2) instances the preliminary worth of S_mx (which needs to be lower than R), if we select any worth of M_i to be greater than 3, the scale of the set wouldn’t be most as there can all the time be a brand new ingredient S_mx+1  = 2*S_mx such dimension of the set would turn out to be mx+1. 

Comply with the under steps to implement the concept: 

• First calculate the worth of mx, i.e the utmost potential dimension of the set. This may be calculated assuming all of the values of M_i are 2, and the worth of S₁ is L, then mx = flooring(log2(r/l)) + 1. 
• Calculate the utmost worth of S₁ such {that a} set of dimension mx satisfying the given circumstances is feasible. Let’s name it X, We all know 2^mx-1 * X ≤ R, then X = R/2^mx-1.
• Calculate the utmost worth of S₁ such {that a} set of dimension mx satisfying the given circumstances is feasible and one of many values of M_i will be 3 as a substitute of two, allow us to name it Y. We all know that 3*2^mx-2 * Y ≤ R, then Y = R/(3*2^mx-2).
• We all know L ≤ Y ≤ X ≤ R, various units with S₁ ≤ Y are (Y-L+1)*mx, observe that we multiplied by mx as any of the M_i in these units will be 3. Plenty of units with S₁>Y and S₁ ≤ X is X – Y.
• Whole units of most dimension = (Y-L+1)*mx + X-Y.

Under is the implementation of the above strategy:

Time Complexity: O(1) 
Auxilairy House: O(1)