अवधारणा
दी गई संख्या N के संबंध में, हमारा कार्य सबसे बड़ा पूर्ण घन निर्धारित करना है जिसे संख्या से न्यूनतम अंक (संभवतः 0) हटाकर बनाया जा सकता है। तो लक्ष्य तक पहुंचने के लिए दिए गए नंबर से किसी भी अंक को हटाया जा सकता है।
A को एक पूर्ण घन कहा जाता है यदि किसी पूर्णांक B के लिए A =B^3 हो।
यह देखा गया है कि यदि संख्या पूर्ण घन प्रिंट -1 नहीं हो सकती है।
उदाहरण
मान लीजिए 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' से शुरू होगा जो "7" और "76" उसके बाद "6" देगा।
इसके परिणामस्वरूप, यह दी गई संख्या 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