সমস্যা বিবরণ
দুটি ধনাত্মক পূর্ণসংখ্যা N এবং X দেওয়া আছে। কাজ হল N কে X-এর ক্ষমতার যোগফল হিসেবে প্রকাশ করা (X⁰ + X¹ + ... + Xⁿ) যাতে X-এর ক্ষমতার পদের সংখ্যা ন্যূনতম হয়।
N কে তৈরি করতে ব্যবহৃত X-এর ক্ষমতার ন্যূনতম সংখ্যা প্রিন্ট করতে হবে।
যদি 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 বার প্রকাশ করতে হবে।
উদাহরণ কোড
#include <iostream>
using namespace std;
int minNumOfPower(int n, int x) {
if (x == 1) {
return n;
}
int result = 0;
while (n > 0) {
result = result + (n % x);
n = n / x;
}
return result;
}
int main() {
int n = 15;
int x = 3;
cout << "Minimum number of powers = " << minNumOfPower(15, 3) << endl;
return 0;
}
আউটপুট
উপরোক্ত প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট জেনারেট হবে:
Minimum number of powers = 3
