Znajdowanie sumy cyfr liczby, aż suma stanie się jedną cyfrą
Biorąc pod uwagę liczbę całkowitą n, musimy wielokrotnie znajdować sumę jej cyfr, aż wynik stanie się liczbą jednocyfrową.
Przykłady:
Wejście: n = 1234
Wyjście: 1
Wyjaśnienie:
Krok 1: 1 + 2 + 3 + 4 = 10
Krok 2: 1 + 0 = 1Wejście: n = 5674
Wyjście: 4
Wyjaśnienie:
Krok 1: 5 + 6 + 7 + 4 = 22
Krok 2: 2 + 2 = 4
Spis treści
- [Podejście naiwne] Przez wielokrotne dodawanie cyfr
- [Oczekiwane podejście] Przy użyciu wzoru matematycznego
[Podejście naiwne] Przez wielokrotne dodawanie cyfr
Podejście koncentruje się na obliczaniu cyfrowego roo T liczby powstałej w wyniku wielokrotnego sumowania cyfr, aż do uzyskania wartości jednocyfrowej. Oto jak to działa koncepcyjnie:
- Zsumuj cyfry : Zacznij od dodania wszystkich cyfr podanej liczby.
- Sprawdź wynik : Jeśli suma jest liczbą jednocyfrową (tj. mniejszą niż 10), zatrzymaj się i zwróć ją.
- Powtórz proces : Jeśli suma nadal jest większa niż jedna cyfra, powtórz proces z sumą cyfr. Trwa to aż do osiągnięcia jednocyfrowej sumy.
// 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 ));
Wyjście
1
Złożoność czasowa: O(log 10 n) podczas iteracji po cyfrach liczby.
Przestrzeń pomocnicza: O(1)
[Oczekiwane podejście] Przy użyciu wzoru matematycznego
Wiemy, że każdą liczbę w systemie dziesiętnym można wyrazić jako sumę jej cyfr pomnożoną przez potęgę 10. Na przykład liczba reprezentowana jako abcd można zapisać w następujący sposób:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Możemy oddzielić cyfry i zapisać to jako:
abcd = a + b + do + d + (a*999 + b*99 + c*9)
abcd = a + b + do + d + 9*(a*111 + b*11 + c)
Oznacza to, że dowolną liczbę można wyrazić jako sumę jej cyfr plus wielokrotność 9.
Więc jeśli weźmiemy modulo z 9 po każdej stronie
abcd % 9 = (a + b + do + d) % 9 + 0Oznacza to, że reszta z dzielenia abcd przez 9 jest równa reszcie z sumy jego cyfr (a + b + c + d) dzielonej przez 9.
Jeśli suma samych cyfr składa się z więcej niż jednej cyfry, możemy dalej wyrazić tę sumę jako sumę jej cyfr plus wielokrotność 9. W rezultacie przyjęcie modulo 9 wyeliminuje wielokrotność 9, aż suma cyfr stanie się liczbą jednocyfrową.
W rezultacie suma cyfr dowolnej liczby będzie równa jej modulo 9. Jeśli wynik operacji modulo wynosi zero, oznacza to, że wynik jednocyfrowy wynosi 9.
Aby dowiedzieć się o implementacji kodu, zobacz Pierwiastek cyfrowy (powtarzana suma cyfrowa) danej dużej liczby całkowitej
