Binary Search approach
- Binary Search: The approach performs a binary search on the range from 0 to N-1 (where N is the length of the string S). For each mid value, it checks if it’s possible to make all characters from index 0 to mid ‘0’ by using at most K operations or not.
- Checking Possibility: The possible() function checks if it’s possible to make all characters from index 0 to mid ‘0’. It does this by iterating from mid to 0 and for each character, it calculates the required operations to make it ‘0’. If at any point, the total required operations exceed K, it returns false. Otherwise, it returns true.
- Updating Answer: If it’s possible to make all characters from index 0 to mid ‘0’, then mid+1 is a potential answer and we try to find a bigger answer in the range from mid+1 to high. Otherwise, we try to find an answer in the range from low to mid-1.
- Results: Finally, after the binary search ends, We have the maximum length of a prefix with all zeros, after that we can get the minimum sum of suffix easily.
This approach ensures that we find the maximum length in O(N*log N) time complexity where N is the length of the string.
Steps were taken to solve the problem:
- Create two variables let say low and high and initialize them as 0 and N-1 respectively.
- Declare a variable let say Count to store the length of longest prefix of zeros.
- While (low <= high)
- mid = low + (high-low)/2
- If (possible (mid, S, K))
- Count = mid + 1
- low = mid + 1
- Else
- high = mid – 1
- Declare a variable let say Min_sum to count the minimum sum.
- Iterate over the suffix after the longest prefix of zeros and calculate the sum of digits into Min_sum
- Output Min_sum.
Code to implement the approach:
C++
#include <iostream> using namespace std; // Function to check the possibility of making a prefix of zeros till the mid index bool possible( int mid, const string& s, int k) { int op = 0, req = 0; // Iterate from mid to 0 for ( int i = mid; i >= 0; i--) { // Calculate the required operations to make the character '0' req = ((s[i] - '0' ) + op) % 10; if (req != 0) { // Update the total required operations op += (10 - req); } } // Check if the total required operations do not exceed k return op <= k; } // Function to find the minimum possible sum of digits void Min_sum( int N, int K, const string& S) { // Binary search approach int low = 0, high = N - 1; // Variable to count the length of the longest prefix of zeros int count = 0; // Binary Search algorithm while (low <= high) { int mid = (low + high) / 2; // Check if it's possible to make all characters from index 0 to mid '0' if (possible(mid, S, K)) { // Update the answer count = mid + 1; // Search in the right half low = mid + 1; } else { // Search in the left half high = mid - 1; } } // Variable to store the minimum_sum int min_sum = 0; // Loop to calculate the sum of the suffix after the longest prefix of zeros for ( int i = count; i < N; i++) { min_sum += (S[i] - '0' ); } // Printing the minimum possible sum of digits of S cout << min_sum << endl; } // Driver Function int main() { // Input int N = 5; int K = 13; string S = "78712" ; // Function call Min_sum(N, K, S); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver class class GFG { // Driver Function public static void main(String[] args) { // Input int N = 5 ; int K = 13 ; String S = " 78712 "; // Function call Min_sum(N, K, S); } public static void Min_sum( int N, int K, String S) { // Binary search approach int low = 0 , high = N - 1 ; // Variable to count the length of // longest prefix of zeros int count = 0 ; // Binary Search algo while (low <= high) { int mid = (low + high) / 2 ; // Check if it's possible to // make all characters from // index 0 to mid '0' if (possible(mid, S, K)) { // Update the answer count = mid + 1 ; // Search in the right half low = mid + 1 ; } // Search in the left half else { high = mid - 1 ; } } // Variable to store the minimum_sum int min_sum = 0 ; // Loop for calculate sum of // suffix after the longest prefix // of zeros for ( int i = count; i < S.length(); i++) { min_sum += (S.charAt(i) - '0' ); } // Printing the min possible sum // of digits of S System.out.println(min_sum); } // Method to check the possiblity of // making prefix of zeros till mid index static boolean possible( int mid, String s, int k) { int op = 0 , req = 0 ; // Iterate from mid to 0 for ( int i = mid; i >= 0 ; i--) // Calculate the required operations // to make the character '0' { req = ((s.charAt(i) - '0' ) + op) % 10 ; if (req != 0 ) // Update the total // required operations op += ( 10 - req); } // Check if the total required // operations do not exceed k return op <= k; } } |
Python3
# Python program for the above approach def possible(mid, s, k): op = 0 req = 0 # Iterate from mid to 0 for i in range (mid, - 1 , - 1 ): # Calculate the required operations to make the character '0' req = (( ord (s[i]) - ord ( '0' )) + op) % 10 if req ! = 0 : # Update the total required operations op + = ( 10 - req) # Check if the total required operations do not exceed k return op < = k def min_sum(n, k, s): # Binary search approach low = 0 high = n - 1 # Variable to count the length of the longest prefix of zeros count = 0 # Binary Search algorithm while low < = high: mid = (low + high) / / 2 # Check if it's possible to make all characters from index 0 to mid '0' if possible(mid, s, k): # Update the answer count = mid + 1 # Search in the right half low = mid + 1 else : # Search in the left half high = mid - 1 # Variable to store the minimum_sum min_sum = 0 # Loop to calculate the sum of the suffix after the longest prefix of zeros for i in range (count, n): min_sum + = int (s[i]) # Printing the minimum possible sum of digits of S print (min_sum) # Driver Function if __name__ = = "__main__" : # Input N = 5 K = 13 S = "78712" # Function call min_sum(N, K, S) # This code is contributed by Susobhan Akhuli |
C#
// C# program for the above approach using System; public class GFG { // Function to check the possibility of making a prefix // of zeros till the mid index static bool Possible( int mid, string s, int k) { int op = 0, req = 0; // Iterate from mid to 0 for ( int i = mid; i >= 0; i--) { // Calculate the required operations to make the // character '0' req = ((s[i] - '0' ) + op) % 10; if (req != 0) { // Update the total required operations op += (10 - req); } } // Check if the total required operations do not // exceed k return op <= k; } // Function to find the minimum possible sum of digits static void MinSum( int N, int K, string S) { // Binary search approach int low = 0, high = N - 1; // Variable to count the length of the longest // prefix of zeros int count = 0; // Binary Search algorithm while (low <= high) { int mid = (low + high) / 2; // Check if it's possible to make all characters // from index 0 to mid '0' if (Possible(mid, S, K)) { // Update the answer count = mid + 1; // Search in the right half low = mid + 1; } else { // Search in the left half high = mid - 1; } } // Variable to store the minimum_sum int minSum = 0; // Loop to calculate the sum of the suffix after the // longest prefix of zeros for ( int i = count; i < N; i++) { minSum += (S[i] - '0' ); } // Printing the minimum possible sum of digits of S Console.WriteLine(minSum); } // Driver Function public static void Main() { // Input int N = 5; int K = 13; string S = "78712" ; // Function call MinSum(N, K, S); } } // This code is contributed by Susobhan Akhuli |
Javascript
// Function to check the possibility of making a prefix of zeros till the mid index function possible(mid, s, k) { let op = 0, req = 0; // Iterate from mid to 0 for (let i = mid; i >= 0; i--) { // Calculate the required operations to make the character '0' req = ((parseInt(s[i]) - 0) + op) % 10; if (req !== 0) { // Update the total required operations op += (10 - req); } } // Check if the total required operations do not exceed k return op <= k; } // Function to find the minimum possible sum of digits function Min_sum(N, K, S) { // Binary search approach let low = 0, high = N - 1; // Variable to count the length of the longest prefix of zeros let count = 0; // Binary Search algorithm while (low <= high) { let mid = Math.floor((low + high) / 2); // Check if it's possible to make all characters from index 0 to mid '0' if (possible(mid, S, K)) { // Update the answer count = mid + 1; // Search in the right half low = mid + 1; } else { // Search in the left half high = mid - 1; } } // Variable to store the minimum_sum let min_sum = 0; // Loop to calculate the sum of the suffix after the longest prefix of zeros for (let i = count; i < N; i++) { min_sum += (parseInt(S[i]) - 0); } // Printing the minimum possible sum of digits of S console.log(min_sum); } // Driver Function function main() { // Input let N = 5; let K = 13; let S = "78712" ; // Function call Min_sum(N, K, S); } // Call the main function to start the program main(); //This cide is contributed by Adarsh. |
3
Time Complexity: O(N*logN)
Auxiliary space: O(1)
Find the minimum possible sum that can be made by the digits of given String
Given a string S of length N along with K, the task is to output the minimum sum of suffix after making the longest prefix of zeros that can be obtained by applying the given operation at most K times. Then you can apply the given operation on S:
- Choose an index let’s say i (1 <= i <= N)
- Do this for each digit of S[1, i]
- Replace the digit with the remainder after incrementing it by one and then dividing it by 10.
Examples:
Input: N = 3, K = 9, S = “380”
Output: 0
Explanation: The series of operations is performed as:
- First Operation: Choose i = 2, We will apply operation on S[1, 2], then:
- Initially, S[1] = 3 and S[2] = 8. During operation: S[1] = (S[1]+1)%10 and S[2] = (S[2]+1)%10, then S[1] and S[2] are 4,9 respectively. Updated S = “490”
- Second Operation: Choose again, i = 2, We will apply operation on S[1, 2], then:
- Initially, S[1] = 4 and S[2] = 9. During operation: S[1] = (S[1]+1)%10 and S[2] = (S[2]+1)%10, then S[1] and S[2] are 5,0 respectively. Updated S = “500”
- Next 5 operations: Choose, i = 1, We will apply operation on S[1, 1], then:
- Initially, S[1] = 5. During operation: S[1] = (S[1]+1)%10, then S[1] = 0. Updated S = “000”
So, the length longest prefix that can be made using a given operation is obtained by using 7 (at most K = 9) operations. No digit is remained in the suffix after making it of all zeros. So the minimum sum of suffixes will be 0.
Input: N = 5, K = 13, S = “78712”
Output: 3
Explanation: It can be verified that the longest suffix of length 3 will formed in exactly 13 operations. Then Suffix S[4, 5] = 12 will remain. Whose sum is 3. Therefore, output is 3.
Approach: To solve the problem follow the below idea:
The main crux of the problem is to maximize the length of the prefix formed by zero. So that the sum formed by remaining digits will be lower itself. This problem is based on the Greedy logic. Now, let us see the different approaches to solve the problem.
In this approach we will maximizing the length of a prefix with all zeros in at most K times. Which is based on greedy algorithm. Here are the steps:
- Greedy logic: We have to iterate over each character in the string from left to right. For each character, We need to calculate the minimum number of operations required to make it ‘0’. This is done by subtracting the character’s value from 10 and taking the modulus 10.
- Checking Possibility: If at any point, the required operations for a character exceed the remaining operations, then break out of the loop. Otherwise, increment a counter (representing the length of the prefix with all zeros) and updates the remaining operations.
- results: Finally, after iterating over all characters or until no more operations can be performed, count the sum of suffix remained after the longest prefix of zeros. Calculate the sum of digits in that suffix and print it.
This approach ensures that we find the maximum length in O(N) time complexity where N is the length of the string.
Steps were taken to solve the problem:
- Declare a variable let say Count, to calculate the length longest prefix of zeros.
- Run a loop for i = 0 to i < S.length() and follow below mentioned steps under the scope of loop:
- num = (int)(S.charAt(i) – ‘0’)
- diff = (10 – num) % 10
- If(K < diff)
- break
- Count++
- K = ((K – diff) / 10) * 10 + diff
- Declare a variable let say Min_sum to count the minimum sum.
- Iterate over the suffix after the longest prefix of zeros and calculate the sum of digits into Min_sum
- Output Min_sum.
Code to implement the approach:
C++
#include <iostream> #include <string> using namespace std; // Function to calculate the minimum possible sum of digits void Min_sum( int N, int K, string S) { // Variable to count the max length of prefix of only zeros int count = 0; // Loop for applying the approach for ( int i = 0; i < S.length(); i++) { // Get the value of the character int num = static_cast < int >(S[i] - '0' ); // Calculate the minimum operations required to make it '0' int diff = (10 - num) % 10; // If required operations exceed remaining operations, break if (K < diff) { break ; } // Increment the counter count++; // Update the remaining operations K = ((K - diff) / 10) * 10 + diff; } // Variable to store the minimum_sum int min_sum = 0; // Loop to calculate the sum of suffix after the longest prefix of zeros for ( int i = count; i < S.length(); i++) { min_sum += (S[i] - '0' ); } // Printing the min possible sum of digits of S cout << min_sum << endl; } // Driver Function int main() { // Input int N = 3; int K = 9; string S = "380" ; // Function call Min_sum(N, K, S); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver class class GFG { // Driver Function public static void main(String[] args) { // Input int N = 3 ; int K = 9 ; String S = " 380 "; // Function call Min_sum(N, K, S); } public static void Min_sum( int N, int K, String S) { // Variable to count the max // length of prefix of only zeros int count = 0 ; // Loop for applying the approach for ( int i = 0 ; i < S.length(); i++) { // Get the value of the // character int num = ( int )(S.charAt(i) - '0' ); // Calculate the minimum operations // required to make it '0' int diff = ( 10 - num) % 10 ; // If required operations exceed // remaining operations, break if (K < diff) { break ; } // Increment the counter count++; // Update the remaining operations K = ((K - diff) / 10 ) * 10 + diff; } // Variable to store the minimum_sum int min_sum = 0 ; // Loop for calculate sum of // suffix after the longest prefix // of zeros for ( int i = count; i < S.length(); i++) { min_sum += (S.charAt(i) - '0' ); } // Printing the min possible sum // of digits of S System.out.println(min_sum); } } |
Python3
def min_sum(N, K, S): # Variable to count the max length of prefix of only zeros count = 0 # Loop for applying the approach for i in range ( len (S)): # Get the value of the character num = int (S[i]) # Calculate the minimum operations required to make it '0' diff = ( 10 - num) % 10 # If required operations exceed remaining operations, break if K < diff: break # Increment the counter count + = 1 # Update the remaining operations K = ((K - diff) / / 10 ) * 10 + diff # Variable to store the minimum_sum min_sum = 0 # Loop to calculate the sum of suffix after the longest prefix of zeros for i in range (count, len (S)): min_sum + = int (S[i]) # Printing the min possible sum of digits of S print (min_sum) # Driver Function if __name__ = = "__main__" : # Input N = 3 K = 9 S = "380" # Function call min_sum(N, K, S) # This code is contributed by shivamgupta0987654321 |
C#
using System; class Program { // Function to calculate the minimum possible sum of digits static void MinSum( int N, int K, string S) { // Variable to count the max length of prefix of only zeros int count = 0; // Loop for applying the approach for ( int i = 0; i < S.Length; i++) { // Get the value of the character int num = ( int )(S[i] - '0' ); // Calculate the minimum operations required to make it '0' int diff = (10 - num) % 10; // If required operations exceed remaining operations, break if (K < diff) { break ; } // Increment the counter count++; // Update the remaining operations K = ((K - diff) / 10) * 10 + diff; } // Variable to store the minimum_sum int minSum = 0; // Loop to calculate the sum of suffix after the longest prefix of zeros for ( int i = count; i < S.Length; i++) { minSum += (S[i] - '0' ); } // Printing the min possible sum of digits of S Console.WriteLine(minSum); } // Driver Function static void Main() { // Input int N = 3; int K = 9; string S = "380" ; // Function call MinSum(N, K, S); } } |
Javascript
// Function to calculate the minimum // possible sum of digits function minSum(N, K, S) { // Variable to count the max length // of prefix of only zeros let count = 0; // Loop for applying the approach for (let i = 0; i < S.length; i++) { // Get the value of the character let num = parseInt(S[i]); // Calculate the minimum operations // required to make it '0' let diff = (10 - num) % 10; // If required operations exceed // remaining operations, break if (K < diff) { break ; } // Increment the counter count++; // Update the remaining operations K = Math.floor((K - diff) / 10) * 10 + diff; } // Variable to store the minimum_sum let minSum = 0; // Loop to calculate the sum of suffix // after the longest prefix of zeros for (let i = count; i < S.length; i++) { minSum += parseInt(S[i]); } // Printing the min possible // sum of digits of S console.log(minSum); } // Driver Function // Input let N = 3; let K = 9; let S = "380" ; // Function call minSum(N, K, S); |
0
Time Complexity: O(N)
Auxiliary Space: O(1)