Given a string S of length N consisting of digits and an integer K, Reduce the string by performing the following operation till the length of the string is greater than K:
- Divide the string into consecutive groups of size K such that the first K characters are in the first group, the next K characters are in the second group, and so on. Note that the size of the last group can be smaller than K.
- Merge the digit sum of consecutive groups together to form a new string. If the length of the string is greater than K, repeat the steps.
Examples:
Input: S = “11111222223”, K = 3
Output: “135”
Explanation:
For the first round, divide S into groups of size 3: “111”, “112”, “222”, and “23”.
Then calculate the digit sum of each group:
1 + 1 + 1 = 3, 1 + 1 + 2 = 4, 2 + 2 + 2 = 6, and 2 + 3 = 5.
So, string becomes “3” + “4” + “6” + “5” = “3465”.
For the second round, divide s into “346” and “5”.
Then calculate the digit sum of each group: 3 + 4 + 6 = 13, 5 = 5.
So, string becomes “13” + “5” = “135”.
After second round. Now, length of S <= K, so return “135” as the answer.Input: S = “1123”, K = 2
Output: “25”
Explanation: For the first round, divide S into groups of size 2: “11”, “23”.
Then we calculate the digit sum of each group: 1 + 1 = 2 and 2 + 3 = 5.
So, String becomes “2” + “5” = “25” after the first round.
Now, length of S <= K, so return “25” as the answer.
Approach: This is a simple implementation based problem. The solution is as follows:
Iterate S until its size is greater than K. In every iteration, divide the string in consecutive K sized groups, get their sum and add them to form the new string.
Follow the below steps to implement the idea:
- Run a loop until the given string S has length greater than K.
- Take one new string (say temp) to store the new string.
- Traverse string S from i = 0 to i = s.size() – 1.
- Define a variable (say sum = 0) to store the sum.
- Iterate in a group of K characters and keep storing the digit sum of K digits.
- Append the sum in temp string.
- Make S = temp, i.e. same as the newly formed string.
- Return S as the final string.
Below is the implementation for the above approach:
C++
// C++ code to implement the approach\#include <bits/stdc++.h>using namespace std;// Function for finding the sum of Digits// of number in group of kstring digitSum(string s, int k){ // Run the loop until given string s // length is greater than k otherwise // return the string while (s.size() > k) { // Temp variable to store new string string temp = ""; for (int i = 0; i < s.size(); i++) { int sum = 0; int count = 0; // Run the loop until count is // less than k or iterator is // less than the size of string while (i < s.size() && count < k) { // Sum up the string value sum += s[i++] - '0'; // Increase the count count++; } // Add the obtained sum to the // temp variable temp += to_string(sum); i--; } // Update the value of main string s = temp; } // Return the final string return s;}// Driver codeint main(){ string S = "11111222223"; int K = 3; // Function call string ans = digitSum(S, K); cout << ans << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function for finding the sum of Digits // of number in group of k public static String digitSum(String s, int k) { // Run the loop until given string s // length is greater than k otherwise // return the string while (s.length() > k) { // Temp variable to store new string String temp = ""; for (int i = 0; i < s.length(); i++) { int sum = 0; int count = 0; // Run the loop until count is // less than k or iterator is // less than the size of string while (i < s.length() && count < k) { // Sum up the string value sum += s.charAt(i++) - '0'; // Increase the count count++; } // Add the obtained sum to the // temp variable temp += Integer.toString(sum); i--; } // Update the value of main string s = temp; } // Return the final string return s; } // Driver Code public static void main(String[] args) { String S = "11111222223"; int K = 3; // Function call String ans = digitSum(S, K); System.out.println(ans); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach# Function for finding the sum of Digits# of number in group of kdef digitSum(s,k): # Run the loop until given string s # length is greater than k otherwise # return the string while(len(s)>k): # Temp variable to store new string temp="" # using while loop instead of for loop # because there is need to change value # of i which is not possible in python # in for loop i=0 while(i<len(s)): Sum=0 count=0 # Run the loop until count is # less than k or iterator is # less than the size of string while(i<len(s) and count<k): # Sum up the string value Sum = Sum + int(s[i]) i=i+1 # Increase the count count=count+1 # Add the obtained sum to the # temp variable temp = temp+str(Sum) i=i-1 # Increment to make while loop Run # like for loop i=i+1 # Update the value of main string s=temp # Return the final string return s # Driver codeS = "11111222223"K = 3# Function callans = digitSum(S,K)print(ans)# This code is contributed by Pushpesh Raj |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function for finding the sum of Digits // of number in group of k public static string digitSum(string s, int k) { // Run the loop until given string s // length is greater than k otherwise // return the string while (s.Length > k) { // Temp variable to store new string string temp = ""; for (int i = 0; i < s.Length; i++) { int sum = 0; int count = 0; // Run the loop until count is // less than k or iterator is // less than the size of string while (i < s.Length && count < k) { // Sum up the string value sum += s[i++] - '0'; // Increase the count count++; } // Add the obtained sum to the // temp variable temp += sum; i--; } // Update the value of main string s = temp; } // Return the final string return s; }// Driver Codepublic static void Main(){ string S = "11111222223"; int K = 3; // Function call String ans = digitSum(S, K); Console.Write(ans);}}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript code to implement the approach\// Function for finding the sum of Digits// of number in group of kfunction digitSum(s, k){ // Run the loop until given string s // length is greater than k otherwise // return the string while (s.length > k) { // Temp variable to store new string let temp = ""; for (let i = 0; i < s.length; i++) { let sum = 0; let count = 0; // Run the loop until count is // less than k or iterator is // less than the size of string while (i < s.length && count < k) { // Sum up the string value sum += s[i++] - '0'; // Increase the count count++; } // Add the obtained sum to the // temp variable temp += sum.toString(); i--; } // Update the value of main string s = temp; } // Return the final string return s;}// Driver codelet S = "11111222223";let K = 3;// Function calllet ans = digitSum(S, K);document.write(ans); // This code is contributed by Samim Hossain Mondal.</script> |
Output
135
Time Complexity: O(N * K)
Auxiliary Space: 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!
