Наибольшее целое число, которое можно поместить в центр заданной квадратной матрицы, чтобы максимизировать арифметическую прогрессию

Дана матрица N x N , в которой элемент с индексом [N/2, N/2] отсутствует, задача состоит в том, чтобы найти максимальное целое число, которое можно поместить с индексом [N/2, N/2] , такое что количество арифметических прогрессий по всем строкам, столбцам и диагоналям максимально.

Пример:

Input: mat[][]={{3, 4, 11}, {10, ?, 9}, {-1, 6, 7}}
Output: 5
Explanation: The maximum integer that can be placed on [1, 1] is 5. Hence, the AP’s formed is are:

1. Top left diagonal: 3, 5, 7.
2. Top right diagonal: −1, 5, 1.
3. Middle column: 4, 5, 6.
4. Right column: 11, 9, 7.

Therefore, the number of AP formed is 4 which is the maximum possible.

Input: mat[][]={{2, 2, 11}, {1, ?, 7}, {-1, 6, 6}}
Output: 4

Подход: Данную задачу можно решить, найдя все возможные числа, которые можно разместить в индексе [N/2, N/2] так, чтобы он образовывал арифметическую прогрессию по любой строке, столбцу или диагонали данной матрицы и отслеживание наибольшего целого числа из них, которое формирует максимальное количество AP .

Let’s suppose the matrix is of 3*3 size. 

Now, the missing element is (1, 1). 
So, for each row, column and diagonal, three numbers are present. Say, these three numbers are A, B, C and B is missing. 

So, it can be observed that for integers A, B, and C to form and an AP,  
B must be equal to [A + (C – A)]/2. 

Hence, for any value of A and C, B can be calculated using the above-discussed formula. Also, if (C – A) is odd then no integer value exists for B.

So, apply this formula to over row, column and diagonal and find the maximum element which will form the maximum element.

Тот же подход можно применить к матрице N*N .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)