Given a string s containing 0's and 1's. You have to return the smallest positive integer C, such that the binary string can be cut into C pieces and each piece should be of the power of 5  with no leading zeros.
Note: The string s is a binary string. And if no such cuts are possible, then return -1.
Example 1:
Input:
s = "101101101"
Output: 
3
Explanation: 
We can split the given string into 
three 101s, where 101 is the binary 
representation of 5.
Example 2:
Input:
s = "00000"
Output: 
-1
Explanation: 
0 is not a power of 5.
Your Task:
Your task is to complete the function cuts() which take a single argument(string s). You need not take any input or print anything. Return an int C if the cut is possible else return -1.
Expected Time Complexity: O(|s|*|s|*|s|).
Expected Auxiliary Space: O(|s|).
Constraints:
1<= |s| <=50

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Bit manipulation

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:



    def cuts(self, s):

        # code here

Solutions:
class Solution:

	def cuts(self, s):
		c = list(s)
		l = len(c)
		dp = [0] * (l + 1)
		dp[0] = 0
		for i in range(1, l + 1):
			index = i - 1
			if c[index] == '0':
				dp[i] = -1
			else:
				dp[i] = -1
				t = 1000
				count = 0
				for j in range(i):
					if c[index - j] == '1':
						count += Solution.num(j)
						if Solution.check(count) and dp[index - j] != -1:
							w = 1 + dp[index - j]
							t = min(w, t)
				if t != 1000:
					dp[i] = t
		return dp[l]

	def num(y):
		if y == 0:
			return 1
		x = 2
		for i in range(1, y):
			x = x << 1
		return x

	@staticmethod
	def check(n):
		if n == 0:
			return False
		if n == 1:
			return True
		if n % 5 != 0:
			return False
		else:
			return Solution.check(n // 5)


class Solution:

	def check(self, string):
		temp = int(string, 2)
		while temp > 1:
			if temp % 5 != 0:
				return False
			temp /= 5
		return True

	def cuts(self, s):
		n = len(s)
		if n == 0 or s[0] == '0':
			return -1
		if self.check(s):
			return 1
		min_cuts = float('inf')
		for i in range(1, n):
			left = s[:i]
			right = s[i:]
			if self.check(left):
				cuts_right = self.cuts(right)
				if cuts_right != -1:
					min_cuts = min(min_cuts, cuts_right + 1)
		if min_cuts != float('inf'):
			return min_cuts
		return -1


class Solution:

	def cuts(self, s):
		if s == '1':
			return 1
		c = 0
		d = 0
		l = ['1', '101', '11001', '1111101', '1001110001', '110000110101', '11110100001001', '10011000100101101', '1011111010111100001', '111011100110101100101', '100101010000001011111001', '10111010010000111011011101', '1110100011010100101001010001', '1001000110000100111001110010101', '101101011110011000100000111101001', '11100011010111111010100100110001101', '10001110000110111100100110111111000001', '1011000110100010101111000010111011000101', '110111100000101101101011001110100111011001', '100010101100011100100011000001001000100111101', '10101101011110001110101111000101101011000110001']
		l.reverse()
		q = s
		for i in l:
			if i in s:
				x = s.count(i)
				s = s.replace(i, '')
				d += x
				c += x * len(i)
		if c == len(q):
			return d
		return -1


import sys

class Solution:

	def isPower(self, num, exp):
		pwr = 1
		pcnt = 0
		while num > 1:
			if num % exp == 0:
				num //= exp
				pwr += 1
			else:
				return 0
		return pwr

	def solve(self, s, start, count, mcount):
		if start == len(s):
			mcount[0] = min(mcount[0], count)
			return
		if start > len(s):
			return
		if s[start] == '0':
			return
		x = 0
		j = 1
		for i in range(start, len(s)):
			if s[i] == '1':
				x += j
				if self.isPower(x, 5):
					self.solve(s, i + 1, count + 1, mcount)
			j *= 2

	def cuts(self, s):
		phase = 0
		ans = 0
		snum = 0
		dv = int(s, 2)
		if dv < 5:
			if dv == 1:
				return 1
			return -1
		if self.isPower(dv, 5):
			return 1
		rs = s[::-1]
		mcnt = [sys.maxsize - 1]
		self.solve(rs, 0, 0, mcnt)
		if mcnt[0] == sys.maxsize - 1:
			return -1
		return mcnt[0]

	def cuts_v1(self, s):
		phase = 0
		ans = 0
		snum = 0
		for i in range(len(s)):
			snum <<= 1
			if s[i] == '1':
				snum += 1
			if snum % 5 == 0:
				ans += 1
				snum = 0
		return ans if ans > 0 else -1


from math import inf, log

class Solution:

	def cuts(self, s):
		n = len(s)
		m = [inf] * n + [0]
		for i in range(n - 1, -1, -1):
			if s[i] == '0':
				continue
			x = 0
			for j in range(i, n):
				x = x * 2 + int(s[j])
				if 5 ** int(log(x, 5)) == x:
					m[i] = min(m[i], m[j + 1] + 1)
		return m[0] if m[0] != inf else -1


class Solution:

	def check(self, s):
		j = 1
		num = 0
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '1':
				num = num + j
			j *= 2
		while num > 1:
			if num % 5 != 0:
				return False
			num = num // 5
		return True

	def helper(self, ind, s):
		if ind >= len(s):
			return 1000000000.0
		if s[ind] == '0':
			return -1
		if self.check(s[ind:]) == True:
			return 1
		ans = 1000000000.0
		for i in range(ind, len(s)):
			if self.check(s[ind:i + 1]) == True:
				b = self.helper(i + 1, s)
				if b != -1:
					ans = min(ans, 1 + b)
		return ans

	def cuts(self, s):
		res = self.helper(0, s)
		if res == 1000000000.0:
			return -1
		return res


class Solution:

	def cuts(self, s):
		n = len(s)
		power = [1, 5, 25, 125, 625]
		binary = ['1', '101', '11001', '1111101', '1001110001']
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			for j in range(5):
				l = len(binary[j])
				if i >= l and s[i - l:i] == binary[j]:
					dp[i] = min(dp[i], dp[i - l] + 1)
		return dp[n] if dp[n] != float('inf') else -1


import math
import re

class Solution:

	def cuts(self, s):
		d = {}

		def generate_binary_powers(n):
			base = 5
			exponent = 0
			power = 1
			while power <= n:
				binary = bin(power)[2:]
				d[binary] = 1
				exponent += 1
				power = base ** exponent
		n = int(s, 2)
		generate_binary_powers(n)
		sorted_list = sorted(d.items(), key=lambda x: len(x[0]), reverse=True)
		cnt = 0
		for item in sorted_list:
			(key, value) = item
			if len(s) == 0:
				return cnt
			pattern = str(key)
			matches = re.findall(pattern, s)
			if matches:
				s = s.replace(key, '')
				cnt += len(matches)
		if len(s) == 0:
			return cnt
		return -1


from typing import *

class Solution:

	def cuts(self, s):
		n = len(s)

		def pow5(st, en):
			tmp = s[st:en + 1]
			val = int(tmp, 2)
			while val % 5 == 0:
				val //= 5
			return val == 1
		dp = {}

		def f(i: int) -> int:
			if i == n:
				return 0
			if s[i] == '0':
				return 1000000000.0
			if i in dp:
				return dp[i]
			dp[i] = 1000000000.0
			for j in range(i, n):
				if pow5(i, j):
					dp[i] = min(dp[i], 1 + f(j + 1))
			return dp[i]
		res = f(0)
		if res >= 1000000000.0:
			return -1
		return res


class Solution:

	def cuts(self, s):

		def ok(ss):
			n = int(ss, 2)
			while n > 1 and n % 5 == 0:
				n //= 5
			return n == 1
		n = len(s)
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for i in range(n):
			for k in range(i, -1, -1):
				if s[k] != '0' and ok(s[k:i + 1]):
					dp[i + 1] = min(dp[i + 1], dp[k] + 1)
		return dp[n] if dp[n] != float('inf') else -1


import math

class Solution:

	def cuts(self, s):

		def power(s, start, end):
			num = 0
			j = 1
			for i in range(end, start - 1, -1):
				if s[i] == '1':
					num += j
				j *= 2
			while num > 1:
				if num % 5 != 0:
					return False
				num /= 5
			return True

		def help(s, start, end):
			if start > end:
				return 0
			if s[start] == '0':
				return -1
			if power(s, start, end):
				return 1
			ans = end + 2
			for i in range(start, end + 1):
				if power(s, start, i):
					second = help(s, i + 1, end)
					if second != -1:
						ans = min(ans, 1 + second)
			return -1 if ans == end + 2 else ans
		lgt = len(s)
		return help(s, 0, lgt - 1)


import math
import sys

class Solution:

	def split(s, inx, n):
		if inx > n - 1:
			return 0
		if s[inx] == '0':
			return sys.maxsize
		bit = ''
		ans = sys.maxsize
		for i in range(inx, n):
			bit += s[i]
			num = int(bit, 2)
			if num > 0:
				res1 = math.log(num) // math.log(5)
				res2 = round(math.log(num) / math.log(5), 10)
				if res1 == res2:
					ans = min(ans, Solution.split(s, i + 1, n) + 1)
		return ans

	def cuts(self, s):
		n = len(s)
		ans = Solution.split(s, 0, n)
		return (ans, -1)[ans == sys.maxsize]


def pow_5(n):
	if n == 0:
		return False
	if n == 1:
		return True
	if n % 5 == 0:
		return pow_5(n / 5)
	return False

class Solution:

	def cuts(self, s):
		n = len(s)
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			j = i - 1
			if s[j] == '0':
				dp[i] = -1
			else:
				dp[i] = -1
				curr_ans = 1000000000
				dec = 0
				for k in range(i):
					if s[j - k] == '1':
						dec += 1 << k
						if pow_5(dec) and dp[j - k] != -1:
							curr_ans = min(1 + dp[j - k], curr_ans)
				if curr_ans != 1000000000:
					dp[i] = curr_ans
		return dp[n]


import math

class Solution:

	def cuts(self, s):

		def isPowerOf5(num):
			power = int(math.log(num, 5))
			return 5 ** power == num

		def countCutsHelper(ind):
			nonlocal ans
			if ind >= n:
				return 0
			if s[ind] == '0':
				return math.inf
			if ind in d:
				return d[ind]
			curNum = 0
			tempCuts = math.inf
			for i in range(ind, n):
				curNum = curNum * 2 + int(s[i])
				if isPowerOf5(curNum):
					tempCuts = min(tempCuts, 1 + countCutsHelper(i + 1))
			d[ind] = tempCuts
			return tempCuts
		n = len(s)
		d = {}
		ans = countCutsHelper(0)
		if ans == math.inf:
			return -1
		else:
			return ans


class Solution:

	def p(self, n):
		if n == 1:
			return True
		while n >= 5:
			if n % 5 != 0:
				return False
			n /= 5
		return n == 1

	def cuts(self, s):
		m = 0
		j = 0
		while len(s) - 1 >= 0:
			c = 0
			i = len(s)
			while True:
				if s[0] == '0':
					return -1
				if self.p(int(s[:i], 2)):
					s = s[i:]
					c += 1
					break
				elif i == 1:
					return -1
				i -= 1
			m += c
		if s != '':
			return -1
		return m


class Solution:

	def cuts(self, s):
		if not s:
			return -1
		if s[0] == '0':
			return -1
		(pow5, local, out) = (1, 0, 99)
		for i in range(len(s)):
			local *= 2
			if s[i] == '1':
				local += 1
			if local > pow5:
				pow5 *= 5
			if local == pow5:
				if i == len(s) - 1:
					return 1
				deeper = self.cuts(s[slice(i + 1, len(s) + 1)])
				if deeper != -1:
					out = min(deeper + 1, out)
		return out if out < 99 else -1


class Solution:

	def cuts(self, s):

		def check(s, start, end):
			num = 0
			j = 1
			for i in range(end, start - 1, -1):
				if s[i] == '1':
					num += j
				j *= 2
			while num > 1:
				if num % 5 != 0:
					return False
				num //= 5
			return True

		def recur(s, start, end, dp):
			if end < start:
				return 0
			if s[start] == '0':
				return -1
			if dp[start][end] != -1:
				return dp[start][end]
			if check(s, start, end):
				return 1
			ans = float('inf')
			for i in range(start, end + 1):
				if check(s, start, i):
					second = recur(s, i + 1, end, dp)
					if second != -1:
						ans = min(ans, 1 + second)
			dp[start][end] = -1 if ans == float('inf') else ans
			return dp[start][end]
		n = len(s)
		dp = [[-1] * n for _ in range(n)]
		return recur(s, 0, n - 1, dp)


import math
import re

class Solution:

	def cuts(self, s):
		d = {}

		def generate_bi_powers(n):
			be = 5
			exp = 0
			power = 1
			while power <= n:
				bi = bin(power)[2:]
				d[bi] = 1
				exp += 1
				power = be ** exp
		n = int(s, 2)
		generate_bi_powers(n)
		sorted_list = sorted(d.items(), key=lambda x: len(x[0]), reverse=True)
		count = 0
		for item in sorted_list:
			(key, value) = item
			if len(s) == 0:
				return count
			pattern = str(key)
			matches = re.findall(pattern, s)
			if matches:
				s = s.replace(key, '')
				count += len(matches)
		if len(s) == 0:
			return count
		return -1


class Solution:
	st = set()

	@staticmethod
	def initialize():
		p = 1
		for i in range(1, 23):
			Solution.st.add(bin(p)[2:])
			p *= 5

	@staticmethod
	def helper(s, idx):
		if idx >= len(s):
			return 0
		ans = float('inf')
		for i in range(idx, len(s)):
			substring = s[idx:i + 1]
			if substring in Solution.st:
				ans = min(ans, 1 + Solution.helper(s, i + 1))
		return ans

	@staticmethod
	def cuts(s):
		Solution.initialize()
		ans = Solution.helper(s, 0)
		return -1 if ans == float('inf') else ans


class Solution:

	def is_power_of_5(self, n):
		while n % 5 == 0:
			n //= 5
		return n == 1

	def cuts(self, s):
		n = len(s)
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			for j in range(i):
				num = int(s[j:i], 2)
				if s[j] == '0':
					continue
				if self.is_power_of_5(num):
					dp[i] = min(dp[i], dp[j] + 1)
		return dp[n] if dp[n] != float('inf') else -1