|
Given a binary matrix mat[][] with dimensions m * n, and any square sub-matrix of mat of size len * len has at most k ones. The task is to return the maximum possible number of ones that the matrix mat can have.
Example:
Input: m = 3, n = 3, len = 2, k = 1
Output: 4
Explanation: In a 3*3 matrix, no 2*2 sub-matrix can have more than 1 one.
The best solution that has 4 ones is:
[1,0,1]
[0,0,0]
[1,0,1]
Input: m = 3, n = 3, len = 2, k = 2
Output: 6
Explanation:
[1,0,1]
[1,0,1]
[1,0,1]
Approach:
The idea is based on following points:
- Get number of non-overlapping squares from grid
- Get remainders on the bottom (wr) and right side (hr)
- Count ones from full squares
- Greedily fill the remaining corner
- Greedily fill the bottom and right side in the order of most greed
Steps-by-step approach:
- Calculate the number of full squares horizontally and vertically:
- Calculate the remaining m and n after the full squares:
- Calculate the maximum number of ones from the full squares:
- Handle the corner squares (partially overlapping edges):
- corner = wr * hr
- res += min(corner, k) * (w + h + 1)
- k -= min(corner, k)
- Handle the bottom and right sides (partially filled squares):
- bottom = wr * (len – hr)
- right = hr * (len – wr)
- Determine the filling order based on the m and n:
- If w > h, fill the right side first, then the bottom.
- If h >= w, fill the bottom first, then the right side.
- res += min(right, k) * w
- k -= min(right, k)
- res += min(bottom, k) * h
- Return the final result (res).
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the maximum number of ones in a
// matrix with constraints
int maximumNumberOfOnes(int m, int n, int len, int k)
{
// Number of full squares horizontally
int w = m / len;
// Number of full squares vertically
int h = n / len;
// Remaining m after full squares
int wr = m % len;
// Remaining n after full squares
int hr = n % len;
// Maximum ones from full squares
int res = w * h * k;
// Handle corner squares (partially overlapping edges)
int count = k;
int corner = wr * hr;
// Add ones based on corner size and remaining count
res += min(corner, count) * (w + h + 1);
// Update remaining count
count -= min(corner, count);
// Handle bottom and right sides (partially filled
// squares)
int bottom = wr * (len - hr);
int right = hr * (len - wr);
// Check if m is greater than n to determine
// filling order
if (w > h) {
// Add ones to the right side based on count and
// remaining m
res += min(right, count) * w;
count -= min(right, count);
// Add remaining ones to the bottom
return res += min(bottom, count) * h;
}
else {
// Add ones to the bottom based on count and
// remaining n
res += min(bottom, count) * h;
count -= min(bottom, count);
// Add remaining ones to the right side
return res += min(right, count) * w;
}
}
// Driver code
int main()
{
int m = 3, n = 3, len = 2, k = 1;
int max_ones = maximumNumberOfOnes(m, n, len, k);
cout << "The maximum number of ones in the matrix is: "
<< max_ones << endl;
return 0;
}
import java.util.*;
public class MaximumNumberOfOnes {
// Function to calculate the maximum number of ones in a
// matrix with constraints
static int maximumNumberOfOnes(int m, int n, int len,
int k)
{
// Number of full squares horizontally
int w = m / len;
// Number of full squares vertically
int h = n / len;
// Remaining m after full squares
int wr = m % len;
// Remaining n after full squares
int hr = n % len;
// Maximum ones from full squares
int res = w * h * k;
// Handle corner squares (partially overlapping
// edges)
int count = k;
int corner = wr * hr;
// Add ones based on corner size and remaining count
res += Math.min(corner, count) * (w + h + 1);
// Update remaining count
count -= Math.min(corner, count);
// Handle bottom and right sides (partially filled
// squares)
int bottom = wr * (len - hr);
int right = hr * (len - wr);
// Check if m is greater than n to determine
// filling order
if (w > h) {
// Add ones to the right side based on count and
// remaining m
res += Math.min(right, count) * w;
count -= Math.min(right, count);
// Add remaining ones to the bottom
return res + Math.min(bottom, count) * h;
}
else {
// Add ones to the bottom based on count and
// remaining n
res += Math.min(bottom, count) * h;
count -= Math.min(bottom, count);
// Add remaining ones to the right side
return res + Math.min(right, count) * w;
}
}
// Driver code
public static void main(String[] args)
{
int m = 3, n = 3, len = 2, k = 1;
int maxOnes = maximumNumberOfOnes(m, n, len, k);
System.out.println(
"The maximum number of ones in the matrix is: "
+ maxOnes);
}
}
// This code is contributed by Akshita
def maximum_number_of_ones(m, n, length, k):
# Number of full squares horizontally
w = m // length
# Number of full squares vertically
h = n // length
# Remaining m after full squares
wr = m % length
# Remaining n after full squares
hr = n % length
# Maximum ones from full squares
res = w * h * k
# Handle corner squares (partially overlapping edges)
count = k
corner = wr * hr
# Add ones based on corner size and remaining count
res += min(corner, count) * (w + h + 1)
# Update remaining count
count -= min(corner, count)
# Handle bottom and right sides (partially filled squares)
bottom = wr * (length - hr)
right = hr * (length - wr)
# Check if m is greater than n to determine filling order
if w > h:
# Add ones to the right side based on count and remaining m
res += min(right, count) * w
count -= min(right, count)
# Add remaining ones to the bottom
return res + min(bottom, count) * h
else:
# Add ones to the bottom based on count and remaining n
res += min(bottom, count) * h
count -= min(bottom, count)
# Add remaining ones to the right side
return res + min(right, count) * w
# Driver code
if __name__ == "__main__":
m, n, length, k = 3, 3, 2, 1
max_ones = maximum_number_of_ones(m, n, length, k)
print("The maximum number of ones in the matrix is:", max_ones)
function maximumNumberOfOnes(m, n, len, k) {
// Number of full squares horizontally
const w = Math.floor(m / len);
// Number of full squares vertically
const h = Math.floor(n / len);
// Remaining m after full squares
const wr = m % len;
// Remaining n after full squares
const hr = n % len;
// Maximum ones from full squares
let res = w * h * k;
// Handle corner squares (partially overlapping edges)
let count = k;
const corner = wr * hr;
// Add ones based on corner size and remaining count
res += Math.min(corner, count) * (w + h + 1);
// Update remaining count
count -= Math.min(corner, count);
// Handle bottom and right sides (partially filled squares)
const bottom = wr * (len - hr);
const right = hr * (len - wr);
// Check if m is greater than n to determine filling order
if (w > h) {
// Add ones to the right side based on count and remaining m
res += Math.min(right, count) * w;
count -= Math.min(right, count);
// Add remaining ones to the bottom
return res + Math.min(bottom, count) * h;
} else {
// Add ones to the bottom based on count and remaining n
res += Math.min(bottom, count) * h;
count -= Math.min(bottom, count);
// Add remaining ones to the right side
return res + Math.min(right, count) * w;
}
}
// Driver code
const m = 3, n = 3, len = 2, k = 1;
const maxOnes = maximumNumberOfOnes(m, n, len, k);
console.log("The maximum number of ones in the matrix is: " + maxOnes);
OutputThe maximum number of ones in the matrix is: 4
Time complexity: O(1)
Auxiliary Space: O(1)
|
