একটি সংখ্যাকে অন্য সংখ্যার ঘাতের রূপে প্রকাশ করার সমস্যা আলোচনা করব। আমাদের দুটি সংখ্যা দেওয়া আছে, x এবং y। আমাদের বলতে হবে y কি x-এর ঘাতের রূপে প্রকাশ করা সম্ভব, যেখানে x-এর প্রতিটি ঘাত একবার ব্যবহার করা যাবে। উদাহরণস্বরূপ:
Input: x = 4, y = 11 Output: true Explanation: 4^2 - 4^1 - 4^0 = 11 अतः y, x-এর ঘাতে প্রকাশ করা সম্ভব। Input: x = 2, y = 19 Output: true Explanation: 2^4 + 2^1 + 2^0 =19 अतः y, x-এর ঘাতে প্রকাশ করা সম্ভব। Input: x = 3, y = 14 Output: false Explanation: 14 = 3^2 + 3^1 + 3^0 + 3^0 কিন্তু x-এর একটি ঘাত দুইবার ব্যবহার করা যায় না।
সমাধানের পদ্ধতি
19 কে 2-এর ঘাতের রূপে প্রকাশ করার উদাহরণ দেখে আমরা একটি সমীকরণ তৈরি করতে পারি:
c0(x^0) + c1(x^1) + c2(x^2) + c3(x^3) + … = y ….(1),
যেখানে c0, c1, c2 হতে পারে -1, 0, +1 যা বোঝায় (-1) টার্ম বিয়োগ করবে, (+1) টার্ম যোগ করবে, (0) টার্ম অন্তর্ভুক্ত করবে না।
c1(x^1) + c2(x^2) + c3(x^3) + … = y - c0,
x কে কমন ফ্যাক্টর হিসেবে নিয়ে,
c1(x^0) + c2(x^1) + c3(x^2) + … = (y - c0)/x ….(2),
সমীকরণ (1) এবং (2) থেকে আমরা আবার সংখ্যাটিকে একইভাবে ঘাতের রূপে প্রকাশ করতে পারি। একটি সমাধান থাকার জন্য (y - Ci) x দিয়ে বিভাজ্য হতে হবে এবং Ci শুধু -1, 0, +1 ধারণ করতে পারে।
সুতরাং চূড়ান্তভাবে আমাদের y>0 পর্যন্ত চেক করতে হবে [(y-1) % x == 0] বা [(y) % x == 0] বা [(y+1) % x == 0] অথবা কোনো সমাধান নেই।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main(){ int x = 2, y = 19; // y>0 পর্যন্ত y-এর বিভাজ্যতা চেক করুন while (y>0) { // যদি y-1, x দিয়ে বিভাজ্য হয়। if ((y - 1) % x == 0) y = (y - 1) / x; // যদি y, x দিয়ে বিভাজ্য হয়। else if (y % x == 0) y = y / x; // যদি y+1, x দিয়ে বিভাজ্য হয়। else if ((y + 1) % x == 0) y = (y + 1) / x; // কোনো শর্ত পূরণ না হলে মানে // y, x-এর ঘাতে প্রকাশ করা সম্ভব নয়। else break; } if(y==0) cout<<"y can be represented in terms of the power of x."; else cout<<"y cannot be represented in terms of the power of x."; return 0; }
আউটপুট
y can be represented in terms of the power of x.
উপসংহার
এই টিউটোরিয়ালে, আমরা আলোচনা করেছি কিভাবে চেক করব একটি সংখ্যাকে অন্য সংখ্যার ঘাতে প্রকাশ করা সম্ভব কিনা। আমরা একটি সহজ পদ্ধতি আলোচনা করেছি বর্তমান, আগের, এবং পরের সংখ্যার y দিয়ে বিভাজ্যতা চেক করে। আমরা এই সমস্যার জন্য C++ প্রোগ্রামও আলোচনা করেছি যা আমরা C, Java, Python ইত্যাদি প্রোগ্রামিং ভাষায়ও করতে পারি। আশা করি আপনি এই টিউটোরিয়ালটিকে উপকারী পাবেন।
