Count Even Numbers
空でない整数のリスト nums が与えられたとき、その値のうち偶数であるものの個数を返します。数を 2 で割ったときに余りがなければ偶数です。これには 0 や -4 などの負の数も含まれます。
関数
- numsinteger-array
- 確認する整数のリスト
- 戻り値integer
- nums 内の偶数の数
制約
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
例
- 入力
- nums = [3, 8, 12, 5, 6]
- 出力
- 3
- 説明
8、12、6は2で割り切れますが、3と5は割り切れません。答えは3です。
- 入力
- nums = [-4, -3, 0, 7]
- 出力
- 2
- 説明
-4 = 2 × (-2)と0 = 2 × 0なので、どちらも偶数です。-3と7は奇数で、個数は2です。
- 入力
- nums = [1, 9, 15]
- 出力
- 0
- 説明
1、9、15はいずれも奇数なので、答えは0です。
発展問題
次のような質問をたくさん受けます。インデックス l とインデックス r の間には、偶数の値がいくつありますか？nums を1回走査した後、それぞれの質問に O(1) 時間で答えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
偶数を
2で割ったとき、余りはいくつですか？値
xが偶数であるのは、x % 2が0の場合に限ります。注意してください。負の奇数の場合、言語によっては余りが1ではなく-1になります。カウンターを
0で開始し、各値を一度ずつ読み取り、2で割った余りが0の場合は1を加えます。
解説
各値を1回ずつ確認し、2で割ったときの余りが0になるものを数えます。余りを1と比較して奇数かどうかを判定するのではなく、0と比較することで、負の数も正しく扱えます。
偶数の値を集めてから、それらを数える
考え方
filterで偶数の値を取り出し、その結果の長さを返します。[3, 8, 12, 5, 6]の場合、フィルタリング後のリストは[8, 12, 6]なので、答えは3です。
時間計算量はO(n)ですが、新しいリストにはO(n)のメモリが必要です。長さを一度読み取るだけなのに、最大5000個の値を保持します。
アルゴリズム
numsの中でx % 2 == 0を満たすすべてのxを保持する新しいリストを作成します。- そのリストの長さを返します。
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)カウンターを使って数える
考え方
リストの代わりにカウンターを使い、x % 2 == 0 を満たす値ごとに 1 を加えます。偶数は符号にかかわらず余りが 0 になるため、どの言語でも -4 と 0 ではこの判定が成り立ちます。奇数を判定するために x % 2 == 1 と書いても、そうはなりません。C、Java、JavaScript、およびほとんどの C 系言語では、余りの符号は数値の符号と同じになるため、-3 % 2 は -1 です。
1 回の走査と 1 つの整数で済みます。時間計算量は O(n)、空間計算量は O(1) です。
アルゴリズム
countを0に設定します。nums内のすべての値xを順に処理します。x % 2 == 0の場合、countに1を加えます。- ループの後、
countを返します。
def countEvens(nums):
count = 0
for x in nums:
if x % 2 == 0: # 0 also works for negatives, where the remainder can be -1
count += 1
return count
落とし穴と境界ケース
x % 2 == 1で奇数の値を数え、その数を長さから引く方法。C系の言語では-3 % 2は-1になるため、[-3]は0ではなく1を返します。0を偶数でも奇数でもないものとして扱う方法。0 = 2 × 0なので、[0]は1を返します。- ビット判定を
x & 1 == 0と書く方法。C、C++、JavaScriptでは、==は&より優先順位が高いため、これはx & (1 == 0)を意味します。これは常に0となり、何も数えません。(x & 1) == 0と書いてください。
よくある質問3
コードで数値が偶数かどうかを確認するにはどうすればよいですか？
2で割った余りがゼロかどうかを確認します：x % 2 == 0。-3 % 2が-1になる言語でも、正の数、負の数、ゼロで機能します。(x & 1) == 0で最下位ビットを確認することもできます。
ゼロは偶数ですか？
はい。ゼロを2で割ると余りなしで0になるため、偶数の定義に当てはまります。また、偶数が属する奇数-1と1の間にあります。
配列内の偶数を数える時間計算量は何ですか？
カウンターを使った1回の走査にかかる時間はO(n)、追加の領域はO(1)です。すべての値を確認する必要があるため、O(n)より速い方法はありません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def countEvens(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [3, 8, 12, 5, 6]
期待される出力
3