Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Scale back string by performing repeated digit sum in group of Okay

[ad_1]

Given a string S of size N consisting of digits and an integer Okay, Scale back the string by performing the next operation until the size of the string is larger than Okay:

  1. Divide the string into consecutive teams of measurement Okay such that the primary Okay characters are within the first group, the following Okay characters are within the second group, and so forth. Observe that the scale of the final group will be smaller than Okay.
  2. Merge the digit sum of consecutive teams collectively to type a brand new string. If the size of the string is larger than Okay, repeat the steps.

Examples:

Enter: S = “11111222223”, Okay = 3
Output: “135”
Clarification: 
For the primary spherical, divide S into teams of measurement 3: “111”, “112”, “222”, and “23”. 
Then calculate the digit sum of every group: 
1 + 1 + 1 = 3, 1 + 1 + 2 = 4,  2 + 2 + 2 = 6, and a couple of + 3 = 5. 
So, string turns into “3” + “4” + “6” + “5” = “3465”. 
For the second spherical, divide s into “346” and “5”. 
Then calculate the digit sum of every group: 3 + 4 + 6 = 13, 5 = 5. 
So, string turns into “13” + “5” = “135”. 
After second spherical. Now, size of S <= Okay, so return “135” as the reply.

Enter: S = “1123”, Okay = 2
Output: “25”
Clarification: For the primary spherical, divide S into teams of measurement 2: “11”, “23”. ​
Then we calculate the digit sum of every group: 1 + 1 = 2 and a couple of + 3 = 5. 
So, String turns into “2” + “5” = “25” after the primary spherical. 
Now, size of S <= Okay, so return “25” as the reply.

 

Strategy: This can be a easy implementation primarily based downside. The answer is as follows:

Iterate S till its measurement is larger than Okay. In each iteration, divide the string in consecutive Okay sized teams, get their sum and add them to type the brand new string.

Observe the under steps to implement the concept:

  • Run a loop till the given string S has size larger than Okay.
    • Take one new string (say temp) to retailer the brand new string. 
    • Traverse string S from i = 0 to i = s.measurement() – 1.
      • Outline a variable (say sum = 0) to retailer the sum. 
      • Iterate in a gaggle of Okay characters and maintain storing the digit sum of Okay digits.
      • Append the sum in temp string.
    • Make S = temp, i.e. similar because the newly fashioned string.
  • Return S as the ultimate string.

Beneath is the implementation for the above strategy:

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

string digitSum(string s, int okay)

{

    

    

    

    whereas (s.measurement() > okay) {

  

        

        string temp = "";

        for (int i = 0; i < s.measurement(); i++) {

            int sum = 0;

            int rely = 0;

  

            

            

            

            whereas (i < s.measurement() && rely < okay) {

  

                

                sum += s[i++] - '0';

  

                

                rely++;

            }

  

            

            

            temp += to_string(sum);

            i--;

        }

  

        

        s = temp;

    }

  

    

    return s;

}

  

int predominant()

{

    string S = "11111222223";

    int Okay = 3;

  

    

    string ans = digitSum(S, Okay);

    cout << ans << endl;

    return 0;

}

Time Complexity: O(N * Okay)
Auxiliary House: O(1)

[ad_2]

Leave a Reply