Сократите строку, выполнив повторяющуюся сумму цифр в группе K

Опубликовано: 19 Сентября, 2022

Дана строка S длины N , состоящая из цифр и целого числа K. Сократите строку, выполнив следующую операцию, пока длина строки не станет больше, чем K :

  1. Разделите строку на последовательные группы размером K так, чтобы первые K символов находились в первой группе, следующие K символов — во второй группе и так далее. Обратите внимание, что размер последней группы может быть меньше, чем K .
  2. Объедините сумму цифр последовательных групп вместе, чтобы сформировать новую строку. Если длина строки больше K , повторите шаги.

Примеры:

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.

Подход: это простая проблема, основанная на реализации. Решение выглядит следующим образом:

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.

Для реализации идеи выполните следующие шаги:

  • Запустите цикл, пока заданная строка S не будет иметь длину больше, чем K .
    • Возьмите одну новую строку (скажем, temp ) для хранения новой строки.
    • Перейдите строку S от i = 0 до i = s.size() – 1.
      • Определите переменную (скажем, sum = 0 ) для хранения суммы.
      • Итерируйте группу из K символов и сохраняйте сумму цифр из K цифр.
      • Добавьте сумму во временную строку.
    • Сделайте S = temp , т.е. таким же, как вновь сформированная строка.
  • Верните S в качестве последней строки.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * K)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ