एक संख्या एन को देखते हुए, पता लगाएं कि श्रेणी 0 में कितनी संख्या अंकों 2 है ... n

Question

यह एक साक्षात्कार प्रश्न है।

एक संख्या n को देखते हुए, यह पता लगाना है कि कितने नंबर अंकों 2 रेंज 0 में है ... n

उदाहरण के लिए,

इनपुट = 13 उत्पादन = 2 (2 और 12)

मैंने सामान्य ओ (एन^2) समाधान दिया लेकिन क्या एक बेहतर दृष्टिकोण है।

वहाँ किसी भी 'चाल' सूत्र ने मुझे जवाब सही दूर

Answer 1

प्राप्त करने के लिए मदद मिलेगी गणना संख्या ऐसा नहीं संख्या कम से कम 10 ^{कश्मीर} अलावा अंकों 2. है, देखते हैं है उनमें से 9 ^के उनमें से। तो फिर यह n, 10 ^{कश्मीर} से संख्या के इलाज के लिए बनी हुई है जहां

10^k <= n < 10^(k+1) 

जो आप (मामलों 2 और दूसरों विभेदित किया जा करने के लिए है) को व्यक्तिगत रूप से पहले अंक का इलाज कर सकते हैं, और उसके बाद पहले 2 अंक आदि

उदाहरण के लिए, n = 2345 के लिए, हम पाते हैं 9^3 = 729 संख्या 1000 से नीचे अंकों 2 बिना देखते हैं वहाँ फिर 2000 से 2345 तक की अवधि के 1000 1999 तक की सीमा में फिर से इस तरह की संख्या 729 हैं, वहाँ कुल 1458 के लिए कोई नहीं है, इसलिए अंक 2 वाले नंबर

हैं

2345 - 1458 = 887 

Answer 2

अंकों एबीसीडीईएफ के साथ संख्या को देखते हुए आप [0,F], [0,E9], [0,D99], [0,C999], [0,B9999] और [0,A99999] में '2 की संख्या को गिन सकते हैं और उन्हें जोड़ सकते हैं।

फिर [0, X9999...999] श्रेणी के लिए, शीर्ष संख्या T = X9999...999(X+1) * 10<sup>nines</sup> -1 के रूप में लिखा जा सकता है।

की संख्या 'उस श्रेणी में 2 की है:

((X >= 2 ? 1/(X + 1)) : 0) + nines/10) * (T + 1); 

यही कारण है: अगर X >= 2, है कि संख्या के अंश एक' देखते हैं 2 'स्थिति नौ + 1 1/(X+1) है, कुल में से (T+1)/(X+1) '2 उस स्थिति में है। यदि X < 2 है, तो उस स्थिति पर [0..T] पर कोई संख्या '2' नहीं है।

अन्य अंकों पदों के लिए, संख्या के 1/10 एक '2' देखने के लिए कि हर अंकों की स्थिति में आसान है, इसलिए (T+1)/10 'स्थिति 0 पर 2 के, (T+1)/10' स्थिति 1, आदि में से 2 के देखते हैं कुल, (T+1) * nines/10।

इस समाधान की जटिलता ओ (लॉगएन) है।

Answer 3

इस

मैं

def count2(n) : 
    return [p for p in range(n+1) if '2' in str(p)] 

मेरा पहला मसौदा (अजगर कोड) कोडिंग के बारे में कैसे जाना होगा और आप युक्त संख्या के साथ एक सूची प्रदान करेगा है।

प्रदर्शन के संदर्भ में यह है कि बुरा नहीं है, के लिए एन = 10,000,000 औसत यात्रा 5.5 सेकंड

लेता

Answer 4

तर्क 'अंकों' एक जो हम गिनती करने के लिए और आर्ग 'संख्या' जहां तक ​​है चाहते है हम गिनना चाहते हैं। उदाहरण के लिए: यदि हम '1' की घटनाओं को 0 से 12 तक गिनना चाहते हैं, तो फ़ंक्शन को अंक = 1, और संख्या = 12 के साथ कॉल करें, और यह '1' की घटनाओं की संख्या वापस कर देगा।

int countOccurrences(int digit, int number) 
{ 
    int counter = 0; 
    for(int i=1; i<number; i++) 
    { 
     int j = i; 
     while(j > 0) 
     { 
      if(j%10 == digit) 
       counter++; 
      j /= 10; 
     } 
    } 
    return counter; 
}