Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

दोहराए गए अंकों वाली संख्याएं C++ में

मान लीजिए हमारे पास एक धनात्मक पूर्णांक N है, हमें N से कम या बराबर उन धनात्मक पूर्णांकों की संख्या ढूंढनी है जिनमें कम से कम 1 दोहराया गया अंक है।

उदाहरण के लिए, यदि इनपुट 99 है, तो आउटपुट 9 होगा, क्योंकि हमारे पास 11, 22, 33, 44, 55, 66, 77, 88, 99 जैसी संख्याएं हैं।

हल करने का दृष्टिकोण

हम पूरक गिनती का उपयोग करते हैं: N से कम या बराबर उन संख्याओं को गिनें जिनके सभी अंक अलग-अलग हैं, फिर N से घटाएं।

  • संयोजन A(m, n) = m * (m-1) * ... * (m-n+1) की गणना करने के लिए फ़ंक्शन A(m, n) परिभाषित करें

  • N+1 को अंक सरणी में बदलें

  • N से कम अंकों वाली सभी-अलग-अलग-अंकों वाली संख्याओं को गिनें

  • समान अंकों की लंबाई वाली संख्याओं के लिए, अंक-दर-अंक डीपी के साथ गिनें

  • पहले से उपयोग किए गए अंकों को ट्रैक करने के लिए विज़िटेड सेट का उपयोग करें

  • अंत में N - (सभी-अलग-अलग-अंकों की गिनती) लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int A(int m, int n){ 
        int ret = 1; 
        for (int i = 0; i < n; i++) { 
            ret *= m; 
            m--; 
        } 
        return ret; 
    } 
    
    int numDupDigitsAtMostN(int N){ 
        vector<int> arr; 
        for (int i = N + 1; i > 0; i /= 10) { 
            arr.insert(arr.begin(), i % 10); 
        } 
        
        int ret = 0; 
        int n = arr.size(); 
        
        // N से कम अंकों वाली संख्याएं
        for (int i = 1; i < n; i++) { 
            ret += 9 * A(9, i - 1); 
        } 
        
        set<int> visited; 
        for (int i = 0; i < n; i++) { 
            int digit = arr[i]; 
            for (int j = (i == 0 ? 1 : 0); j < digit; j++) { 
                if (visited.count(j)) continue; 
                ret += A(9 - i, n - i - 1); 
            } 
            if (visited.count(digit)) break; 
            visited.insert(digit); 
        } 
        
        return N - ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.numDupDigitsAtMostN(99)); 
    return 0;
}

इनपुट

99

आउटपुट

9
  1. C++ में दी गई शर्तों के साथ ग्रिड में 8 संख्याएं भरें C++ में दी गई शर्तों के साथ ग्रिड में 8 संख्याएं भरें

    समस्या विवरण हम 1, 2, 3, 4, 5, 6, 7, 8 को दिए गए चित्र में आठ वृत्तों में इस तरह रखना चाहते हैं कि कोई भी संख्या उस संख्या से सटी न हो जो अनुक्रम में उसके बगल में है। इनपुट ग्रिड 0-1-10 -1-1-1-1 0-1-10 आउटपुट एल्गोरिदम चरण N := 3, M := 4 NOTCONSIDERED := -1 फ़ंक्शन present_in_grid(grid, num

  1. - C++ में N से छोटी अधिकतम 2 अद्वितीय अंकों वाली सभी संख्याएं प्रिंट करना

    इस समस्या में, हमें एक पूर्णांक N दिया गया है और हमें N से छोटी उन सभी संख्याओं को प्रिंट करना है जिनमें अधिकतम 2 अद्वितीय अंक हों यानी संख्या बनाने के लिए अधिकतम 2 अलग-अलग अंकों का उपयोग किया जा सकता है। उदाहरण Input: N = 17 Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 इस समस्या को हल करने

  1. - C++ में ट्राइबोनैकी नंबर्स

    यहां हम देखेंगे कि C++ का उपयोग करके ट्राइबोनैकी नंबर्स कैसे जेनरेट करें। ट्राइबोनैकी नंबर्स फिबोनैकी नंबर्स के समान हैं, लेकिन यहां हम तीन पिछले टर्म्स को जोड़कर एक टर्म जेनरेट कर रहे हैं। मान लीजिए हम T(n) जेनरेट करना चाहते हैं, तो फॉर्मूला नीचे जैसा होगा -T(n) = T(n - 1) + T(n - 2) + T(n - 3)शुरू