Maximum Number of Ones

Moderate
0/80
Average time to solve is 20m
7 upvotes
Asked in companies
AmazonMicrosoftFlipkart

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
1
2 2 1 1
Sample Output 1:
4
Explanation for sample input 1:
In a 2*2 matrix, each 1*1 sub-matrix can have at most 1 one. So, the best solution will be:
[1, 1]
[1, 1]
Sample Input 2:
1
3 3 2 0
Sample Output 2:
0
Explanation for sample input 2:
Each sub-matrix of dimensions 2*2 must have 0 ones. So, the matrix M must contain all entries to be 0:
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
Hint

Try to divide the matrix into non-overlapping sub-matrices.

Approaches (1)
Observation + Greedy
  • 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.
Time Complexity

O((N ^ 2) * log(N ^ 2)), where N * N is the dimensions of the sub-matrix.

 

We are creating an array of size N * N that contains all the subMatrix elements, and we are sorting this array. So, the time complexity will be O((N ^ 2) * log(N ^ 2)).

Space Complexity

O(N ^ 2), where N * N is the dimensions of the sub-matrix.

 

As we are creating an extra matrix and an array both of size N * N. Hence, the space complexity will be O(N ^ 2).

Code Solution
(100% EXP penalty)
Maximum Number of Ones
Full screen
Console