Găsirea sumei cifrelor unui număr până când suma devine o singură cifră
Având în vedere un număr întreg n, trebuie să găsim în mod repetat suma cifrelor sale până când rezultatul devine un număr cu o singură cifră.
Exemple:
Intrare: n = 1234
Ieșire: 1
Explicaţie:
Pasul 1: 1 + 2 + 3 + 4 = 10
Pasul 2: 1 + 0 = 1Intrare: n = 5674
Ieșire: 4
Explicaţie:
Pasul 1: 5 + 6 + 7 + 4 = 22
Pasul 2: 2 + 2 = 4
Cuprins
[Abordare naivă] Adăugând în mod repetat cifre
Abordarea se concentrează pe calcularea acoperișului digital t a unui număr care este rezultatul însumării cifrelor în mod repetat până la obținerea unei valori cu o singură cifră. Iată cum funcționează conceptual:
- Însumați cifrele : Începeți prin a adăuga toate cifrele numărului dat.
- Verificați rezultatul : Dacă suma este un număr dintr-o singură cifră (adică mai puțin de 10), opriți-l și returnați-l.
- Repetați procesul : Dacă suma este mai mare decât o singură cifră, repetați procesul cu suma cifrelor. Aceasta continuă până când se ajunge la o sumă cu o singură cifră.
// 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 ));
Ieșire
1
Complexitatea timpului: O (log 10 n) pe măsură ce iterăm peste cifrele numărului.
Spațiu auxiliar: O(1)
[Abordare așteptată] Folosind formula matematică
Știm că fiecare număr din sistemul zecimal poate fi exprimat ca o sumă a cifrelor sale înmulțite cu puterile lui 10. De exemplu, un număr reprezentat ca abcd se poate scrie astfel:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Putem separa cifrele și rescrie asta ca:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Aceasta implică faptul că orice număr poate fi exprimat ca suma cifrelor sale plus un multiplu de 9.
Deci dacă luăm modulo cu 9 pe fiecare parte
abcd % 9 = (a + b + c + d) % 9 + 0Aceasta înseamnă că restul când abcd este împărțit la 9 este egal cu restul în care suma cifrelor sale (a + b + c + d) este împărțită la 9.
Dacă suma cifrelor în sine constă din mai mult de o cifră, putem exprima în continuare această sumă ca suma cifrelor sale plus un multiplu de 9. Prin urmare, luarea modulo 9 va elimina multiplu de 9 până când suma cifrelor devine un număr cu o singură cifră.
Ca rezultat, suma cifrelor oricărui număr va fi egală cu modulo 9. Dacă rezultatul operației modulo este zero, înseamnă că rezultatul dintr-o singură cifră este 9.
Pentru a afla despre implementarea codului Consultați Rădăcină digitală (suma digitală repetată) a întregului mare dat
