How to find entry of each a(i, j) in n*n matrix where n<=900 and a(i,j)=0 or a(i, j)=1?

Question

Suppose i have given n basically n*n matrix with all zero's at start.

And sum's associated with each row and column is given.

eg. n=4

Matrix:

0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0

given rows sum : 2, 2, 1, 1

given columns sum: 2, 0, 2, 2

So output matrix should look like:

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

There's always a solution exist. So for n=4, 0<=rowsum<=4 and 0<=columnsum<=4

Answer 1

You can solve this with a greedy approach.

while not filled:
    find biggest unfilled row:
        fill in putting 1s in columns with largest sums

In your case you started with:

    2 2 0 2
  ----------
2 | _ _ _ _
2 | _ _ _ _
1 | _ _ _ _
1 | _ _ _ _

Filling in one of the rows we get:

    1 1 0 2
  ----------
2 | _ _ _ _
  | 1 1 0 0
1 | _ _ _ _
1 | _ _ _ _

Fill in another:

      1   1
  ----------
  | 1 0 0 1
  | 1 1 0 0
1 | _ _ _ _
1 | _ _ _ _

And the other two can be filled in similarly:

  ----------
  | 1 0 0 1
  | 1 1 0 0
  | 0 1 0 0
  | 0 0 0 1

Assuming that the sum of the row values matches the sum of the column values, and 0 <= value <= n for all of them, this procedure will always work.

---

UPDATE: As pointed out in the comments, it is possible for no solution to exist in other ways. That will be detectable by the fact that you try to fill in a row and there aren't enough columns left to fill it with.

However if you run into such a barrier, then there was no solution.