นับอาร์เรย์ย่อยที่ประกอบด้วยเพียง 0 และ 1 เท่านั้นในอาร์เรย์ไบนารีใน C++

เราได้รับอาร์เรย์ arr[] ที่มี 0 และ 1 เท่านั้น เป้าหมายคือการนับอาร์เรย์ย่อยทั้งหมดของ arr[] โดยที่แต่ละ subarray มีเพียง 0 หรือ 1 เท่านั้นไม่ใช่ทั้งสองอย่าง หากอาร์เรย์เป็น [1,0,0] อาร์เรย์ย่อยจะเป็น 0 เท่านั้น [0], [0], [0,0] และสำหรับ 1 เท่านั้น [1].

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − arr[] ={ 0, 0, 1, 1, 1, 0 };

ผลผลิต − Subarray ที่มี 0 เท่านั้นคือ :4 Subarray ที่มี 1 ตัวเท่านั้นคือ :6

คำอธิบาย − Subaarays จะเป็น -

For all 0’s: [0], [0], [0], [0,0]. Total 4 ( arr[0], arr[1], arr[5], arr[0-1] )
For all 1’s: [1], [1], [1], [1,1], [1,1], [1,1,1]. Total 6 ( arr[2], arr[2], arr[4], arr[2-3], arr[3-4],
arr[2-4] )

ป้อนข้อมูล − arr[] ={ 1,0,1,0 };

ผลผลิต − Subarrays ที่มีเพียง 0 คือ :2 Subarray ที่มีเพียง 1 คือ :2

คำอธิบาย − Subaarays จะเป็น -

For all 0’s: [0], [0]. Total 2 ( arr[1], arr[3] )
For all 1’s: [1], [1]. Total 2 ( arr[0], arr[2] )

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

เราจะสำรวจอาร์เรย์สองครั้งเพื่อนับอาร์เรย์ย่อยที่แยกจากกันด้วย 0 และ 1 เท่านั้น ใช้ตัวนับสองตัว count_0 และ count_1 เพื่อเก็บจำนวน 0 และ 1 ที่ต่อเนื่องกันในอาร์เรย์ สำหรับการนับแต่ละครั้ง อาร์เรย์ย่อยที่เป็นไปได้จะเป็น count_0*(count_0+1)/2 และเช่นเดียวกันสำหรับ count_1

เพิ่มไปยังจำนวน Total_0 จนกว่าจะถึงจุดสิ้นสุดของอาร์เรย์ ทำขั้นตอนที่คล้ายกันสำหรับ 1

• หาอาร์เรย์ arr[] ของตัวเลข

• ฟังก์ชั่น sub_zero_one(int arr[], int size) รับอาร์เรย์และส่งกลับจำนวนอาร์เรย์ย่อยที่มีเพียง 0 และจำนวนอาร์เรย์ย่อยที่มีเพียง 1

• นับเริ่มต้นเป็น temp_0 และ temp_1 สำหรับอาร์เรย์ย่อย

• ใช้การนับต่อเนื่องกันชั่วคราวของ 0 และ 1 เป็น count_0 และ count_1

• เราจะสำรวจอาร์เรย์โดยใช้ for loop จาก i=0 ถึง I

• หากองค์ประกอบปัจจุบันเป็น 0 เพิ่มขึ้น count_0.

• หากไม่เป็นเช่นนั้น ให้คำนวณอาร์เรย์ย่อยที่เป็นไปได้ทั้งหมดด้วยจำนวน count_0 ของ 0 เป็น temp_one_0=count*(count+1)/2

• เพิ่มสิ่งนี้ใน temp_0 ก่อนหน้าสำหรับอาร์เรย์ย่อยที่พบทั้งหมด 0 จนถึงตอนนี้

• ทำกระบวนการที่คล้ายกันโดยใช้ for ลูปสำหรับ 1 โดยมีตัวแปรเป็น count_1, temp_one_1 และtemp_1

• เมื่อสิ้นสุดการสำรวจทั้งสอง temp_0 และ temp_1 จะนับอาร์เรย์ย่อยทั้งหมดภายใน arr ที่มี 0 ทั้งหมดและ 1 ทั้งหมด

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
void sub_zero_one(int arr[], int size){
   int count_1 = 0;
   int count_0 = 0;
   int temp_1 = 0;
   int temp_0 = 0;
   for (int i = 0; i < size; i++){
      if (arr[i] == 1){
         count_1++;
      }
      else{
         int temp_one_1 = (count_1) * (count_1 + 1) / 2;
         temp_1 = temp_1 + temp_one_1;
         count_1 = 0;
      }
   }
   for (int i = 0; i < size; i++){
      if (arr[i] == 0)
         { count_0++; }
      else{
         int temp_one_0 = (count_0) * (count_0 + 1) / 2;
         temp_0 = temp_0 + temp_one_0;
         count_0 = 0;
      }
   }
   if (count_1){
      int temp_one_1 = (count_1) * (count_1 + 1) / 2;
      temp_1 = temp_1 + temp_one_1;
   }
   if (count_0){
      int temp_one_0 = (count_0) * (count_0 + 1) / 2;
      temp_0 = temp_0 + temp_one_0;
   }
   cout<<"Subarrays with only 0's are : "<<temp_0;
   cout<<"\nSubarrays with only 1's are : "<<temp_1;
}
int main(){
   int arr[] = { 0, 0, 0, 1, 1, 0, 1};
   int size = sizeof(arr) / sizeof(arr[0]);
   sub_zero_one(arr, size);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Subarrays with only 0's are : 7
Subarrays with only 1's are : 4