De som van de cijfers van een getal vinden totdat de som één cijfer wordt
Gegeven een geheel getal n moeten we herhaaldelijk de som van de cijfers ervan vinden totdat het resultaat een getal van één cijfer wordt.
Voorbeelden:
Invoer: n = 1234
Uitgang: 1
Uitleg:
Stap 1: 1 + 2 + 3 + 4 = 10
Stap 2: 1 + 0 = 1Invoer: n = 5674
Uitgang: 4
Uitleg:
Stap 1: 5 + 6 + 7 + 4 = 22
Stap 2: 2 + 2 = 4
Inhoudsopgave
- [Naïeve aanpak] Door herhaaldelijk cijfers toe te voegen
- [Verwachte aanpak] Wiskundige formule gebruiken
[Naïeve aanpak] Door herhaaldelijk cijfers toe te voegen
De aanpak is gericht op het berekenen van de digitale ro T van een getal dat het resultaat is van het herhaaldelijk optellen van de cijfers totdat een waarde van één cijfer wordt verkregen. Conceptueel werkt het als volgt:
- Tel de cijfers bij elkaar op : Begin met het optellen van alle cijfers van het opgegeven getal.
- Controleer het resultaat : Als de som een getal van één cijfer is (d.w.z. minder dan 10), stop dan en geef het terug.
- Herhaal het proces : Als de som nog steeds meer dan één cijfer bedraagt, herhaalt u het proces met de som van de cijfers. Dit gaat door totdat een som van één cijfer is bereikt.
// 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 ));
Uitvoer
1
Tijdcomplexiteit: O(logboek 10 n) terwijl we de cijfers van het getal herhalen.
Hulpruimte: O(1)
[Verwachte aanpak] Wiskundige formule gebruiken
We weten dat elk getal in het decimale systeem kan worden uitgedrukt als de som van de cijfers vermenigvuldigd met machten van 10. Een getal dat bijvoorbeeld wordt weergegeven als abcd kan als volgt worden geschreven:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
We kunnen de cijfers scheiden en dit herschrijven als:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Dit houdt in dat elk getal kan worden uitgedrukt als de som van de cijfers plus een veelvoud van 9.
Dus als we modulo nemen met 9 aan elke kant
abcd % 9 = (a + b + c + d) % 9 + 0Dit betekent dat de rest wanneer abcd wordt gedeeld door 9 gelijk is aan de rest waarbij de som van de cijfers (a + b + c + d) wordt gedeeld door 9.
Als de som van de cijfers zelf uit meer dan één cijfer bestaat, kunnen we deze som verder uitdrukken als de som van de cijfers plus een veelvoud van 9. Bijgevolg zal het nemen van modulo 9 het veelvoud van 9 elimineren totdat de som van de cijfers een getal met één cijfer wordt.
Als gevolg hiervan zal de som van de cijfers van elk getal gelijk zijn aan modulo 9. Als het resultaat van de modulo-bewerking nul is, geeft dit aan dat het resultaat met één cijfer 9 is.
Voor meer informatie over code-implementatie Raadpleeg Digitale Wortel (herhaalde digitale som) van het gegeven grote gehele getal
