นับอาร์เรย์ย่อยที่มีองค์ประกอบคู่และคี่เหมือนกันใน C++

เราได้รับอาร์เรย์ของจำนวนเต็มบวก เป้าหมายคือการค้นหาอาร์เรย์ย่อยของตัวเลขในอาร์เรย์ โดยที่แต่ละอาร์เรย์ย่อยมีจำนวนองค์ประกอบคู่และคี่เท่ากัน ถ้าอาร์เรย์เป็น { 1,2,3,4 } จากนั้นอาร์เรย์ย่อยจะเป็น {1,2}, {2,3}, {3,4}, {1,2,3,4} จำนวนอาร์เรย์ย่อยดังกล่าวคือ 4

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

ป้อนข้อมูล − arr[] ={1,3,5,7,8,3,2 };

ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีองค์ประกอบคู่และคี่เท่ากันคือ − 4

คำอธิบาย − อาร์เรย์ย่อยจะเป็น − { 7,8 }, {8,3} {3,2}, {7,8,3,2}

ป้อนข้อมูล − arr[] ={2,4,6 };

ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีองค์ประกอบคู่และคี่เท่ากันคือ − 0

คำอธิบาย − องค์ประกอบทั้งหมดเท่ากัน

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

ในแนวทางนี้ เราจะใช้ตัวแปร temp เป็นค่าความแตกต่างระหว่างองค์ประกอบอาร์เรย์ (เริ่มแรก 0) และเพิ่มขึ้น 1 ถ้า arr[i] เป็นเลขคี่ และลดค่าลง 1 ถ้า arr[i] เป็นเลขคู่ เมื่อค่าของ temp เกิดขึ้นซ้ำแล้วซ้ำอีก จะต้องมีอาร์เรย์ย่อยที่มีจำนวนเลขคู่คี่เท่ากันระหว่างดัชนีเหล่านี้ อุณหภูมิสามารถเป็นบวกและลบได้ ใช้อาร์เรย์แฮชสองตัว arr_1[size+1] สำหรับความถี่ของความแตกต่างเชิงบวก และ arr_2[size+1] สำหรับความถี่ของความแตกต่างเชิงลบ

สำหรับแต่ละความแตกต่าง temp<0 เพิ่มความถี่จาก arr_1[-temp] เพื่อนับ [ -(-temp) ] ให้ดัชนีบวก

สำหรับแต่ละความแตกต่าง temp> 0 เพิ่มความถี่จาก arr_2[temp] เพื่อนับ เนื่องจากค่าความแตกต่างเดียวกันที่เกิดขึ้นทั้งหมดจะเป็นส่วนหนึ่งของอาร์เรย์ย่อย อัปเดตความถี่เหล่านี้ทีละ 1

Arr[] = { 1,3,5,7,8,3,2 }

ค่าอุณหภูมิเริ่มต้นจาก 0 -

1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } //all differences are positive
arr_2[] { 0,0,0,0,0,0,0,0 } //no difference is negative
Adding arr_1[temp] to count in each iteration gives count=4.

อาร์เรย์ย่อยคือ − { 7,8 }, {8,3} {3,2}, {7,8,3,2}

• ใช้อาร์เรย์เริ่มต้นเป็น arr[].

• ฟังก์ชัน Sub_even_odd(int arr[], int size) ใช้อาร์เรย์และความยาวและส่งคืนจำนวนอาร์เรย์ย่อยที่มีองค์ประกอบคู่และคี่เหมือนกัน

• ใช้การนับเริ่มต้นเป็น 0 และตัวแปร temp เป็นตัวแปรที่จะเพิ่มขึ้นเมื่อพบค่าคี่และลดค่าเมื่อพบค่าคู่

• ใช้สองอาร์เรย์ arr_1[] และ arr_2[] เพื่อเก็บความถี่ของอุณหภูมิ arr_1[] สำหรับค่าบวกของ temp ซึ่งสามารถสูงถึง size+1 ในกรณีที่อาร์เรย์ทั้งหมดมีค่าเท่ากัน

  arr_2[] สำหรับค่าลบของ temp ซึ่งสามารถสูงถึง size+1 ในกรณีที่อาร์เรย์ทั้งหมดมีค่าเท่ากัน

• Traverse arr[] ใช้สำหรับวนซ้ำ

• ถ้า arr[i] &1==1 แสดงว่า arr[i] เป็นเลขคี่ อุณหภูมิที่เพิ่มขึ้น ลดอุณหภูมิอย่างอื่น

• หาก temp<0 ให้เพิ่มความถี่ที่สอดคล้องกันจาก arr_2[] เพื่อนับ เพิ่มความถี่นั้นขึ้น 1

• หาก temp> 0 ให้เพิ่มความถี่ที่สอดคล้องกันจาก arr_1[] เพื่อนับ เพิ่มความถี่นั้นขึ้น 1

• ในท้ายที่สุด เราได้นับเป็นจำนวนของอาร์เรย์ย่อยใน arr[] ที่มีจำนวนองค์ประกอบคู่และคี่เท่ากัน

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int Sub_even_odd(int arr[], int size){
   int count = 0;
   int temp = 0;
   int arr_1[size + 1] = {0};
   int arr_2[size + 1] = {0};
   arr_1[0] = 1;
   for (int i = 0; i < size; i++){
      if(arr[i] & 1 == 1)
         { temp++; }
      else
         { temp--; }
      if (temp < 0){
         count += arr_2[-temp];
         arr_2[-temp]++;
      }
      else{
         count += arr_1[temp];
         arr_1[temp]++;
      }
   }
   return count;
}
int main(){
   int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subarrays with same even and odd elements are: "<<Sub_even_odd(arr,
size);
   return 0;
}

ผลลัพธ์

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

Count of subarrays with same even and odd elements are: 4