Maximum number of ones in a N*N matrix with given constraints in C++

Given the task is to find the maximum number of ones in a binary matrix possible with the following constraints.

Two integers N and X are given where X<=N. The size of the binary matrix should be N*N and every sub-matrix of size X*X should contain at least one zero.

Let’s now understand what we have to do using an example −

Input − N=4, X=2

Output − 12

Explanation − The resultant matrix will be −

1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1

Input − N=7, X=3

Output − 45

Approach used in the below program as follows

• To obtain the maximum number of ones, first we will have to find the minimum number of zeros required in the given matrix.

  By observing a common pattern in all the matrices, it can be seen that the number of zeroes required = (N / X)²

  So the maximum number of ones = Total elements in matrix – number of zeros\

• In function MaxOne() create a variable Z of type int and store in it the minimum number of zeros required which is equal to (N / X)²

• Then initialize another variable total = N*N of type int to store the total size of the matrix.

• Then finally initialize int ans = total – Z to store the final answer and return ans.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int MaxOne(int N, int X){    // Minimum number of zeroes that are needed    int Z = (N / X);    Z = Z * Z;    /* Totol elements in matrix = square of the size of the matrices*/    int total =N * N;    //Final answer    int ans = total - Z;    return ans; } int main(){    int N = 4;    int X = 2;    cout << MaxOne(N, X);    return 0; }

Output

If we run the above code we will get the following output −

12