Minimum number of sets with numbers less than Y
Given a string of consecutive digits and a number Y, the task is to find the number of minimum sets such that every set follows the below rule:
- Set should contain consecutive numbers
- No digit can be used more than once.
- The number in the set should not be more than Y.
Examples:
Input: s = "1234", Y = 30 Output: 3 Three sets of {12, 3, 4} Input: s = "1234", Y = 4 Output: 4 Four sets of {1}, {2}, {3}, {4}
Approach: The following problem can be solved using a greedy approach whose steps are given below:
- Iterate in the string, and concatenate the number to a variable(let say num) using num*10 + (s[i]-‘0’)
- If the number is not greater than Y, then mark f = 1.
- If the number exceeds Y, then increase count if f = 1 and re-initialize f as 0 and also initialize num as s[i]-‘0’ or num as 0.
- After iterating in the string completely, then increase the count if f is 1.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum number // sets with consecutive numbers and less than Y #include <bits/stdc++.h> using namespace std; // Function to find the minimum number of shets int minimumSets(string s, int y) { // Variable to count // the number of sets int cnt = 0; int num = 0; int l = s.length(); int f = 0; // Iterate in the string for ( int i = 0; i < l; i++) { // Add the number to string num = num * 10 + (s[i] - '0' ); // Mark that we got a number if (num <= y) f = 1; else // Every time it exceeds { // Check if previous was // anytime less than Y if (f) cnt += 1; // Current number num = s[i] - '0' ; f = 0; // Check for current number if (num <= y) f = 1; else num = 0; } } // Check for last added number if (f) cnt += 1; return cnt; } // Driver Code int main() { string s = "1234" ; int y = 30; cout << minimumSets(s, y); return 0; } |
Java
// Java program to find the minimum number // sets with consecutive numbers and less than Y import java.util.*; class solution { // Function to find the minimum number of shets static int minimumSets(String s, int y) { // Variable to count // the number of sets int cnt = 0 ; int num = 0 ; int l = s.length(); boolean f = false ; // Iterate in the string for ( int i = 0 ; i < l; i++) { // Add the number to string num = num * 10 + (s.charAt(i) - '0' ); // Mark that we got a number if (num <= y) f = true ; else // Every time it exceeds { // Check if previous was // anytime less than Y if (f) cnt += 1 ; // Current number num = s.charAt(i) - '0' ; f = false ; // Check for current number if (num <= y) f = true ; else num = 0 ; } } // Check for last added number if (f == true ) cnt += 1 ; return cnt; } // Driver Code public static void main(String args[]) { String s = "1234" ; int y = 30 ; System.out.println(minimumSets(s, y)); } } // This code is contributed by // Shashank_Sharma |
Python3
# Python3 program to find the minimum number # sets with consecutive numbers and less than Y import math as mt # Function to find the minimum number of shets def minimumSets(s, y): # Variable to count the number of sets cnt = 0 num = 0 l = len (s) f = 0 # Iterate in the string for i in range (l): # Add the number to string num = num * 10 + ( ord (s[i]) - ord ( '0' )) # Mark that we got a number if (num < = y): f = 1 else : # Every time it exceeds # Check if previous was anytime # less than Y if (f): cnt + = 1 # Current number num = ord (s[i]) - ord ( '0' ) f = 0 # Check for current number if (num < = y): f = 1 else : num = 0 # Check for last added number if (f): cnt + = 1 return cnt # Driver Code s = "1234" y = 30 print (minimumSets(s, y)) # This code is contributed by # Mohit kumar 29 |
C#
// C# program to find the minimum number // sets with consecutive numbers and less than Y using System; class solution { // Function to find the minimum number of shets static int minimumSets( string s, int y) { // Variable to count // the number of sets int cnt = 0; int num = 0; int l = s.Length ; bool f = false ; // Iterate in the string for ( int i = 0; i < l; i++) { // Add the number to string num = num * 10 + (s[i] - '0' ); // Mark that we got a number if (num <= y) f = true ; else // Every time it exceeds { // Check if previous was // anytime less than Y if (f) cnt += 1; // Current number num = s[i] - '0' ; f = false ; // Check for current number if (num <= y) f = true ; else num = 0; } } // Check for last added number if (f == true ) cnt += 1; return cnt; } // Driver Code public static void Main() { string s = "1234" ; int y = 30; Console.WriteLine(minimumSets(s, y)); } // This code is contributed by Ryuga } |
PHP
<?php // PHP program to find the minimum number // sets with consecutive numbers and less than Y // Function to find the minimum number of shets function minimumSets( $s , $y ) { // Variable to count // the number of sets $cnt = 0; $num = 0; $l = strlen ( $s ); $f = 0; // Iterate in the string for ( $i = 0; $i < $l ; $i ++) { // Add the number to string $num = $num * 10 + ( $s [ $i ] - '0' ); // Mark that we got a number if ( $num <= $y ) $f = 1; else // Every time it exceeds { // Check if previous was // anytime less than Y if ( $f ) $cnt += 1; // Current number $num = $s [ $i ] - '0' ; $f = 0; // Check for current number if ( $num <= $y ) $f = 1; else $num = 0; } } // Check for last added number if ( $f ) $cnt += 1; return $cnt ; } // Driver Code $s = "1234" ; $y = 30; echo (minimumSets( $s , $y )); //This code is contributed by Shivi_Aggarwal ?> |
Javascript
<script> // Javascript program to find the minimum number // sets with consecutive numbers and less than Y // Function to find the minimum number of shets function minimumSets(s, y) { // Variable to count // the number of sets let cnt = 0; let num = 0; let l = s.length; let f = false ; // Iterate in the string for (let i = 0; i < l; i++) { // Add the number to string num = num * 10 + (s[i] - '0' ); // Mark that we got a number if (num <= y) f = true ; else // Every time it exceeds { // Check if previous was // anytime less than Y if (f) cnt += 1; // Current number num = s[i] - '0' ; f = false ; // Check for current number if (num <= y) f = true ; else num = 0; } } // Check for last added number if (f == true ) cnt += 1; return cnt; } // Driver code let s = "1234" ; let y = 30; document.write(minimumSets(s, y)); </script> |
Output:
3
Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the length of the string.
Auxiliary Space: O(1), as we are not using any extra space.