Бројање непарних бројева у интервентном опсегу Леетцоде решење


Ниво тешкоће Лако
Често питани у мицрософт
Математика

Изјава о проблему

У овом проблему су нам дате две негативне целобројне вредности мала и велика. Морамо да пронађемо колико има непарних бројева у датом опсегу интервала [низак, висок].

Пример

low = 3, high = 7
3

objašnjenje:

Непарни бројеви између 3 и 7 су [3, 5, 7].

low = 8, high = 10
1

objašnjenje:

Непарни бројеви између 8 и 10 су [9].

Приступ

Један од начина за проналажење укупног броја непарних бројева у датом опсегу интервала је прелазак са леве на десну границу интервала у петља и повећати непарни бројач за сваки непаран број. Али ово ће бити врло хром приступ за бројање непарних бројева у опсегу. Ово ће захтијевати линеарну временску сложеност и не желимо такав лак проблем.

Врло је лако пронаћи укупне непарне бројеве у датом опсегу интервала, јер знамо да у распону интервала има готово половину непарних и пола непарних бројева.
Али границе интервала морамо узети у обзир врло пажљиво. Дакле, оно што можемо је да обликујемо формулу за бројање непарних бројева у првих н природних бројева. Нека се рачуна [н]. Тада ће непарни бројеви између ниског и високог бити једнаки:
цоунт [лов, хигх] = цоунт [хигх] - цоунт [лов-1].

Бројање непарних бројева у интервентном опсегу Леетцоде решење

Узмимо неколико примера за цоунт [и]:

цоунт [1] = 1
цоунт [2] = 1
цоунт [3] = 2
цоунт [4] = 2
цоунт [5] = 3

Можемо закључити да је број [н] = (н + 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

Анализа сложености бројања непарних бројева у решењу Леетцоде интервала у опсегу

Сложеност времена

Трајање за сваки број ће трајати Он) временска сложеност док израчунавање анса помоћу формуле траје константно О (1) да извршава.

Сложеност простора 

О (1): У оба решења се не користи додатни простор, осим променљиве која се користи за чување анс.