C++ में दिए गए समीकरण के हल की संख्या खोजना

समस्या विवरण

इस समस्या में, हमें तीन पूर्णांक मान A, B, C दिए गए हैं। हमारा कार्य दिए गए समीकरण के हल की संख्या खोजना है।

समीकरण

X = B × Sm(X)^A + C

जहां Sm(X), X के अंकों का योग है।

हमें X के उन सभी मानों को गिनने की आवश्यकता है जो उपरोक्त समीकरण को संतुष्ट करते हैं जहां X 1 से 10⁹ के बीच कोई भी संख्या हो सकती है।

उदाहरण

इनपुट

A = 3, B = 6, C = 4

आउटपुट

3

हल का दृष्टिकोण

समस्या को हल करने का एक समाधान X के मानों की संख्या गिनना है। इसके लिए, अंकों का योग एक महत्वपूर्ण भूमिका निभाता है। अधिकतम अंक योग 81 है (अधिकतम मान 999,999,999 के लिए)। और प्रत्येक अंक योग मान के लिए, हम समीकरण का एक हल प्राप्त कर सकते हैं।

हम 1 से 81 तक के प्रत्येक अंक योग मान के लिए मानों को गिनेंगे जो समीकरण को संतुष्ट करते हैं।

एल्गोरिदम

1. digitSum = 1 से 81 तक लूप करें
2. प्रत्येक के लिए, solVal = B × (digitSum)^A + C की गणना करें
3. यदि solVal < 10⁹ और solVal के अंकों का योग digitSum के बराबर है, तो गिनती बढ़ाएं
4. कुल गिनती वापस करें

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

int countSolutions(int a, int b, int c) {
    int solutionCount = 0;
    for (int digSum = 1; digSum <= 81; digSum++) {
        long long solVal = 1LL * b * pow(digSum, a) + c;
        if (solVal >= 1e9) continue;
        
        int temp = solVal;
        int sum = 0;
        while (temp) {
            sum += temp % 10;
            temp /= 10;
        }
        
        if (sum == digSum)
            solutionCount++;
    }
    return solutionCount;
}

int main() {
    int a = 3, b = 6, c = 4;
    cout << "समीकरण के हल की संख्या है " << countSolutions(a, b, c);
    return 0;
}

आउटपुट

समीकरण के हल की संख्या है 3

जटिलता विश्लेषण

• समय जटिलता: O(81 × log₁₀(X)) ≈ O(1) - स्थिर 81 पुनरावृत्तियाँ
• स्पेस जटिलता: O(1)

मुख्य अंतर्दृष्टि

चूंकि X ≤ 10⁹, अधिकतम अंक योग 9×9 = 81 है। हम केवल 81 संभावित अंक योगों की जांच करते हैं, जिससे समाधान बहुत कुशल होता है।