एक इंटरवल रेंज लेटकोड सॉल्यूशन में विषम संख्याओं की गणना करें


कठिनाई स्तर आसान
में अक्सर पूछा माइक्रोसॉफ्ट
मठ

समस्या का विवरण

इस समस्या में, हमें दो गैर-नकारात्मक पूर्णांक निम्न और उच्च दिए गए हैं। हमें यह पता लगाना है कि दी गई अंतराल सीमा में कितनी विषम संख्याएँ हैं [निम्न, उच्च]।

उदाहरण

low = 3, high = 7
3

स्पष्टीकरण:

3 और 7 के बीच विषम संख्याएं हैं [3, 5, 7]।

low = 8, high = 10
1

स्पष्टीकरण:

8 और 10 के बीच विषम संख्याएं हैं [9]।

दृष्टिकोण

दिए गए अंतराल सीमा में विषम संख्याओं की कुल संख्या को खोजने का एक तरीका है, एक में अंतराल की बाईं से दाईं सीमा तक पार करना पाश और प्रत्येक विषम संख्या के लिए विषम काउंटर बढ़ाएं। लेकिन यह एक सीमा में विषम संख्याओं की गिनती के लिए एक बहुत ही लंगड़ा दृष्टिकोण होगा। यह रैखिक समय जटिलता ले जाएगा, और हम ऐसी आसान समस्या के लिए नहीं चाहते हैं।

दिए गए अंतराल सीमा में कुल विषम संख्याओं को खोजना बहुत आसान है क्योंकि हम जानते हैं कि एक अंतराल सीमा में लगभग आधी और आधी विषम संख्याएँ हैं।
लेकिन हमें अंतराल सीमाओं पर बहुत सावधानी से विचार करना होगा। तो हम क्या कर सकते हैं कि हम पहले n प्राकृतिक संख्याओं में विषम संख्याओं की गणना के लिए सूत्र बना सकते हैं। इसे गिनने दो [n]। फिर निम्न और उच्च के बीच विषम संख्याएँ बराबर होंगी:
गिनती [निम्न, उच्च] = गिनती [उच्च] - गिनती [निम्न -१]।

एक इंटरवल रेंज लेटकोड सॉल्यूशन में विषम संख्याओं की गणना करें

अब गिनती के लिए कुछ उदाहरण लेना [i]:

गिनती [१] = १
गिनती [१] = १
गिनती [१] = १
गिनती [१] = १
गिनती [१] = १

हम उस गणना को घटा सकते हैं [n] = (n + 1) / 2
इसलिए गिनती [निम्न, उच्च] = (उच्च + 1) / 2 - निम्न / 2

कार्यान्वयन

एक इंटरवल रेंज लेटकोड सॉल्यूशन में काउंट ऑड नंबर के लिए C ++ प्रोग्राम (Naive दृष्टिकोण)

#include <iostream>
using namespace std;

int countOdds(int low, int high) 
{
    int count=0;
    for(int i=low;i<=high;i++)
        if(i%2==1) count++;
        
    return count;
}

int main()
{
    int low=3,high=7;  
    cout<< countOdds(low, high) <<endl;
}
3

एक इंटरवल रेंज लेटकोड सॉल्यूशन में काउंट ऑड नंबर के लिए जावा प्रोग्राम (Naive एप्रोच)

class CountOdd
{  
    public static int countOdds(int low, int high) 
    {
        int count=0;
        for(int i=low;i<=high;i++)
            if(i%2==1) count++;
        
        return count;
    }
    
    public static void main(String args[])
    {
        int low=3,high=7;
        System.out.println(countOdds(low, high));
    }
}
3

सी ++ प्रोग्राम (इष्टतम दृष्टिकोण)

#include <iostream>
using namespace std;

int countOdds(int low, int high) 
{
   return (high + 1) / 2 - low / 2;       
}

int main()
{
    int low=3,high=7;  
    cout<< countOdds(low, high) <<endl;
}
3

जावा प्रोग्राम (इष्टतम दृष्टिकोण)

class CountOdd
{  
    public static int countOdds(int low, int high) 
    {
        return (high + 1) / 2 - low / 2;   
    }
    
    public static void main(String args[])
    {
        int low=3,high=7;
        System.out.println(countOdds(low, high));
    }
}
3

एक इंटरवल रेंज लेटकोड सॉल्यूशन में काउंट ऑड नंबर के लिए जटिलता विश्लेषण

समय जटिलता

प्रत्येक नंबर के लिए ट्रैवर्सिंग लगेगा पर) फार्मूला का उपयोग करके एएनएस की गणना करते समय समय जटिलता निरंतर समय लगता है ओ (1) निष्पादन हेतु।

अंतरिक्ष जटिलता 

ओ (1): Ans को स्टोर करने के लिए उपयोग किए जाने वाले वैरिएबल को छोड़कर दोनों सॉल्यूशंस में कोई अतिरिक्त स्थान का उपयोग नहीं किया जाता है।