ধারণা
প্রদত্ত সংখ্যা N এর ক্ষেত্রে, আমাদের কাজ হল সবচেয়ে বড় নিখুঁত ঘনক নির্ধারণ করা যা সংখ্যা থেকে ন্যূনতম সংখ্যাগুলি (সম্ভবত 0) মুছে ফেলার মাধ্যমে তৈরি করা যেতে পারে। তাই লক্ষ্যে পৌঁছানোর জন্য প্রদত্ত নম্বর থেকে যেকোনো সংখ্যা মুছে ফেলা যেতে পারে।
A কে একটি নিখুঁত ঘনক বলা হয় যদি A =B^3 কিছু পূর্ণসংখ্যা B.
এর জন্যদেখা গেছে সংখ্যাটি নিখুঁত হতে না পারলে কিউব প্রিন্ট-১।
উদাহরণ
ধরুন N =1025। এটা দেখা গেছে যে উপরের সংখ্যা থেকে 0 মুছে দিলে আমরা অবশিষ্ট সংখ্যা হিসাবে 125 পাব, যা 5 এর ঘনমূল (5 * 5 * 5 =125)।
ধরুন N =806। এটা দেখা গেছে যে আমরা যদি 0 এবং 6 মুছে ফেলি তাহলে আমাদের অবশিষ্ট সংখ্যা হিসাবে 8 থাকবে যা 2 এর ঘনমূল (2 * 2 * 2 =8)
পদ্ধতি
সংখ্যার প্রতিটি পরের জন্য আমাদের পরীক্ষা করতে হবে সংখ্যাটি ঘনক কিনা এবং তারপরে তাদের মধ্যে সর্বাধিক ঘনকের সাথে তুলনা করতে হবে। সমস্ত সাবস্ট্রিং তৈরি করার জন্য আমরা শেষ অক্ষর মুছে ফেলি যাতে পরবর্তী পারমুটেশন তৈরি করা যায়।
সুতরাং আমাদের একটি সংখ্যা num ="876" আছে, তারপরে আমরা বর্তমান স্ট্রিং-এ প্রতিটি উপাদান যোগ করি যা আমাদের দেবে −
8 87 876
এর পরে পুনরাবৃত্তিটি "87" এর সাথে ফিরে আসবে, তারপর '7' সরানো হবে এবং পরবর্তী পুনরাবৃত্তি বলা হবে যা পরবর্তী "86" দেবে। সুতরাং এটি '8' এর জন্য পুনরাবৃত্তি সম্পূর্ণ করবে, পরবর্তীটি '7' থেকে শুরু হবে যা "6" এর পরে "7" এবং "76" দেবে।
এর ফলস্বরূপ, এটি প্রদত্ত নম্বর 876-এর সমস্ত পরবর্তী অংশ দেবে।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mx1 = INT_MIN;
bool is_Cube(ll x1){
int found = 0;
for (int i = 2; i <= (x1 / 2); i++){
if (x1 % i == 0){
if ((i * i * i) == x1)
found = 1;
}
}
if (found == 1)
return true;
else
return false;
}
void printSubSeqRec(string str, int n1, int index = -1, string curr1 = ""){
if (index == n1)
return;
if (curr1 != ""){
ll temp = stoi(curr1);
if (is_Cube(temp))
mx1 = max(mx1, temp);
}
for (int i = index + 1; i < n1; i++){
curr1 += str[i];
printSubSeqRec(str, n1, i, curr1);
curr1 = curr1.erase(curr1.size() - 1);
}
return;
}
int main(){
int nums1 = 1025;
string str1 = to_string(nums1);
printSubSeqRec(str1, str1.size());
if (mx1 != INT_MIN)
cout << mx1;
else
cout << "NOT FOUND ANY CUBE";
return 0;
} আউটপুট
125
