Maximum Number of Ones in C++

Suppose we have a matrix M with dimensions w x h, such that every cell has value 0 or 1, and any square sub-matrix of M of size l x l has at most maxOnes number of ones. We have to find the maximum possible number of ones that the matrix M can have.

So, if the input is like w = 3, h = 3, l = 2, maxOnes = 1, then the output will be 4 as in a 3*3 matrix, no 2*2 sub-matrix can have more than 1 one. The best solution that has 4 ones is −

To solve this, we will follow these steps −

• ret := 0

• make one 2D array sq of size n x n

• for initialize i := 0, when i < height, update (increase i by 1), do −

  • for initialize j := 0, when j < width, update (increase j by 1), do −

    • increase sq[i mod n, j mod n] by 1

• Define an array v

• for initialize i := 0, when i < n, update (increase i by 1), do −

  • for initialize j := 0, when j < n, update (increase j by 1), do −

    • insert sq[i, j] at the end of v

• sort the array v in reverse order

• for initialize i := 0, j := 0, when i < size of v and j < maxOnes, update (increase i by 1), (increase j by 1), do −

• return ret

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {       int ret = 0;       vector < vector <int> > sq(n, vector <int>(n));       for(int i = 0; i < height; i++){          for(int j = 0; j < width; j++){             sq[i % n][j % n]++;          }       }       vector <int> v;       for(int i = 0; i < n; i++){          for(int j = 0; j < n ; j++){             v.push_back(sq[i][j]);          }       }       sort(v.rbegin(), v.rend());       for(int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++){          ret += v[i];       }       return ret;    } }; main(){    Solution ob;    cout << (ob.maximumNumberOfOnes(3,3,2,1)); }

Input

3, 3, 2, 1

Output

4