กำหนดเมทริกซ์ row x col เป็นอินพุต เป้าหมายคือหา submatrices ทั้งหมดภายใน matrix[row][col] ที่ผลรวมของสมาชิกของ submatrix นั้นหารด้วยจำนวนเต็ม k ลงตัว
ถ้าเมทริกซ์คือ mat[3][3] และ k คือ 4 submatrices จะเป็นดังแสดงด้านล่าง:-
ทำความเข้าใจด้วยตัวอย่าง
ตัวอย่าง
Input - matrix[3][3] = { {1,1,1}, {2,2,2}, {3,3,3} } k = 4
Output - จำนวน sub-matrices ที่ผลรวมหารด้วย 'k' ลงตัวคือ: 4
คำอธิบาย - Submatrices จะเป็นดังแสดงข้างต้น
Input - matrix[3][3] = { {1,1,1}, {2,2,2}, {3,3,3} } k = 12
Output - จำนวน sub-matrices ที่ผลรวมหารด้วย 'k' ลงตัวคือ: 4
คำอธิบาย - Submatrices จะเป็นดังแสดงด้านล่าง:-
แนวทางที่ใช้ในโปรแกรมด้านล่าง
ในแนวทางนี้ เราจะเดินทางผ่านเมทริกซ์จากซ้ายไปขวา และสำหรับแต่ละคู่ของคอลัมน์ซ้ายและขวา เพิ่มสมาชิกของ submatrix เข้าไปในอาร์เรย์ arr[] และคำนวณผลรวมของสมาชิกและ subarrays ที่มีผลรวมหารด้วย k ลงตัวแยกต่างหาก
ฟังก์ชัน check_val() รับอาร์เรย์ที่มีสมาชิกของ submatrix เป็นอาร์เรย์ 1D ตอนนี้คำนวณผลรวมสะสมและตรวจสอบเศษกับ k และเก็บความถี่ของเศษในอาร์เรย์ arr_2[]
- รับ matrix[row][col] และจำนวนเต็ม k เป็นอินพุต
- ฟังก์ชัน check_val(int arr[], int size, int k) รับ arr[] ของสมาชิก submatrices และคืนค่าจำนวน subarrays ทั้งหมดภายใน arr ที่มีผลรวมหารด้วย k ลงตัว
- รับตัวแปร count และ temp เป็น 0
- รับอาร์เรย์ arr_2[] สำหรับเก็บความถี่ของเศษของผลรวมสะสมกับ k
- คำนวณผลรวมสะสมด้วย for loop จาก i = 0 ถึง i < size บวก arr[i] เข้า temp และเพิ่มความถี่ของเศษด้วย arr_2[((temp % k) + k) % k]++ (สำหรับผลรวมลบ ใช้ mod สองครั้ง)
- อีกครั้งใช้ for loop เดินทางผ่านอาร์เรย์ความถี่ arr_2[] และสำหรับค่าแต่ละค่า > 1 บวก arr_2[i] * (arr_2[i] - 1)) / 2 เข้า count เป็นจำนวน subarrays ทั้งหมดที่เป็นไปได้
- ในที่สุดบวก arr_2[0] เข้า count
- ฟังก์ชัน matrix_divisible(int matrix[row][col], int size, int k) รับ submatrix อินพุตและคืนค่าจำนวน submatrices ทั้งหมดที่มีผลรวมหารด้วย k ลงตัว
- รับ count เริ่มต้นเป็น 0
- รับอาร์เรย์ชั่วคราว arr[size]
- ใช้ for loop สองลูป ตั้งดัชนีคอลัมน์ซ้าย i และคอลัมน์ขวา j
- คำนวณผลรวมของสมาชิกเป็น arr[temp] += matrix[temp][j]
- สำหรับจำนวน subarrays ใน arr[] บวก check_val(arr, size, k) เข้า count
- ในท้ายที่สุดของ for loops ทั้งหมด คืนค่า count เป็นผลลัพธ์
ตัวอย่าง
#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
