Last Updated: 16 Apr, 2021

Maximum Number of Ones

Moderate

Asked in companies

Solve now

Problem statement

You are given a matrix ‘M’ having dimensions ‘WIDTH x ‘HEIGHT’ and provided with an integer ‘N’. The matrix ‘M’ can take only binary values, i.e., 0 and 1. Your task is to find the “maximum number of ones” that the matrix ‘M’ can have such that every square sub-matrix of M of dimensions ‘N’ x ‘N’ has no more than ‘MAXONES’ ones.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first and only line of each test case contains four positive integers, ‘WIDTH’, ‘HEIGHT’, ‘N’, and ‘MAXONES’, as described in the problem statement.

Output Format:

For each test case, print a single line containing a single integer denoting the maximum number of ones that the matrix M can have.

The output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 10
1 <= ‘WIDHT’, ‘HEIGHT’ <= 1000
1 <= ‘N’ <= WIDHT, HEIGHT
0 <= ‘MAXONES’ <= N * N

Where ‘T’ is the number of test cases, ‘WIDHT’ x ‘HEIGHT’ is the dimension of the matrix, ‘N’ * ‘N’ is the dimension of the square sub-matrix, and ‘MAXONES’ is the maximum number of ones a square sub-matrix can have.

Time Limit: 1sec.

Solve now

Approaches

01 Approach

The idea here is to divide the matrix M into the non-overlapping sub-matrices of dimensions ‘N’x’N’. The corners sub-matrices may have a smaller area if the dimensions of the matrix ‘M’ is not divisible by the ‘N’.
Now, consider any proper sub-matrix after division. If we can put maxOnes in it, then the remaining non-overlapping sub-matrices are just a copy of it. For, simplicity we can consider the top-left sub-matrix as the base matrix.
So, create a new matrix of dimensions N*N named subMatrix and fill ‘0’ in each cell.
Now, we try to map each cell (i, j) of the matrix ‘M’ to the top-left’s sub-matrix relative position, i.e., new-formed matrix subMatrix. We can use i % N to get the desired row and similarly j % N for the column. As discussed above, start putting 1s in all the relative positions.
To implement this, run a loop from i = 0 to i < height, in each iteration:
- Run a loop from j = 0 to j < width, in each iteration:
  - Increment subMatrix[i%N][j%N] by 1.
Now, we want only maxOnes in the top-left matrix, and the rest will automatically be taken care of with the help of subMatrix. So, in other words, we want maxOnes maximum entries of the matrix subMatrix.
To implement this, we can use an array of size N*N named temp, and add all the elements of the matrix subMatrix into the array temp.
Create a new variable ans, and initialize it with 0.
Sort the array temp in descending order.
Add starting maxOnes elements of the array temp in the ans.
Return the ans.

Solve now