Підрахунок непарних чисел у інтервалі інтервалів Leetcode Solution


Рівень складності Легко
Часто запитують у Microsoft
Математика

Постановка проблеми

У цій задачі нам дано два цілих невід’ємних числа низьке і високе. Ми маємо знайти, скільки непарних чисел є в даному інтервалі інтервалу [низький, високий].

Приклад

low = 3, high = 7
3

Пояснення:

Непарні числа від 3 до 7 - [3, 5, 7].

low = 8, high = 10
1

Пояснення:

Непарні числа від 8 до 10 складають [9].

Підхід

Одним із способів знайти загальну кількість непарних чисел у даному діапазоні інтервалу є перехід від лівої до правої межі інтервалу в петля і збільшити непарний лічильник для кожного непарного числа. Але це буде дуже кульгавий підхід для підрахунку непарних чисел у діапазоні. Це займе лінійну складність у часі, і ми не хочемо мати таку легку проблему.

Дуже легко знайти загальні непарні числа в даному діапазоні інтервалів, оскільки ми знаємо, що в діапазоні інтервалів є майже половина парних і половина непарних чисел.
Але ми повинні дуже ретельно розглядати межі інтервалів. Отже, що ми можемо зробити, це сформувати формулу для підрахунку непарних чисел у перших n натуральних числах. Нехай це буде рахуватися [n]. Тоді непарні числа між низьким і високим будуть дорівнювати:
count [низький, високий] = count [high] - рахунок [низький-1].

Підрахунок непарних чисел у інтервалі інтервалів Leetcode Solution

Тепер візьмемо кілька прикладів для count [i]:

кол [1] = 1
кол [2] = 1
кол [3] = 2
кол [4] = 2
кол [5] = 3

Ми можемо зробити висновок, що рахунок [n] = (n + 1) / 2
Звідси кількість [низька, висока] = (висока + 1) / 2 - низька / 2

Реалізація

Програма C ++ (наївний підхід) для підрахунку непарних чисел у інтервалі інтервалів Leetcode Solution

#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

Програма Java (наївний підхід) для підрахунку непарних чисел у інтервалі інтервалів Leetcode Solution

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

Програма C ++ (оптимальний підхід)

#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

Програма Java (оптимальний підхід)

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

Аналіз складності для підрахунку непарних чисел у інтервалі інтервалів Leetcode

Складність часу

Перехід по кожному номеру займе О (п) складність часу під час обчислення ансів за формулою займає постійний час O (1) виконати.

Складність простору 

O (1): В обох рішеннях не використовується зайвий простір, за винятком змінної, яка використовується для зберігання ans.