Trovare la somma delle cifre di un numero finché la somma non diventa una cifra singola
Dato un numero intero n dobbiamo trovare ripetutamente la somma delle sue cifre finché il risultato non diventa un numero a una cifra.
Esempi:
Ingresso: n = 1234
Produzione: 1
Spiegazione:
Passaggio 1: 1 + 2 + 3 + 4 = 10
Passaggio 2: 1 + 0 = 1Ingresso: n = 5674
Produzione: 4
Spiegazione:
Passaggio 1: 5 + 6 + 7 + 4 = 22
Passaggio 2: 2 + 2 = 4
Sommario
- [Approccio ingenuo] Aggiungendo ripetutamente cifre
- [Approccio previsto] Utilizzo di formule matematiche
[Approccio ingenuo] Aggiungendo ripetutamente cifre
L'approccio è focalizzato sul calcolo del roo digitale T di un numero che è il risultato della somma ripetuta delle cifre fino ad ottenere un valore a una cifra. Ecco come funziona concettualmente:
- Somma le cifre : Inizia aggiungendo tutte le cifre del numero indicato.
- Controlla il risultato : Se la somma è un numero a una cifra (cioè inferiore a 10) fermati e restituiscilo.
- Ripeti il processo : Se la somma è ancora superiore a una singola cifra, ripetere il processo con la somma delle cifre. Questo continua finché non viene raggiunta una somma a una cifra.
// 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 ));
Produzione
1
Complessità temporale: O(log 10 n) mentre stiamo iterando sulle cifre del numero.
Spazio ausiliario: O(1)
[Approccio previsto] Utilizzo di formule matematiche
Sappiamo che ogni numero nel sistema decimale può essere espresso come la somma delle sue cifre moltiplicata per potenze di 10. Ad esempio un numero rappresentato come abcd può essere scritto come segue:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Possiamo separare le cifre e riscriverlo come:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Ciò implica che qualsiasi numero può essere espresso come la somma delle sue cifre più un multiplo di 9.
Quindi se prendiamo il modulo con 9 su ciascun lato
abcd % 9 = (a + b + c + d) % 9 + 0Ciò significa che il resto della divisione di abcd per 9 è uguale al resto della divisione della somma delle sue cifre (a + b + c + d) per 9.
Se la somma delle cifre stessa è costituita da più di una cifra, possiamo esprimere ulteriormente questa somma come la somma delle sue cifre più un multiplo di 9. Di conseguenza, prendendo il modulo 9 si eliminerà il multiplo di 9 finché la somma delle cifre non diventerà un numero a cifra singola.
Di conseguenza la somma delle cifre di qualsiasi numero sarà uguale al suo modulo 9. Se il risultato dell'operazione modulo è zero indica che il risultato a una cifra è 9.
Per conoscere l'implementazione del codice Fare riferimento Radice digitale (somma digitale ripetuta) del numero intero grande dato
