CareerCup

dynamic programming
f[i] = min (f[j -1] + 1, f[i])

public int numsOfWays (String s ){
		long [] f = new long [s.length() + 1] ;
		f[0] = 0;	
		for (int i = 1 ; i <= s.length() ;++i) {
			f[i] = Integer.MAX_VALUE;
		 for (int j = 1 ; j <= i ;++j) {
			 if (s.charAt(j - 1) == '0'){
				 continue ;
			 }
			 int num = Integer.parseInt(s.substring(j - 1, i), 2) ;				 
			 if (isPower(num)) {
				 f[i] = Math.min(f[i], f[j - 1] + 1) ;				 
			 }			 
		 }
		}								
		return f[s.length()] == Integer.MAX_VALUE ? -1 : (int)f[s.length()] ;
	}
	
	private boolean isPower (long val){
		if (val == 0) {
			return false ;
		}
		int n = (int)(Math.log(val) / Math.log(5));
		return Math.pow(5, n) == val;
	}

@Scott
I agree with the thought. You may need to check f[j-1] before taking it into account, what if f[j-1] is Integer.MAX_VALUE.
Code in python:

import math

def sliceIntoMultiplesOf5(s):
	def isPowerOf5(s):
		x = int(s, 2)
		n = int(math.log2(x) / math.log2(5))
		return 5 ** n == x

	# initialize
	n = len(s)
	f = [-1] * n
	# dp
	for i in range(n):
		if isPowerOf5(s[:i+1]):
			f[i] = 1
			continue
		for j in range(i):
			# pieces do not start with 0
			if f[j] == -1 or s[j+1] == '0' or not isPowerOf5(s[j+1:i+1]):
				continue
			if f[i] == -1:
				f[i] = f[j] + 1
			else:
				f[i] = min(f[i], f[j] + 1)
	# result
	return f[n-1]


# test case
strList = [
"101101101",
"1111101",
"110011011",
"1000101011",
"111011100110101100101110111" 
]

for s in strList:
	print(sliceIntoMultiplesOf5(s))

'''
The following code takes a binary number as input and prints the number 
of chunks in the number which are divisible by 5.
'''
import sys
import math

def validateInput(inputStream):
  isValid = True;
  for x in inputStream:
    if x != '0' and x != '1':
      isValid = False;
      break;  
  return isValid;

'''
For divisibility by 5, the number must end in 1010 or 101.
'''
def processInput(inputStream):
  chunk = '';
  chunksDivisibleBy5 = 0;
  for x in inputStream:
    chunk += x;
    decimal = convertBinaryToDecimal(chunk);
    if decimal is not None and decimal%5 == 0:
      chunksDivisibleBy5 += 1;
      chunk = '';
  return chunksDivisibleBy5;

'''
Converts a binary number to its decimal counterpart.
'''
def convertBinaryToDecimal(inputStream):
  length = len(inputStream);
  decimal = 0;
  for x in inputStream:
    decimal += length * math.pow(int(x), length - 1);
  return decimal;

def main():
    input = sys.argv[1];
    inputStream = list(input);
    if (validateInput(inputStream)):
      print 'Valid input';
      chunksDivisibleBy5 = processInput(inputStream);
      print chunksDivisibleBy5 if chunksDivisibleBy5 != 0 else -1;
    else:
      print 'Invalid input. The input should contain only 0s and 1s.';

if __name__ == '__main__':
    main()

1) Consider int start = 0, curr = 0;
2) Traverse from left to right one letter at a time and and increment curr++ accordingly.
3) Validate whether the number formed from start to curr index is in power of 5 or not. If it is then increment k and also update start variable to curr+1 (start=curr+1)

Wow this seems to be an intimidating problem at first but if you think about it you just need to split once a power of five is found then look for another sets after that chunk and used memoization to recall when you already processed a previous chunk.

I used a hash set to know if a number is a power of 5.

I think there are better solutions but this is what I would came up with at the moment.

public int FindSplitsOfPowerOfFive(string S)
{

	return CoreFindSplits(S, 0, S.Length, new Dictionary<string, int>());
}

private int CoreFindSplits(string S, int start, int end, Dictionary<string, int> memo)
{
	string hash = start + "," + end;

	if(memo.ContainsKey(hash))
	{
		return memo[hash];
	}

	var sorted = SortedDictionary<int, int>()

	// Find all Powers of Five while parsing
	long current = 0;
	int min = -2;

	for(int i = start, i < S.Length; i++)
	{
		current <<= 1;
		current += S[i] =='1'?1:0;
		
		if(IsPowerOfFive(current))
		{
			int sub = CoreFindSplits(S, i+1, end, memo);

			if(sub != -1 && sub < min)
			{
				min = sub + 1;
			}
		}
	}

	memo.Add(hash, min);

	return min;
}

private bool IsPowerOfFive(long number)
{
	// Precalculated all powers of five for efficient lookup
	const HashSet<long> powersOfFive = new HashSet<long> 
	{
            5,
            25,
            125,
            625,
            3125,
            15625,
            78125,
            390625,
            1953125,
            9765625,
            48828125,
            244140625,
            1220703125,
            6103515625,
            30517578125,
            152587890625,
            762939453125,
            3814697265625,
            19073486328125,
            95367431640625,
            476837158203125,
            2384185791015625,
            11920928955078125,
            59604644775390625,
            298023223876953125,
            1490116119384765625,
            7450580596923828125
	};

	return powersOfFive.Contains(number);
}

is there a cpp solution for this problem

#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long int
#define llu unsigned long long int
#define I int
#define S string
#define D double
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define in(n) scanf("%lld",&n)
#define in2(a,b) scanf("%lld %lld",&a,&b)
#define in3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define out(a) printf("%lld\n",a)
#define inu(a) scanf("%lld",&a)
#define outu(a) printf("%llu",a)
#define outf(a) printf("%.9f\n", a);
#define mod 1000000007
#define inf 100000000000000
#define MM(a,x)  memset(a,x,sizeof(a));
#define ALL(x)   (x).begin(), (x).end()
#define UN(v)    sort(ALL(v)), v.resize(unique(ALL(v))-v.begin())
#define fill(a,x) memset(a,x,sizeof(a)) 
#define MP make_pair
#define PB push_back
#define f first
#define s second
#define sz(v) v.size()
#define nl cout<<"\n"
#define MX1 100005
#define MX2 1000005
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
typedef pair<ll,ll>  pll;
typedef vector<ll>     vll;
typedef vector<llu>    vllu;
typedef vector<string>  vs;
typedef vector<pll>     vpll;

bool check(int i , string s , int k){
	ll ans = 0;
	for(int j = k ; j >= i ; j--)
		ans = ans + ((s[j] - '0') * pow(2,k - j));
	
	while(ans > 0){
		if(ans % 5 == 0)
			ans/=5;
		else if(ans != 1)
			return(false);
		if(ans == 1)
			return(true);
	}
}


int main(){
	fast;
	// freopen("A-large-practice.in","r",stdin);
	// freopen("output_file_name.out","w",stdout);
	S s;
	cin >> s;
	ll k = sz(s)-1;
	int i;
	int count = 0;
	while(k >= 0){
		for(i = 0 ; i <= k ; i++){
			bool  p = check(i,s,k);
			if(p){
				count++;
				k = --i;
				break;
			}
		}
		if(k < 0)
			break;
	}
	 cout << count << endl;

}