समस्या
n के अंकों का योग करें। यदि परिणाम एक से अधिक अंकों का है, तो उसके अंकों का फिर से योग करें। यह प्रक्रिया तब तक दोहराएँ जब तक केवल एक अंक न बच जाए।
digital_root(n) को लागू करें।
इनपुट
n: एक धनात्मक पूर्णांक।
आउटपुट
अंतिम एकल अंक लौटाएँ।
सीमाएँ
1 ≤ n ≤ 10¹⁸
उदाहरण
उदाहरण 1
इनपुट:
n = 999
अपेक्षित आउटपुट:
expected = 9इनपुट:
long long n = 999;
अपेक्षित आउटपुट:
long long expected = 9;इनपुट:
long n = 999;
अपेक्षित आउटपुट:
long expected = 9;व्याख्या
9 + 9 + 9 = 27, फिर 2 + 7 = 9।
उदाहरण 2
इनपुट:
n = 38
अपेक्षित आउटपुट:
expected = 2इनपुट:
long long n = 38;
अपेक्षित आउटपुट:
long long expected = 2;इनपुट:
long n = 38;
अपेक्षित आउटपुट:
long expected = 2;व्याख्या
3 + 8 = 11, फिर 1 + 1 = 2।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Digits को बार-बार जोड़ने पर आखिर में number एक digit तक सिमट जाता है।
संकेत 2
Value 10 से छोटी होने तक repeated summing process simulate कर सकते हैं।
संकेत 3
बहुत बड़े inputs के लिए सावधान रहें; process simple है, लेकिन digits पर repeated passes ही मुख्य काम हैं।
अपेक्षित जटिलता
समय O(d log n), अतिरिक्त स्थान O(1)