Generate a Matrix with imply of every subarray of every row as an integer

 

Given two integers M and N, the duty is to generate an MxN matrix having components in vary [1, MxN] such that the common of any subarray of any row is an integer. If it isn't doable to take action, return -1.

Examples:

Enter: M = 2, N = 3
Output:
1 3 5
2 4 6
Explaination: Subarrays of first row with dimension larger than 1 are {1, 3}, {3, 5}, {1, 3, 5}. Means are 2, 4 and three respectively.
Subarrays of 2nd row are with dimension larger than 1 are {2, 4}, {4, 6}, {2, 4, 6}. Means are 3, 5 and 4 respectively.

Enter: M = 1, N = 3
Output: -1
Explaination: All Doable preparations are: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}.
In each preparations there's a suarray whose imply is a decimal worth and never an integer.

Method: The answer to the method is predicated on the next mathematical remark:

• The dimensions of the subarray should divide the sum of the weather utterly for the imply to be an integral worth.
• The weather is pure numbers from 1 to M*N.
• The sum of first ‘n’ odd numbers is the same as n² and the sum of first ‘n’ even numbers is the same as n(n+1).

Now suppose from the first n odd components we discard 1st ok odd components and contemplate the remainder because the subarray then:

Whole numbers = n
Numbers discarded = ok
Numbers in subarray = n – ok
Sum of 1st n numbers =n²
Sum of 1st ok numbers =ok²
Due to this fact, sum of subarray = n² – ok²
=> imply = (n² – ok²)/(n – ok)
= (n + ok)*(n – ok)/(n – ok)
= (n + ok), which is an interger as each n and ok are intergers

Equally, suppose from the first n even components, discard 1st ok even components and contemplate the remainder because the subarray then:

Whole numbers = n
Numbers discarded = ok
Numbers in subarray = n – ok
Sum of 1st n numbers =n(n + 1)
Sum of 1st ok numbers =ok(ok + 1)
Due to this fact, sum of subarray = n(n + 1) – ok(ok + 1)
=> imply = (n(n + 1) – ok(ok + 1))/(n – ok)
= (n² + n – ok² – ok)/(n-k)
= (n² – ok²)/(n – ok) + (n-k)/(n-k)
= (n + ok)*(n – ok)/(n – ok) + 1
= (n + ok) + 1, which is an interger as each n and ok are intergers.

Observe the steps talked about under to implement the above remark:

• From the above remark, organized in such a fashion that every row has both all even numbers or all odd numbers.
• Test if there are equal numbers of weird and even numbers and the MxN should be even.
• If the variety of rows is odd then, a legitimate association isn't doable as a result of the odd, and even components can't be saved collectively. There'll at all times be at the very least one row having each odd and even component.

Under is the implementation of the above method.

C++

#embody <bits/stdc++.h> utilizing namespace std; void validArrangement(int M, int N) { if (N == 1) { for (int i = 1; i <= M; i++) cout << i << endl; return; } if (M % 2 == 1) { cout << -1 << endl; return; } else { for (int i = 1; i <= M; i++) { int num = i; for (int j = 1; j <= N; j++) { cout << num << " "; num += M; } cout << endl; } return; } } int predominant() { int M = 2, N = 3; validArrangement(M, N); return 0; }

Time Complexity: O(MxN)
Auxiliary Area: O(1)