Given a binary string str. The task is to find the smallest positive integer C such that the binary string can be cut into C pieces (sub-strings) and each sub-string should be a power of 5 with no leading zeros.
Examples:
Input: str = “101101101”
Output: 3
The string “101101101” can be cut into three binary strings “101”, “101”, “101”
each of which is a power of 5.
Input: str = “1111101”
Output: 1
The string “1111101” can be cut into one binary string “1111101” which is
125 in decimal and a power of 5.
Input: str = “00000”
Output: -1
Strings of only zeroes is equivalent to 0 which is not a power of 5.
Approach: This problem is a simple variation of the longest increasing sub-sequence.
Iterate from i = 1 and for every str[j…i] where j = 0 & j < i, we check if the number formed from str[j..i] is a power of 5 then we update the dp[] array with the value of the lowest possible cut size value. After confirming that the number formed from str[j..i] in decimal is a power of 5 we calculate dp[i] = min(dp[i], dp[j] + 1).
This technique is pretty similar to finding the longest increasing sub-sequence.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define ll unsigned long long// Function that returns true// if n is a power of 5bool ispower(ll n){ if (n < 125) return (n == 1 || n == 5 || n == 25); if (n % 125 != 0) return false; else return ispower(n / 125);}// Function to return the decimal// value of binary equivalentll number(string s, int i, int j){ ll ans = 0; for (int x = i; x < j; x++) { ans = ans * 2 + (s[x] - '0'); } return ans;}// Function to return the minimum cuts requiredint minCuts(string s, int n){ int dp[n + 1]; // Allocating memory for dp[] array memset(dp, n + 1, sizeof(dp)); dp[0] = 0; // From length 1 to n for (int i = 1; i <= n; i++) { // If previous character is '0' then ignore // to avoid number with leading 0s. if (s[i - 1] == '0') continue; for (int j = 0; j < i; j++) { // Ignore s[j] = '0' starting numbers if (s[j] == '0') continue; // Number formed from s[j....i] ll num = number(s, j, i); // Check for power of 5 if (!ispower(num)) continue; // Assigning min value to get min cut possible dp[i] = min(dp[i], dp[j] + 1); } } // (n + 1) to check if all the strings are traversed // and no divisible by 5 is obtained like 000000 return ((dp[n] < n + 1) ? dp[n] : -1);}// Driver codeint main(){ string s = "101101101"; int n = s.length(); cout << minCuts(s, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Function that returns true // if n is a power of 5 static boolean ispower(long n) { if (n < 125) { return (n == 1 || n == 5 || n == 25); } if (n % 125 != 0) { return false; } else { return ispower(n / 125); } } // Function to return the decimal // value of binary equivalent static long number(String s, int i, int j) { long ans = 0; for (int x = i; x < j; x++) { ans = ans * 2 + (s.charAt(x) - '0'); } return ans; } // Function to return the minimum cuts required static int minCuts(String s, int n) { int[] dp = new int[n + 1]; // Alongocating memory for dp[] array Arrays.fill(dp, n+1); dp[0] = 0; // From length 1 to n for (int i = 1; i <= n; i++) { // If previous character is '0' then ignore // to avoid number with leading 0s. if (s.charAt(i - 1) == '0') { continue; } for (int j = 0; j < i; j++) { // Ignore s[j] = '0' starting numbers if (s.charAt(j) == '0') { continue; } // Number formed from s[j....i] long num = number(s, j, i); // Check for power of 5 if (!ispower(num)) { continue; } // Assigning min value to get min cut possible dp[i] = Math.min(dp[i], dp[j] + 1); } } // (n + 1) to check if all the Strings are traversed // and no divisible by 5 is obtained like 000000 return ((dp[n] < n + 1) ? dp[n] : -1); } // Driver code public static void main(String[] args) { String s = "101101101"; int n = s.length(); System.out.println(minCuts(s, n)); }}// This code is contributed by 29AjayKumar |
Python 3
# Python 3 implementation of the approach # Function that returns true# if n is a power of 5def ispower( n): if (n < 125): return (n == 1 or n == 5 or n == 25) if (n % 125 != 0): return 0 else: return ispower(n // 125) # Function to return the decimal# value of binary equivalentdef number(s, i, j): ans = 0 for x in range( i, j) : ans = ans * 2 + (ord(s[x]) - ord('0')) return ans# Function to return the minimum cuts requireddef minCuts(s, n): # Allocating memory for dp[] array dp=[n+1 for i in range(n+1)] dp[0] = 0; # From length 1 to n for i in range(1, n+1) : # If previous character is '0' then ignore # to avoid number with leading 0s. if (s[i - 1] == '0'): continue for j in range(i) : # Ignore s[j] = '0' starting numbers if (s[j] == '0'): continue # Number formed from s[j....i] num = number(s, j, i) # Check for power of 5 if (not ispower(num)): continue # Assigning min value to get min cut possible dp[i] = min(dp[i], dp[j] + 1) # (n + 1) to check if all the strings are traversed # and no divisible by 5 is obtained like 000000 if dp[n] < n + 1: return dp[n] else: return -1 # Driver codeif __name__== "__main__": s = "101101101" n = len(s) print(minCuts(s, n))# This code is contributed by ChitraNayal |
C#
// C# implementation of the approachusing System;class GFG{ // Function that returns true // if n is a power of 5 static Boolean ispower(long n) { if (n < 125) { return (n == 1 || n == 5 || n == 25); } if (n % 125 != 0) { return false; } else { return ispower(n / 125); } } // Function to return the decimal // value of binary equivalent static long number(String s, int i, int j) { long ans = 0; for (int x = i; x < j; x++) { ans = ans * 2 + (s[x] - '0'); } return ans; } // Function to return the minimum cuts required static int minCuts(String s, int n) { int[] dp = new int[n + 1]; // Alongocating memory for dp[] array for (int i = 0; i <= n; i++) dp[i]=n+1; dp[0] = 0; // From length 1 to n for (int i = 1; i <= n; i++) { // If previous character is '0' then ignore // to avoid number with leading 0s. if (s[i - 1] == '0') { continue; } for (int j = 0; j < i; j++) { // Ignore s[j] = '0' starting numbers if (s[j] == '0') { continue; } // Number formed from s[j....i] long num = number(s, j, i); // Check for power of 5 if (!ispower(num)) { continue; } // Assigning min value to get min cut possible dp[i] = Math.Min(dp[i], dp[j] + 1); } } // (n + 1) to check if all the Strings are traversed // and no divisible by 5 is obtained like 000000 return ((dp[n] < n + 1) ? dp[n] : -1); } // Driver code public static void Main(String[] args) { String s = "101101101"; int n = s.Length; Console.WriteLine(minCuts(s, n)); }}/* This code contributed by PrinciRaj1992 */ |
PHP
<?php// PHP implementation of the approach // Function that returns true // if n is a power of 5 function ispower($n) { if ($n < 125) return ($n == 1 || $n == 5 || $n == 25); if ($n % 125 != 0) return false; else return ispower($n / 125); } // Function to return the decimal // value of binary equivalent function number($s, $i, $j) { $ans = 0; for ($x = $i; $x < $j; $x++) { $ans = $ans * 2 + (ord($s[$x]) - ord('0')); } return $ans; } // Function to return the minimum cuts required function minCuts($s, $n) { // Allocating memory for dp[] array $dp = array_fill(0,$n + 1,$n + 1); $dp[0] = 0; // From length 1 to n for ($i = 1; $i <= $n; $i++) { // If previous character is '0' then ignore // to avoid number with leading 0s. if ($s[$i - 1] == '0') continue; for ($j = 0; $j < $i; $j++) { // Ignore s[j] = '0' starting numbers if ($s[$j] == '0') continue; // Number formed from s[j....i] $num = number($s, $j, $i); // Check for power of 5 if (!ispower($num)) continue; // Assigning min value to get min cut possible $dp[$i] = min($dp[$i], $dp[$j] + 1); } } // (n + 1) to check if all the strings are traversed // and no divisible by 5 is obtained like 000000 return (($dp[$n] < $n + 1) ? $dp[$n] : -1); } // Driver code $s = "101101101"; $n = strlen($s); echo minCuts($s, $n); // This code is contributed by AnkitRai01?> |
Javascript
<script>// Javascript implementation of the approach// Function that returns true// if n is a power of 5function ispower(n){ if (n < 125) return (n == 1 || n == 5 || n == 25); if (n % 125 != 0) return false; else return ispower(parseInt(n / 125));}// Function to return the decimal// value of binary equivalentfunction number(s, i, j){ var ans = 0; for (var x = i; x < j; x++) { ans = ans * 2 + (s[x] - '0'); } return ans;}// Function to return the minimum cuts requiredfunction minCuts(s, n){ var dp = Array(n+1).fill(n+1); dp[0] = 0; // From length 1 to n for (var i = 1; i <= n; i++) { // If previous character is '0' then ignore // to avoid number with leading 0s. if (s[i - 1] == '0') continue; for (var j = 0; j < i; j++) { // Ignore s[j] = '0' starting numbers if (s[j] == '0') continue; // Number formed from s[j....i] var num = number(s, j, i); // Check for power of 5 if (!ispower(num)) continue; // Assigning min value to get min cut possible dp[i] = Math.min(dp[i], dp[j] + 1); } } // (n + 1) to check if all the strings are traversed // and no divisible by 5 is obtained like 000000 return ((dp[n] < n + 1) ? dp[n] : -1);}// Driver codevar s = "101101101";var n = s.length;document.write( minCuts(s, n));</script> |
Output:
3
Time complexity: O(n2)
Space complexity: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
