นับเมทริกซ์ย่อยที่มีผลรวมหารด้วย 'k' ใน C++

รับเมทริกซ์แถว x col เป็นอินพุต เป้าหมายคือการหาเมทริกซ์ย่อยทั้งหมดภายในเมทริกซ์[row][col] เพื่อให้ผลรวมขององค์ประกอบของเมทริกซ์ย่อยนั้นหารด้วยจำนวนเต็ม k ลงตัว

หากเมทริกซ์เป็น mat[3][3] และ k คือ 4 เมทริกซ์ย่อยจะเป็นดังที่แสดงด้านล่าง:-

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

ตัวอย่าง

ป้อนข้อมูล - เมทริกซ์[3][3] ={ {1,1,1}, {2,2,2}, {3,3,3} } k=4

ผลลัพธ์ - จำนวนเมทริกซ์ย่อยที่มีผลรวมหารด้วย 'k' คือ 4

คำอธิบาย - เมทริกซ์ย่อยจะเป็นดังที่แสดงด้านบน

ป้อนข้อมูล - เมทริกซ์[3][3] ={ {1,1,1}, {2,2,2 }, {3,3,3} } k=12

ผลลัพธ์ - จำนวนเมทริกซ์ย่อยที่มีผลรวมหารด้วย 'k' คือ 4

คำอธิบาย - เมทริกซ์ย่อยจะเป็นดังนี้:-

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

ในแนวทางนี้ เราจะสำรวจเมทริกซ์จากซ้ายไปขวาและสำหรับคอลัมน์ซ้ายและขวาแต่ละคู่ ให้เพิ่มองค์ประกอบของเมทริกซ์ย่อยไปยังอาร์เรย์ arr[] และคำนวณผลรวมขององค์ประกอบและอาร์เรย์ย่อยที่ผลรวมหารด้วย k ลงตัว>

ฟังก์ชั่น check_val() รับอาร์เรย์ที่มีองค์ประกอบของเมทริกซ์ย่อยเป็นอาร์เรย์ 1D ตอนนี้คำนวณผลรวมสะสมและตรวจสอบส่วนที่เหลือด้วย k และความถี่การจัดเก็บของส่วนที่เหลือในอาร์เรย์ arr_2[]

• นำ matrix[row][col] และจำนวนเต็ม k เป็นอินพุต
• Function check_val(int arr[], int size, int k) รับ arr[] ของอิลิเมนต์ของเมทริกซ์ย่อยและคืนค่าจำนวนอาร์เรย์ย่อยทั้งหมดภายใน arr ที่ผลรวมหารด้วย k ลงตัว
• นับตัวแปรและอุณหภูมิเป็น 0
• ใช้อาร์เรย์ arr_2[] เพื่อเก็บความถี่ของเศษรวมสะสมด้วย k
• คำนวณผลรวมสะสมโดยใช้ for loop จาก i=0 ถึง i
• ใช้อีกครั้งสำหรับอาร์เรย์ความถี่การเคลื่อนที่แบบวนซ้ำ arr_2[] และสำหรับแต่ละค่า>1 เพิ่ม arr_2[i] * (arr_2[i] - 1)) / 2 เพื่อนับเป็นอาร์เรย์ย่อยทั้งหมดที่เป็นไปได้
• ในตอนท้ายให้เพิ่ม arr_2[0] เพื่อนับ
• Function matrix_divisible(int matrix[row][col], int size, int k) รับอินพุตเมทริกซ์ย่อยและคืนค่าการนับของเมทริกซ์ย่อยทั้งหมดที่มีผลรวมหารด้วย k ลงตัว
• นับเริ่มต้นเป็น 0
• ใช้อาร์เรย์ชั่วคราว arr[ขนาด].
• การใช้ two for loops กำหนดดัชนีคอลัมน์ด้านซ้าย i และดัชนีคอลัมน์ด้านขวา j.
• คำนวณผลรวมขององค์ประกอบเป็น arr[temp]+=matrix[temp][j].
• สำหรับจำนวนของอาร์เรย์ย่อยใน arr[] ให้เพิ่ม check_val(arr, size, k) ที่จะนับ
• เมื่อสิ้นสุดลูป ให้นับผลลัพธ์เป็นผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
#define row 10
#define col 10

int check_val(int arr[], int size, int k) {
   int count = 0;
   int temp = 0;
   int arr_2[k];
   memset(arr_2, 0, sizeof(arr_2));

   for (int i = 0; i < size; i++) {
      temp = temp + arr[i];
      arr_2[((temp % k) + k) % k]++;
   }
   for (int i = 0; i < k; i++) {
      if (arr_2[i] > 1) {
         count += (arr_2[i] * (arr_2[i] - 1)) / 2;
      }
   }
   count = count + arr_2[0];
   return count;
}

int matrix_divisible(int matrix[row][col], int size, int k) {
   int count = 0;
   int arr[size];

   for (int i = 0; i < size; i++) {
      memset(arr, 0, sizeof(arr));
      for (int j = i; j < size; j++) {
         for (int temp = 0; temp < size; ++temp) {
            arr[temp] += matrix[temp][j];
         }
         count = count + check_val(arr, size, k);
      }
   }
   return count;
}
int main() {
   int matrix[row][col] = {{2,4,-1},{6,1,-9},{2,2, 1}};
   int size = 3, k = 4;
   cout << "Count of sub-matrices having sum divisible ‘k’ are: " << matrix_divisible(matrix, size, k);
   return 0;
}

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

ผลลัพธ์

Count of sub-matrices having sum divisible 'k' are: 7