Određivanje zbroja znamenki broja dok zbroj ne postane jednoznamenkasti
Za cijeli broj n trebamo iznova pronaći zbroj njegovih znamenki sve dok rezultat ne postane jednoznamenkasti broj.
Primjeri:
Ulazni: n = 1234
Izlaz: 1
Obrazloženje:
1. korak: 1 + 2 + 3 + 4 = 10
2. korak: 1 + 0 = 1Ulazni: n = 5674
Izlaz: 4
Obrazloženje:
1. korak: 5 + 6 + 7 + 4 = 22
2. korak: 2 + 2 = 4
Sadržaj
[Naivni pristup] Uzastopnim zbrajanjem znamenki
Pristup je usmjeren na izračun digitalnog rooa t broja koji je rezultat uzastopnog zbrajanja znamenki dok se ne dobije jednoznamenkasta vrijednost. Evo kako to konceptualno funkcionira:
- Zbrojite znamenke : Započnite dodavanjem svih znamenki zadanog broja.
- Provjerite rezultat : Ako je zbroj jednoznamenkasti broj (tj. manji od 10) zaustavite se i vratite ga.
- Ponovite postupak : Ako je zbroj još uvijek veći od jedne znamenke, ponovite postupak sa zbrojem znamenki. To se nastavlja sve dok se ne postigne jednoznamenkasti zbroj.
// 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 ));
Izlaz
1
Vremenska složenost: O(log 10 n) dok ponavljamo znamenke broja.
Pomoćni prostor: O(1)
[Očekivani pristup] Korištenje matematičke formule
Znamo da se svaki broj u decimalnom sustavu može izraziti kao zbroj njegovih znamenki pomnoženih potencijama broja 10. Na primjer, broj predstavljen kao abcd može se napisati na sljedeći način:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Možemo odvojiti znamenke i prepisati ovo kao:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
To implicira da se bilo koji broj može izraziti kao zbroj njegovih znamenki plus višekratnik broja 9.
Dakle, ako uzmemo modulo s 9 na svakoj strani
abcd % 9 = (a + b + c + d) % 9 + 0To znači da je ostatak kada se abcd podijeli s 9 jednak ostatku gdje je zbroj njegovih znamenki (a + b + c + d) podijeljen s 9.
Ako se sam zbroj znamenki sastoji od više od jedne znamenke, možemo dalje izraziti ovaj zbroj kao zbroj njegovih znamenki plus višekratnik od 9. Posljedično uzimanje modula 9 će eliminirati višekratnik od 9 sve dok zbroj znamenki ne postane jednoznamenkasti broj.
Kao rezultat toga, zbroj znamenki bilo kojeg broja bit će jednak modulu 9. Ako je rezultat modulo operacije nula, to znači da je jednoznamenkasti rezultat 9.
Za informacije o implementaciji koda Pogledajte Digitalni korijen (ponovljeni digitalni zbroj) zadanog velikog cijelog broja
