समस्या
किसी धनात्मक पूर्णांक से शुरू कीजिए और उसे उसके अंकों के वर्गों के योग से बदल दीजिए। यही करते रहिए। अगर आख़िरकार संख्या 1 बन जाती है, तो शुरुआती संख्या हैप्पी (happy) है। वरना यह प्रक्रिया एक ऐसे चक्र में फँस जाती है जिसमें 1 कभी नहीं आता, और तब वह संख्या अनहैप्पी कहलाती है। उदाहरण के लिए, 7 → 49 → 97 → 130 → 10 → 1, इसलिए 7 हैप्पी है।
happy_number(n) लिखिए।
आपको यह पहचानने का कोई तरीक़ा चाहिए कि अनुक्रम दोहराने लगा है, ताकि अनहैप्पी संख्याओं पर भी लूप रुक जाए।
इनपुट
n: शुरुआती संख्या।
आउटपुट
अगर प्रक्रिया 1 तक पहुँचती है तो true लौटाइए, वरना false। संख्या 1 ख़ुद हैप्पी है।
सीमाएँ
1 ≤ n ≤ 10^9
उदाहरण
इनपुट:
n = 19
अपेक्षित आउटपुट:
expected = True
इनपुट:
long long n = 19;
अपेक्षित आउटपुट:
bool expected = true;
इनपुट:
long n = 19;
अपेक्षित आउटपुट:
bool expected = true;
व्याख्या
1² + 9² = 82, फिर 8² + 2² = 68, फिर 6² + 8² = 100, फिर 1² + 0² + 0² = 1, इसलिए 19 हैप्पी है: true।
इनपुट:
n = 4
अपेक्षित आउटपुट:
expected = False
इनपुट:
long long n = 4;
अपेक्षित आउटपुट:
bool expected = false;
इनपुट:
long n = 4;
अपेक्षित आउटपुट:
bool expected = false;
व्याख्या
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4, यानी अनुक्रम 1 तक पहुँचे बिना दोहराने लगता है, इसलिए उत्तर false है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
एक सहायक फ़ंक्शन लिखिए जो किसी संख्या को उसके अंकों के वर्गों के योग में बदल दे।
संकेत 2
अनहैप्पी संख्या कोई ऐसा मान दोहराती है जो पहले आ चुका है; देखे गए मान याद रखिए।
संकेत 3
अनुक्रम बहुत जल्दी कुछ सौ से नीचे आ जाता है, इसलिए set छोटा ही रहता है।
अपेक्षित जटिलता
हर संख्या के लिए O(log n) कदम, two pointers के साथ अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।