విరామ శ్రేణి లీట్‌కోడ్ పరిష్కారంలో బేసి సంఖ్యలను లెక్కించండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది మైక్రోసాఫ్ట్
మఠం

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు తక్కువ మరియు అధిక రెండు ప్రతికూల-కాని పూర్ణాంకాలు ఇవ్వబడతాయి. ఇచ్చిన విరామ పరిధిలో [తక్కువ, అధిక] ఎన్ని బేసి సంఖ్యలు ఉన్నాయో మనం కనుగొనాలి.

ఉదాహరణ

low = 3, high = 7
3

వివరణ:

3 మరియు 7 మధ్య బేసి సంఖ్యలు [3, 5, 7].

low = 8, high = 10
1

వివరణ:

8 మరియు 10 మధ్య బేసి సంఖ్యలు [9].

అప్రోచ్

ఇచ్చిన విరామ పరిధిలో బేసి సంఖ్యల మొత్తం గణనను కనుగొనటానికి ఒక మార్గం, విరామం యొక్క ఎడమ నుండి కుడి సరిహద్దుకు ప్రయాణించడం a లూప్ మరియు ప్రతి బేసి సంఖ్యకు బేసి కౌంటర్ పెంచండి. బేసి సంఖ్యలను ఒక పరిధిలో లెక్కించడానికి ఇది చాలా మందకొడిగా ఉంటుంది. ఇది సరళ సమయ సంక్లిష్టతను తీసుకుంటుంది మరియు అలాంటి సులభమైన సమస్య కోసం మేము కోరుకోము.

ఇచ్చిన విరామ పరిధిలో మొత్తం బేసి సంఖ్యలను కనుగొనడం చాలా సులభం, ఎందుకంటే విరామ పరిధిలో దాదాపు సగం మరియు సగం బేసి సంఖ్యలు ఉన్నాయని మాకు తెలుసు.
కానీ మేము విరామ సరిహద్దులను చాలా జాగ్రత్తగా పరిశీలించాలి. కాబట్టి మనం చేయగలిగేది ఏమిటంటే, మొదటి n సహజ సంఖ్యలలో బేసి సంఖ్యల గణన కోసం సూత్రాన్ని రూపొందించవచ్చు. దానిని లెక్కించనివ్వండి [n]. అప్పుడు తక్కువ మరియు అధిక మధ్య బేసి సంఖ్యలు దీనికి సమానంగా ఉంటాయి:
count [low, high] = count [high] - count [low-1].

విరామ శ్రేణి లీట్‌కోడ్ పరిష్కారంలో బేసి సంఖ్యలను లెక్కించండి

ఇప్పుడు గణన కోసం కొన్ని ఉదాహరణలు తీసుకుంటున్నాను [i]:

లెక్కించు [1] = 1
లెక్కించు [2] = 1
లెక్కించు [3] = 2
లెక్కించు [4] = 2
లెక్కించు [5] = 3

మేము ఆ గణనను తగ్గించవచ్చు [n] = (n + 1) / 2
అందువల్ల [తక్కువ, అధిక] = (అధిక + 1) / 2 - తక్కువ / 2 లెక్కించండి

అమలు

ఇంటర్వెల్ రేంజ్ లీట్‌కోడ్ సొల్యూషన్‌లో కౌంట్ బేసి సంఖ్యల కోసం సి ++ ప్రోగ్రామ్ (నైవ్ అప్రోచ్)

#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

ఇంటర్వెల్ రేంజ్ లీట్‌కోడ్ సొల్యూషన్‌లో కౌంట్ బేసి సంఖ్యల కోసం జావా ప్రోగ్రామ్ (నైవ్ అప్రోచ్)

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

ఇంటర్వెల్ రేంజ్ లీట్‌కోడ్ సొల్యూషన్‌లో కౌంట్ బేసి సంఖ్యల కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

ప్రతి సంఖ్యకు ప్రయాణించడం పడుతుంది పై) ఫార్ములా ఉపయోగించి జవాబులను లెక్కించేటప్పుడు సమయ సంక్లిష్టత స్థిరమైన సమయం పడుతుంది O (1) అమలు చేయడానికి.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): జవాబులను నిల్వ చేయడానికి ఉపయోగించే వేరియబుల్ మినహా రెండు పరిష్కారాలలో అదనపు స్థలం ఉపయోగించబడదు.