इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया जाता है। हमारा कार्य यह जाँचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं।
मितव्ययी संख्या - एक संख्या जिसके अंकों की संख्या दी गई संख्या के अभाज्य गुणनखंड में अंकों की संख्या से अधिक है।
उदाहरण − 625, संख्या 625 का अभाज्य गुणनखंड 5 है 4 ।
625 में अंकों की संख्या 3 होती है।
5 4 . में अंकों की संख्या 2 है।
3 निश्चित रूप से 2 से बड़ा है। इसलिए, 625 एक मितव्ययी संख्या है।
पहले कुछ मितव्ययी नंबर हैं - 125, 128, 243, 256, 343, 512, 625, आदि।
समस्या को समझने के लिए एक उदाहरण लेते हैं
Input: n = 128 Output: Frugal number Explanation : Factors of 128 are 2^7, number of digits 2. The number of digits in 128 is 3. The number is a frugal number.
समाधान दृष्टिकोण
समस्या का एक समाधान यह जाँचना है कि क्या वर्तमान संख्या n एक मितव्ययी संख्या है। इसके लिए हम n के अभाज्य गुणनखंड ज्ञात करेंगे और गुणनखंड में अंकों की संख्या गिनेंगे और फिर संख्या में अंकों की संख्या गिनेंगे। यदि संख्या में अंकों की संख्या गुणनखंडों में संख्याओं से अधिक है, तो संख्या एक मितव्ययी संख्या है अन्यथा यह नहीं है।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
vector<long int> calcPrimeNum(long int n){
bool primeNos[n + 1];
memset(primeNos, true, sizeof(primeNos));
for (int i = 2; i * i <= n; i++) {
if (primeNos[i] == true) {
for (int j = i * 2; j <= n; j += i)
primeNos[j] = false;
}
}
vector<long int> allPrimeNumbers;
for (int i = 2; i < n; i++)
if (primeNos[i])
allPrimeNumbers.push_back(i);
return allPrimeNumbers;
}
int countNumDigits(long int n){
long long int num = n;
int digitCount = 0;
while (num != 0) {
num = num / 10;
digitCount++;
}
return digitCount;
}
bool isFrugalNum(long int n){
vector<long int> primeNum = calcPrimeNum(n);
long int num = n;
long int factorDigitCount = 0;
for (int i = 0; i < primeNum.size(); i++) {
if (num % primeNum[i] == 0) {
long int k = 0;
while (num % primeNum[i] == 0) {
num = num / primeNum[i];
k++;
}
if (k == 1)
factorDigitCount = factorDigitCount + countNumDigits(primeNum[i]);
else if (k != 1)
factorDigitCount = factorDigitCount + countNumDigits(primeNum[i]) + countNumDigits(k);
}
}
return (countNumDigits(n) > factorDigitCount && factorDigitCount != 0);
}
int main(){
long int n = 625;
cout<<"The number "<<n<<" is ";isFrugalNum(n)? cout<<"a Frugal number\n" : cout << "not a Frugal number\n";
return 0;
} आउटपुट
The number 625 is a Frugal number