Problem Statement
John and Brus believe that the digits 4 and 7 are lucky and all others are not. Recently, they became interested in numeral systems with different bases. Normally, people use the numeral system with base 10 to represent numbers, however, there exist numeral systems with other bases. More exactly, for each integer B, B >= 2, there exists a numeral system with base B. In this system, there are B different digits, used to represent numbers from 0 to B-1, inclusive. In order to represent a positive integer A in such system, it’s necessary to find such digits a[n], a[n-1], …, a[0], that A = a[n] * B^n + a[n-1] * B^(n-1) + … + a[0] * B^0 (here ^ denotes the power operator), and then write these digits from left to right, in this exact order. For example, 255 = 4 * 62 + 7, therefore representation of number 255 in the numeral system with base 62 consists of two digits, the leftmost digit is 4 and the rightmost digit is 7. The base of numeral system B is called lucky for some integer number A if all digits of the number A represented in numeral system with base B are the lucky digits (i.e. 4 and 7). For example, base 62 is lucky for the number 255. You are given a long n. Return the total number of lucky bases for the number n. If there are infinitely many such lucky bases, return -1 instead.
Tutorial
Consider the equation \(b^n * a[n] + ..... + b^0 * a[0]\). Let us find the maximum n for the equation whose sum \(<= 10^{12}\). To find the maximum n we need to minimize the value of B. In that case, we need a base B > 4 because any base lesser than 5 cannot constitute the lucky digits 4 & 7 because their remainders will always be between 0 and 3. Hence the minimum base must be B = 5. \(n, 4 * ( 5^n + ... + 5) <= 10^{12}, (5^n + .... + 5) <= 10^{12} / 4\). To simplify the equation, we can ignore the terms whose power < n. The resulting equation will be \(5^n = 10^{12}/4, log(5) * n = 12 * log(10) - log(4), n = 16\). Now, we know that the number of terms won’t be greater than 16. The observation is that the values in the array will be a \(x \epsilon ({ 4, 7 })\). When we deal with equations with more than two terms, the base \(B < 10^6\).With the help of the above observation, we can solve the problem using two different approaches. The first approach is to count all the bases with equations having two terms. To get the count, we need to enumerate all possible values of the vector A. Then the result must be added to the count of a base whose equations have more than three terms. The total complexity of this approach is \(\mathcal{O} ( sqrt(n) * log(n) )\). The second approach is to enumerate all possible values of vector A and find the base B that satisfies the equation. The time complexity of this approach is \(\mathcal{O} ( 2^{16} * log(n) )\).
Code
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class TheLuckyBasesDivTwo {
public long find(long n) {
if(n == 7 || n == 4)
return -1;
long ef = solveForLinearEquation(n);
ef += solveFor3OrMoreTerms(n);
return ef;
}
private long solveFor3OrMoreTerms(long n) {
long sqrtn = (long) Math.sqrt(n);
long result = 0;
for(int b = 5 ; b <= sqrtn; b++)
{
long N = n;
long cnt = 0;
while(N > 0)
{
long aux = N % b;
if(aux != 4 && aux != 7)
break;
cnt += 1;
N = N / b;
}
if(cnt > 2 && N == 0)
result += 1;
}
return result;
}
private long solveForLinearEquation(long n) {
long ans = 0;
for(int a = 4; a <= 7; a += 3)
for(int b = 4 ; b<= 7 ; b+= 3)
ans += isfeasible(a, b, n);
return ans;
}
private long isfeasible(int a, int b, long n) {
long facto = (n-a) / b;
if((n - a) % b == 0 && facto > a && facto > b)
return 1;
return 0;
}
}