Ermitteln der Ziffernsumme einer Zahl, bis die Summe eine einzelne Ziffer wird
Bei einer gegebenen ganzen Zahl n müssen wir wiederholt die Summe ihrer Ziffern ermitteln, bis das Ergebnis eine einstellige Zahl ist.
Beispiele:
Eingang: n = 1234
Ausgabe: 1
Erläuterung:
Schritt 1: 1 + 2 + 3 + 4 = 10
Schritt 2: 1 + 0 = 1Eingang: n = 5674
Ausgabe: 4
Erläuterung:
Schritt 1: 5 + 6 + 7 + 4 = 22
Schritt 2: 2 + 2 = 4
Inhaltsverzeichnis
- [Naiver Ansatz] Durch wiederholtes Hinzufügen von Ziffern
- [Erwarteter Ansatz] Verwendung einer mathematischen Formel
[Naiver Ansatz] Durch wiederholtes Hinzufügen von Ziffern
Der Ansatz konzentriert sich auf die Berechnung des digitalen Raums T einer Zahl, die das Ergebnis der wiederholten Summierung der Ziffern ist, bis ein einstelliger Wert entsteht. So funktioniert es konzeptionell:
- Summieren Sie die Ziffern : Beginnen Sie mit der Addition aller Ziffern der angegebenen Zahl.
- Überprüfen Sie das Ergebnis : Wenn die Summe eine einstellige Zahl ist (d. h. weniger als 10), stoppen Sie und geben Sie sie zurück.
- Wiederholen Sie den Vorgang : Wenn die Summe immer noch mehr als eine einzelne Ziffer beträgt, wiederholen Sie den Vorgang mit der Ziffernsumme. Das geht so lange, bis ein einstelliger Betrag erreicht ist.
// 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 ));
Ausgabe
1
Zeitkomplexität: O(log 10 n) während wir über die Ziffern der Zahl iterieren.
Hilfsraum: O(1)
[Erwarteter Ansatz] Verwendung einer mathematischen Formel
Wir wissen, dass jede Zahl im Dezimalsystem als Summe ihrer Ziffern multipliziert mit Zehnerpotenzen ausgedrückt werden kann. Zum Beispiel eine Zahl dargestellt als abcd kann wie folgt geschrieben werden:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Wir können die Ziffern trennen und dies wie folgt umschreiben:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Dies bedeutet, dass jede Zahl als Summe ihrer Ziffern plus einem Vielfachen von 9 ausgedrückt werden kann.
Nehmen wir also Modulo mit 9 auf jeder Seite
abcd % 9 = (a + b + c + d) % 9 + 0Das bedeutet, dass der Rest, wenn abcd durch 9 geteilt wird, gleich dem Rest ist, bei dem die Summe seiner Ziffern (a + b + c + d) durch 9 geteilt wird.
Wenn die Summe der Ziffern selbst aus mehr als einer Ziffer besteht, können wir diese Summe weiter als Summe ihrer Ziffern plus einem Vielfachen von 9 ausdrücken. Folglich wird bei der Anwendung von Modulo 9 das Vielfache von 9 eliminiert, bis die Summe der Ziffern zu einer einstelligen Zahl wird.
Als Ergebnis entspricht die Summe der Ziffern einer beliebigen Zahl ihrem Modulo 9. Wenn das Ergebnis der Modulo-Operation Null ist, bedeutet dies, dass das einstellige Ergebnis 9 ist.
Weitere Informationen zur Code-Implementierung finden Sie unter Digitale Wurzel (wiederholte digitale Summe) der angegebenen großen Ganzzahl
