Check if it is possible to split the binary string so that each section has a capacity of 5

Question

I recently came across this question - Given a binary string, check if we can split / split the string into 0..n parts so that each part has a capacity of 5. Return the minimum number of partitions if this can be done.

Examples:

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:

• Check if the string itself is a value of 5. if yes, return 0
• Else, iterating over the character of a string by character, checking at each point if the number shown so far is 5. If yes, add 1 to split the count and check the rest of the string recursively for degrees 5, starting from step 1.
• return the minimum number of splits visible so far.

Java. , , . , ?

:

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;
}

:

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

, :

• 5 , .
• , , , .

, :

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:

, .

• 5, input. powers.
• power powers: if power input, start end edges ( ).
• 0 input.length() edges. , BFS.
• - , - .

Answer 2

5 . - :

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

:

5 ¹= 101 ₂
5 ²= 1 1001 ₂
5 ³= 1111 101 ₂
5 ⁴= 10011 10001 ₂
5 ⁵= 110000110 101 ₂
5 ⁶= 1111010000 1001 ₂
5 ⁷= 10011000100101 101 ₂
5 ⁸= 1011111010111 100001 ₂
5 ⁹= 111011100110101100 101 ₂
5 ¹⁰= 10010101000000101111 1001 ₂
5 ¹¹= 10111010010000111011011 101 ₂
5 ¹²= 11101000110101001010010 10001 ₂
5 ¹³= 1001000110000100111001110010 101 ₂
5 ¹⁴= 10110101111001100010000011110 1001 ₂
5 ¹⁵= 11100011010111111010100100110001 101 ₂
5 ¹⁶= 1000111000011011110010011011111 1000001 ₂
5 ¹⁷= 1011000110100010101111000010111011000 101 ₂
5 ¹⁸= 11011110000010110110101100111010011101 1001 ₂
...
5 ²⁹= 10100001100011110000011111010111001101101011100100001011111001010 101 ₂

, 5 101, 5 10+1 ( + ).

trie, , 10+1, , , , .

Answer 3

. , , : ( )

ABCD

, A mod 5 , BCD, , B mod 5 , C D, CD . :

C -> 0
D -> 0
CD -> 0
BCD -> 1  # split B/CD is the best

ABCD - , AB mod 5 , CD - , .

partition() - , (string, start, length). , , .

Answer 4

Below is the solution in C ++. Using dynamic programming, I consider all possible splits and keep the best results.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int isPowerOfFive(ll n)
{
    if(n == 0) return 0;
    ll temp = (ll)(log(n)/log(5));
    ll t = round(pow(5,temp));
    if(t == n)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
ll solve(string s) 
{
    vector<ll> dp(s.length()+1);
    for(int i = 1; i <= s.length(); i++)
    {
        dp[i] = INT_MAX;
        for(int j = 1; j <= i; j++)
        {
            if( s[j-1] == '0')
            {
                continue;
            }
            ll num = stoll(s.substr(j-1, i-j+1), nullptr, 2);
            if(isPowerOfFive(num))
            {
                dp[i] = min(dp[i], dp[j-1]+1);
            }
        }
    }
    if(dp[s.length()] == INT_MAX)
    {
        return -1;
    }
    else
    {
        return dp[s.length()];
    }
}
int main()
{
    string s;
    cin>>s;
    cout<<solve(s);
}