Check if binary string can be partitioned such that each partition is a power of 5

Question

I recently came across this question - Given a binary string, check if we can partition/split the string into 0..n parts such that each part is a power of 5. Return the minimum number of splits, if it can be done.

Examples would be:

input = "101101" - returns 1, as the string can be split once to form "101" and "101",as 101= 5^1.
input = "1111101" - returns 0, as the string itself is 5^3.
input = "100"- returns -1, as it can't be split into power(s) of 5.

I came up with this recursive algorithm:

1. Check if the string itself is a power of 5. if yes, return 0
2. Else, iterate over the string character by character, checking at every point if the number seen so far is a power of 5. If yes, add 1 to split count and check the rest of the string recursively for powers of 5 starting from step 1.
3. return the minimum number of splits seen so far.

I implemented the above algo in Java. I believe it works alright, but it's a straightforward recursive solution. Can this be solved using dynamic programming to improve the run time?

The code is below:

public int partition(String inp){
    if(inp==null || inp.length()==0)
        return 0;
    return partition(inp,inp.length(),0);
}
public int partition(String inp,int len,int index){
    if(len==index)
        return 0;
    if(isPowerOfFive(inp,index))
        return 0;
    long sub=0;
    int count = Integer.MAX_VALUE;
    for(int i=index;i<len;++i){
        sub = sub*2 +(inp.charAt(i)-'0');
        if(isPowerOfFive(sub))
            count = Math.min(count,1+partition(inp,len,i+1));
    }
    return count;
}

Helper functions:

public boolean isPowerOfFive(String inp,int index){
    long sub = 0;
    for(int i=index;i<inp.length();++i){
        sub = sub*2 +(inp.charAt(i)-'0');
    }
    return isPowerOfFive(sub);
}

public boolean isPowerOfFive(long val){
    if(val==0)
        return true;
    if(val==1)
        return false;
    while(val>1){
        if(val%5 != 0)
            return false;
        val = val/5;
    }
    return true;
}

Answer 1

Here is simple improvements that can be done:

• Calculate all powers of 5 before start, so you could do checks faster.
• Stop split input string if the number of splits is already greater than in the best split you've already done.

Here is my solution using these ideas:

public static List<String> powers = new ArrayList<String>();
public static int bestSplit = Integer.MAX_VALUE;

public static void main(String[] args) throws Exception {
    // input string (5^5, 5^1, 5^10)
    String inp = "110000110101101100101010000001011111001";
    // calc all powers of 5 that fits in given string
    for (int pow = 1; ; ++pow) {
        String powStr = Long.toBinaryString((long) Math.pow(5, pow));
        if (powStr.length() <= inp.length()) { // can be fit in input string
            powers.add(powStr);
        } else {
            break;
        }
    }
    Collections.reverse(powers); // simple heuristics, sort powers in decreasing order
    // do simple recursive split
    split(inp, 0, -1);
    // print result
    if (bestSplit == Integer.MAX_VALUE) {
        System.out.println(-1);
    } else {
        System.out.println(bestSplit);
    }
}

public static void split(String inp, int start, int depth) {
    if (depth >= bestSplit) {
        return; // can't do better split
    }
    if (start == inp.length()) { // perfect split
        bestSplit = depth;
        return;
    }
    for (String pow : powers) {
        if (inp.startsWith(pow, start)) {
            split(inp, start + pow.length(), depth + 1);
        }
    }
}

EDIT:

I also found another approach which looks like very fast one.

1. Calculate all powers of 5 whose string representation is shorter than input string. Save those strings in powers array.
2. For every string power from powers array: if power is substring of input then save its start and end indexes into the edges array (array of tuples).
3. Now we just need to find shortest path from index 0 to index input.length() by edges from the edges array. Every edge has the same weight, so the shortest path can be found very fast with BFS.
4. The number of edges in the shortest path found is exactly what you need -- minimum number of splits of the input string.

Answer 2

Instead of calculating all possible substrings, you can check the binary representation of the powers of 5 in search of a common pattern. Using something like:

bc <<< "obase=2; for(i = 1; i < 40; i++) 5^i"

You get:

5¹ = 101₂
5² = 11001₂
5³ = 1111101₂
5⁴ = 1001110001₂
5⁵ = 110000110101₂
5⁶ = 11110100001001₂
5⁷ = 10011000100101101₂
5⁸ = 1011111010111100001₂
5⁹ = 111011100110101100101₂
5¹⁰ = 100101010000001011111001₂
5¹¹ = 10111010010000111011011101₂
5¹² = 1110100011010100101001010001₂
5¹³ = 1001000110000100111001110010101₂
5¹⁴ = 101101011110011000100000111101001₂
5¹⁵ = 11100011010111111010100100110001101₂
5¹⁶ = 10001110000110111100100110111111000001₂
5¹⁷ = 1011000110100010101111000010111011000101₂
5¹⁸ = 110111100000101101101011001110100111011001₂
...
5²⁹ = 10100001100011110000011111010111001101101011100100001011111001010101₂

As you can see, odd powers of 5 always ends with 101 and even powers of 5 ends with the pattern 10+1 (where + means one or more occurrences).

You could put your input string in a trie and then iterate over it identifying the 10+1 pattern, once you have a match, evaluate it to check if is not a false positive.