区間範囲リートコードソリューションで奇数を数える


難易度 簡単に
よく聞かれる マイクロソフト
数学

問題文

この問題では、XNUMXつの非負の整数lowとhighが与えられます。 与えられた区間範囲[低、高]に奇数がいくつあるかを見つける必要があります。

low = 3, high = 7
3

説明:

3と7の間の奇数は[3、5、7]です。

low = 8, high = 10
1

説明:

8から10までの奇数は[9]です。

アプローチ

指定された間隔範囲内の奇数の総数を見つけるXNUMXつの方法は、間隔の左から右の境界までトラバースすることです。 ループ 奇数ごとに奇数カウンターを増やします。 しかし、これは範囲内の奇数を数えるための非常に不完全なアプローチになります。 これには線形の時間計算量が必要であり、このような簡単な問題は望ましくありません。

間隔範囲にはほぼ半分の偶数と半分の奇数があることがわかっているため、指定された間隔範囲内の合計奇数を見つけるのは非常に簡単です。
ただし、間隔の境界を慎重に検討する必要があります。 したがって、私たちにできることは、最初のn個の自然数の奇数の数の式を作成できることです。 count [n]とします。 その場合、低と高の間の奇数は次のようになります。
count [low、high] = count [high] – count [low-1]。

区間範囲リートコードソリューションで奇数を数える

ここで、count [i]の例をいくつか取り上げます。

count [1] = 1
count [2] = 1
count [3] = 2
count [4] = 2
count [5] = 3

count [n] =(n + 1)/ 2と推測できます
したがって、count [low、high] =(high + 1)/ 2 – low / 2

製品の導入

区間範囲リートコードソリューションで奇数を数えるためのC ++プログラム(ナイーブアプローチ)

#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プログラム(ナイーブアプローチ)

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

区間範囲リートコード解における奇数数のカウントの複雑さの分析

時間の複雑さ

各番号のトラバースには時間がかかります O(N) 数式を使用してansを計算する際の時間計算量には一定の時間がかかります O(1) 実行する。

スペースの複雑さ 

O(1): ansを格納するために使用される変数を除いて、両方のソリューションで余分なスペースは使用されません。