C++ में N अंक जोड़ें ताकि प्रत्येक जोड़ के बाद B से विभाज्य हो

समस्या विवरण

दिए गए a, b और n। हमें निम्नलिखित शर्तों पर विचार करके इष्टतम समाधान ढूंढना है: n अंकों को a में जोड़ें ताकि प्रत्येक पुनरावृत्ति के बाद यह b से विभाज्य हो।

शर्तें:

1. a में एक अंक जोड़ें ताकि जोड़ने के बाद, a, b से विभाज्य हो
2. n पुनरावृत्तियों के बाद a का सबसे छोटा संभव मान प्रिंट करें
3. यदि ऑपरेशन विफल हो तो "fail" प्रिंट करें

हर अंक जोड़ने के बाद विभाज्यता जांचें।

उदाहरण

Input: a=5, b=4, n=4
Output: 52000

व्याख्या

पहला अंक 0 से 9 तक जोड़ा जाना है। यदि कोई अंक a को b से विभाज्य नहीं बनाता तो उत्तर -1 है। अन्यथा, पहली शर्त को पूरा करने वाला अंक जोड़ें और फिर 0 को (n-1) बार जोड़ें क्योंकि यदि a, b से विभाज्य है तो a×10, a×100, ... भी b से विभाज्य होंगे।

एल्गोरिदम

addNDigits(a, b, n):
    original = a
    for digit from 0 to 9:
        temp = a * 10 + digit
        if temp % b == 0:
            a = temp
            break
    if a == original:
        return -1  // कोई वैध अंक नहीं मिला
    for i = 1 to n-1:
        a = a * 10  // शेष अंकों के लिए 0 जोड़ें
    return a

उदाहरण

#include <iostream>
using namespace std;

int addNDigits(int a, int b, int n) {
    int original = a;

    // पहला अंक ढूंढें जो विभाज्य बनाए
    for (int i = 0; i <= 9; i++) {
        int temp = a * 10 + i;
        if (temp % b == 0) {
            a = temp;
            break;
        }
    }

    // यदि कोई अंक नहीं मिला
    if (original == a) {
        return -1;
    }

    // शेष (n-1) अंकों के लिए 0 जोड़ें
    for (int j = 0; j < n - 1; j++) {
        a *= 10;
    }

    return a;
}

int main() {
    int a = 5, b = 4, n = 4;
    int result = addNDigits(a, b, n);

    if (result == -1) {
        cout << "fail";
    } else {
        cout << result;
    }
    return 0;
}

आउटपुट

52000

अधिक उदाहरण

समय जटिलता

O(10 + n) = O(n) - स्थिर समय में पहला अंक ढूंढना + n-1 गुणा