C++で通過する車のペアを数える

入力 − arr [] ={1,0,1,0,1}

出力 −通過する車のペアの数は次のとおりです：3

説明 −インデックス0が1未満である（0,1）のペアは次のとおりです。−（arr [1]、arr [2]）、（arr [1]、arr [4]）、（arr [3]、arr [4]）

入力 − arr [] ={1,0,0,0,0}

出力 −通過する車のペアの数は次のとおりです：0

説明 −インデックス0が1未満の（0,1）のペアはありません。

以下のプログラムで使用されているアプローチは次のとおりです

2つのアプローチを使用します。 2つのforループを使用する最初の素朴なアプローチ。 0が検出されたときに配列のトラバースを開始し、そのポイントから最後まで配列をトラバースし、1が検出されたときにカウントをインクリメントします。

• 0と1を含む配列arr[]を取ります。

• 関数count_cars（int arr []、int size）は、配列と長さを入力として受け取り、通過する車の数を返します。

• 初期カウントを0とします。

• 配列をインデックスi=0からiまでトラバースします。

• arr [i]が0の場合、配列をインデックスj =i+1からjまで再度トラバースします。

• 1インクリメントとしての各arr[j]について、ペア（arr [i]、arr [j]）は（0,1）およびiとしてカウントされます。

• 最後に、合計数を取得します。

• 結果としてカウントを返します。

効率的なアプローチ

このアプローチでは、配列を最後からトラバースします。最後からすべて1を数えます。 （最後から）最初の0ごとに、いいえ。ペアの数は、一時的な1のカウントになります。

• 0と1を含む配列arr[]を取ります。

• 関数count_cars（int arr []、int size）は、配列と長さを入力として受け取り、通過する車の数を返します。

• 初期カウントを0とします。

• サイズ>=1までwhileループを使用して配列を最後からトラバースします。

• arr [size-1]が1の場合、これまでに見つかった1の数だけ可変温度をインクリメントします。

• それ以外の場合は0です（これは、rempであるすべての1よりも低いインデックスを持っています）。ペアは一時的になります。 count =count+tempを設定します。

• 次の要素のサイズを減らします。

• 最後に、合計数を取得します。

• 結果としてカウントを返します。

例（素朴なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
   int count = 0;
   for (int i=0; i<size-1; i++){
      if(arr[i] == 0){
         for (int j=i+1; j<size; j++)
         if (arr[j]==1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {1, 1, 0, 0, 1};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of passing car pairs are: "<<count_cars(arr, size);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of passing car pairs are: 2

例（効率的なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
   int count = 0;
   int temp = 0;
   while (size >= 1){
      if (arr[size-1] == 1){
         temp++;
      }
      else{
         count = count + temp;
      }
      size--;
   }
   return count;
}
int main(){
   int arr[] = {1, 1, 0, 1, 1};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of passing car pairs are: "<<count_cars(arr, size);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of passing car pairs are: 2