C++ में योग N के बराबर करने के लिए न्यूनतम घात पदों की संख्या

समस्या कथन

दो धनात्मक पूर्णांक N और X दिए गए हैं। कार्य N को X की घातों के योग (X⁰ + X¹ + ... + Xⁿ) के रूप में व्यक्त करना है ताकि X की घातों की संख्या न्यूनतम हो।

N बनाने के लिए उपयोग की गई N की न्यूनतम घातों की संख्या प्रिंट करें।

यदि N=15 और X=3, तो हमें 3 की 3 घातों की आवश्यकता है: 15 = 3² + 3¹ + 3¹

एल्गोरिदम

अंतिम परिणाम की गणना के लिए नीचे दिए गए सूत्र का उपयोग करें:

1. यदि x = 1, तो उत्तर केवल n होगा (n = 1 + 1 + ... n बार)
2. किसी भी संख्या n को इस प्रकार व्यक्त किया जा सकता है: n = x * a + b जहां 0 ≤ b ≤ x-1।
   चूंकि b 0 से x-1 के बीच है, तो b को x⁰ के योग के रूप में b बार व्यक्त किया जाना चाहिए।

C++ उदाहरण

#include <iostream>
using namespace std;

int minNumOfPower(int n, int x) {
    if (x == 1) return n;
    int result = 0;
    while (n > 0) {
        result += (n % x);
        n = n / x;
    }
    return result;
}

int main() {
    int n = 15, x = 3;
    cout << "Minimum number of powers = " << minNumOfPower(15, 3) << endl;
    return 0;
}

आउटपुट

Minimum number of powers = 3