समस्या
n के उचित भाजक (proper divisors) उसके वे धनात्मक भाजक हैं जो खुद n नहीं हैं। 12 के लिए ये 1, 2, 3, 4 और 6 हैं। इनका योग (जिसे कभी-कभी aliquot sum कहते हैं) बताता है कि संख्या पूर्ण (perfect), प्रचुर (abundant) या न्यून (deficient) है। भाजक जोड़ों में आते हैं, d और n / d, इसलिए d के मान n के वर्गमूल तक ही आज़माने की ज़रूरत है।
sum_of_proper_divisors(n) लिखिए।
इनपुट
n: एक धनात्मक पूर्णांक।
आउटपुट
n के उन सभी धनात्मक भाजकों का योग लौटाइए जो n से छोटे हैं। n = 1 के लिए ऐसा कोई भाजक नहीं है, इसलिए 0 लौटाइए।
सीमाएँ
1 ≤ n ≤ 10^12
उदाहरण
इनपुट:
n = 12
अपेक्षित आउटपुट:
expected = 16
इनपुट:
long long n = 12;
अपेक्षित आउटपुट:
long long expected = 16;
इनपुट:
long n = 12;
अपेक्षित आउटपुट:
long expected = 16;
व्याख्या
1 + 2 + 3 + 4 + 6 = 16।
इनपुट:
n = 28
अपेक्षित आउटपुट:
expected = 28
इनपुट:
long long n = 28;
अपेक्षित आउटपुट:
long long expected = 28;
इनपुट:
long n = 28;
अपेक्षित आउटपुट:
long expected = 28;
व्याख्या
1 + 2 + 4 + 7 + 14 = 28, इसलिए 28 एक पूर्ण संख्या है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
अगर d, n को विभाजित करता है, तो n / d भी n को विभाजित करता है।
संकेत 2
d को सिर्फ़ n के वर्गमूल तक आज़माइए, और हर जोड़े के दोनों सदस्य जोड़िए।
संकेत 3
खुद n को छोड़ दीजिए, और अगर n पूर्ण वर्ग है तो वर्गमूल को सिर्फ़ एक बार जोड़िए।
अपेक्षित जटिलता
समय O(sqrt n), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।