Знаходження суми цифр числа до тих пір, поки сума не стане одноцифровою
Дано ціле число n, нам потрібно кілька разів знаходити суму його цифр, поки результат не стане одноцифровим числом.
приклади:
введення: n = 1234
Вихід: 1
Пояснення:
Крок 1: 1 + 2 + 3 + 4 = 10
Крок 2: 1 + 0 = 1введення: n = 5674
Вихід: 4
Пояснення:
Крок 1: 5 + 6 + 7 + 4 = 22
Крок 2: 2 + 2 = 4
Зміст
[Наївний підхід] Повторним додаванням цифр
Підхід зосереджений на розрахунку цифрового ру t числа, яке є результатом багаторазового підсумовування цифр, поки не буде отримано одноцифрове значення. Ось як це працює концептуально:
- Підсумуйте цифри : Почніть із додавання всіх цифр даного числа.
- Перевірте результат : Якщо сума є однозначним числом (тобто менше 10), зупиніться та поверніть її.
- Повторіть процес : якщо сума все ще перевищує одну цифру, повторіть процес із сумою цифр. Це триває до тих пір, поки не буде досягнуто однозначної суми.
// C++ program to find the digit sum by // repetitively Adding its digits #include using namespace std ; int singleDigit ( int n ) { int sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n == 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n /= 10 ; } return sum ; } int main () { int n = 1234 ; cout < < singleDigit ( n ); return 0 ; }
C // C program to find the digit sum by // repetitively Adding its digits #include int singleDigit ( int n ) { int sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n == 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n /= 10 ; } return sum ; } int main () { int n = 1234 ; printf ( '%d' singleDigit ( n )); return 0 ; }
Java // Java program to find the digit sum by // repetitively Adding its digits class GfG { static int singleDigit ( int n ) { int sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n == 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n /= 10 ; } return sum ; } public static void main ( String [] args ) { int n = 1234 ; System . out . println ( singleDigit ( n )); } }
Python # Python program to find the digit sum by # repetitively Adding its digits def singleDigit ( n ): sum = 0 # Repetitively calculate sum until # it becomes single digit while n > 0 or sum > 9 : # If n becomes 0 reset it to sum # and start a new iteration if n == 0 : n = sum sum = 0 sum += n % 10 n //= 10 return sum if __name__ == '__main__' : n = 1234 print ( singleDigit ( n ))
C# // C# program to find the digit sum by // repetitively Adding its digits using System ; class GfG { static int singleDigit ( int n ) { int sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n == 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n /= 10 ; } return sum ; } static void Main () { int n = 1234 ; Console . WriteLine ( singleDigit ( n )); } }
JavaScript // JavaScript program to find the digit sum by // repetitively Adding its digits function singleDigit ( n ) { let sum = 0 ; // Repetitively calculate sum until // it becomes single digit while ( n > 0 || sum > 9 ) { // If n becomes 0 reset it to sum // and start a new iteration. if ( n === 0 ) { n = sum ; sum = 0 ; } sum += n % 10 ; n = Math . floor ( n / 10 ); } return sum ; } // Driver Code const n = 1234 ; console . log ( singleDigit ( n ));
Вихід
1
Часова складність: O(log 10 n) оскільки ми повторюємо цифри числа.
Допоміжний простір: О(1)
[Очікуваний підхід] Використання математичної формули
Ми знаємо, що кожне число в десятковій системі можна виразити як суму його цифр, помножену на степені числа 10. Наприклад, число представлене як abcd можна записати наступним чином:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Ми можемо розділити цифри і переписати це так:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Це означає, що будь-яке число можна виразити як суму його цифр плюс кратне 9.
Отже, якщо взяти за модулем 9 з кожного боку
abcd % 9 = (a + b + c + d) % 9 + 0Це означає, що залишок від ділення abcd на 9 дорівнює залишку, де сума його цифр (a + b + c + d) поділена на 9.
Якщо сама сума цифр складається з більш ніж однієї цифри, ми можемо далі виразити цю суму як суму її цифр плюс кратне 9. Отже, беручи за модулем 9, виключите кратне 9, доки сума цифр не стане одноцифровим числом.
У результаті сума цифр будь-якого числа дорівнюватиме його по модулю 9. Якщо результат операції по модулю дорівнює нулю, це означає, що однозначний результат дорівнює 9.
Щоб дізнатися про впровадження коду, див Цифровий корінь (повторювана цифрова сума) заданого великого цілого числа
