【C++】全要素の合計との絶対差がkより大きい要素の個数を求める方法

問題の概要

整数型の配列が与えられたとき、「配列全体の要素の合計とその要素自身との絶対差が変数 k より大きい」ような要素の個数を数えるのが本記事の目的です。

解き方はシンプルです。まず配列内の全要素の合計 sum を求めます。そのうえで、各要素 arr[i] について次の条件を判定します。

sum − 2 × arr[i] > k

sum にはすでに arr[i] 自身が含まれているため、合計からその要素を2回引くことで「自分以外の要素の合計」との差を計算できます。この条件が真であればカウントを1つ増やします。

具体例で理解する

入力：arr[] = { 1, 2, 3, 0, 3, 2, 0, 1 }、k = 10

出力：条件を満たす要素の個数：2

解説：要素の合計は12です。各要素について差を計算すると以下のようになります。

12−1−1=10、12−2−2=8、12−3−3=6、12−0−0=12

10 を超えるのは 12 のみであり、これは値が 0 の2つの要素に該当します。したがって答えは 2 となります。

入力：arr[] = { 1, 1, 1, 1, 1 }、k = 10

出力：条件を満たす要素の個数：0

解説：要素の合計は5です。各要素 1 について 5−1−1=3 となり、3 < 10 であるため条件を満たす要素は存在しません。

アルゴリズムの手順

• 乱数などで初期化された整数配列 arr[] を用意します。
• 関数 numberCount(int arr[], int n, int k) は、配列とその長さを受け取り、「他のすべての要素の合計との絶対差が k より大きい」要素の個数を返します。
• カウント用変数 count を 0 で初期化します。
• 配列内の全要素の合計を sum として計算します。
• i = 0 から i < n まで配列全体を走査します。
• 各要素 arr[i] について、sum − arr[i] − arr[i] の絶対値が k より大きければ count をインクリメントします。
• ループ終了後、count を最終結果として返します。

C++による実装例

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int numberCount(int arr[],int n, int k){
    int count=0;
    int sum=0;
    int i;
    for(i=0;i<n;i++)
       { sum+=arr[i]; }
    for(int i=0;i<n;i++){
       if( abs(sum-arr[i]-arr[i]) > k ){
          count++;
       }
   }
    return count;
}
int main(){
    int Arr[]={ 1,2,3,4 };
    int len=sizeof(Arr)/sizeof(Arr[0]);
    int K=5;
    cout<<endl<<"Count of elements: "<<numberCount(Arr,len,K);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of elements: 2

この例では配列 { 1, 2, 3, 4 } の合計は10であり、たとえば要素 4 に対しては |10−4−4| = 2、要素 1 に対しては |10−1−1| = 8 といった具合に判定され、条件 abs(sum − 2×arr[i]) > 5 を満たすのは2つの要素です。