Etsitään luvun numeroiden summaa, kunnes summasta tulee yksinumeroinen
Kun kokonaisluku n on annettu, meidän on löydettävä toistuvasti sen numeroiden summa, kunnes tuloksesta tulee yksinumeroinen luku.
Esimerkkejä:
Syöte: n = 1234
Lähtö: 1
Selitys:
Vaihe 1: 1 + 2 + 3 + 4 = 10
Vaihe 2: 1 + 0 = 1Syöte: n = 5674
Lähtö: 4
Selitys:
Vaihe 1: 5 + 6 + 7 + 4 = 22
Vaihe 2: 2 + 2 = 4
Sisällysluettelo
- [Naiivi lähestymistapa] Lisäämällä toistuvasti numeroita
- [Odotettu lähestymistapa] Matemaattisen kaavan käyttäminen
[Naiivi lähestymistapa] Lisäämällä toistuvasti numeroita
Lähestymistapa keskittyy digitaalisen roon laskemiseen t luvusta, joka on tulosta summaamalla numerot toistuvasti, kunnes saadaan yksinumeroinen arvo. Näin se toimii käsitteellisesti:
- Summaa numerot : Aloita lisäämällä kaikki annetun numeron numerot.
- Tarkista tulos : Jos summa on yksinumeroinen luku (eli alle 10), lopeta ja palauta se.
- Toista prosessi : Jos summa on edelleen enemmän kuin yksi numero, toista prosessi numeroiden summalla. Tämä jatkuu, kunnes saavutetaan yksinumeroinen summa.
// 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 ));
Lähtö
1
Aika monimutkaisuus: O(log 10 n) kun iteroimme luvun numeroiden yli.
Aputila: O(1)
[Odotettu lähestymistapa] Matemaattisen kaavan käyttäminen
Tiedämme, että jokainen luku desimaalijärjestelmässä voidaan ilmaista sen numeroiden summana kerrottuna 10:n potenssilla. Esimerkiksi luku, joka esitetään abcd voidaan kirjoittaa seuraavasti:
abcd = a*10^3 + b*10^2 + c*10^1 + d*10^0
Voimme erottaa numerot ja kirjoittaa tämän uudelleen seuraavasti:
abcd = a + b + c + d + (a*999 + b*99 + c*9)
abcd = a + b + c + d + 9*(a*111 + b*11 + c)
Tämä tarkoittaa, että mikä tahansa luku voidaan ilmaista sen numeroiden summana plus 9:n kerrannainen.
Joten jos otamme modulon 9:n kummallakin puolella
abcd % 9 = (a + b + c + d) % 9 + 0Tämä tarkoittaa, että jäännös, kun abcd jaetaan 9:llä, on yhtä suuri kuin jäännös, jossa sen numeroiden summa (a + b + c + d) jaetaan 9:llä.
Jos itse numeroiden summa koostuu useammasta kuin yhdestä numerosta, voimme edelleen ilmaista tämän summan sen numeroiden summana plus 9:n kerrannainen. Näin ollen modulo 9:n ottaminen eliminoi luvun 9 kerrannaisen, kunnes numeroiden summasta tulee yksinumeroinen luku.
Tämän seurauksena minkä tahansa luvun numeroiden summa on yhtä suuri kuin sen modulo 9. Jos modulo-operaation tulos on nolla, yksinumeroinen tulos on 9.
Lisätietoja koodin käyttöönotosta on kohdassa Annetun suuren kokonaisluvun digitaalinen juuri (toistuva digitaalinen summa).
