【Java】区間内の偶数の個数

問題

サイズがnである数列aの区間x → yの偶数の個数を求めよ。

入力値

標準入力の入力値は下記の通り。

10 2 8
0 1 2 3 4 5 6 7 8 9

変数に置き換えると下記の通り。

n = 10
x = 2
y = 8
a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Javaのコードに使いやすいように一般化

1. 配列aを、偶数なら1で奇数なら0で表記し直す配列bを作成する。

   • a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
   • b = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0}

2. 累積和を使って偶数の個数を求める。

   • 配列bの区間x → yは、下記の[ ]の通り。
   • b = {1, 0, [1, 0, 1, 0, 1, 0, 1], 0}
   • 1 + 1 + 1 + 1 = 4個
   • 配列bの区間x → yの和 = 配列aの偶数の個数
   • ∴ 配列aの偶数の個数 = 配列bの区間b[x] → b[y]の和 = s[y + 1] - s[x]
     ※配列sについては、従前の記事の「累積和と区間の和」より

コード例

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, x, y;
        n = sc.nextInt();
        x = sc.nextInt();
        y = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 配列 b を作成
        // サイズ n の配列 b を初期化
        int[] b = new int[n]; 
        // i を 0 から n-1 まで繰り返す
        for (int i = 0; i < n; i++) {
            // a[i] が偶数なら b[i] = 1 とする
            if (a[i] % 2 == 0) {
                b[i] = 1;
            // a[i] が奇数なら b[i] = 0 とする
            } else {
                b[i] = 0;
            }
        }
        

        // 累積和の配列 s を作成
        int[] s = new int[n + 1];

        for (int i = 0; i < n; i++) {
            s[i+1] = s[i] + b[i];
        }
        
        // 区間 b[x] → b[y] の和 = s[y + 1] - s[x] を出力
        System.out.println(s[y + 1] - s[x]);
    }
}

コード例の解説

今回もコード例の解説は行いません。
今回の肝である配列bを生成する下記のコードも可読性が高く、累積和の配列を作成するコードも、区間の和を出力するコードも使いまわしているコードであるためです。

int[] b = new int[n]; 

for (int i = 0; i < n; i++) {
    if (a[i] % 2 == 0) {
        b[i] = 1;
    } else {
        b[i] = 0;
    }
}