Dada una array N x N , tal que falta el elemento en el índice [N/2, N/2] , la tarea es encontrar el entero máximo que se puede colocar en el índice [N/2, N/2] tal que se maximiza el recuento de progresiones aritméticas en todas las filas, columnas y diagonales.
Ejemplo:
Entrada: mat[][]={{3, 4, 11}, {10, ?, 9}, {-1, 6, 7}}
Salida: 5
Explicación: El entero máximo que se puede colocar en [1, 1] es 5. Por lo tanto, los AP formados son:
- Diagonal superior izquierda: 3, 5, 7.
- Diagonal superior derecha: −1, 5, 1.
- Columna central: 4, 5, 6.
- Columna derecha: 11, 9, 7.
Por lo tanto, el número de AP formados es 4 que es el máximo posible.
Entrada: mat[][]={{2, 2, 11}, {1, ?, 7}, {-1, 6, 6}}
Salida: 4
Enfoque: El problema dado se puede resolver encontrando todos los números posibles que se pueden colocar en el índice [N/2, N/2] de manera que forme una progresión aritmética sobre cualquier fila, columna o diagonal de la array dada y haciendo un seguimiento del número entero más grande de ellos que forma el máximo de AP .
Supongamos que la array tiene un tamaño de 3*3 .
Ahora, el elemento que falta es (1, 1) .
Entonces, para cada fila, columna y diagonal, hay tres números presentes. Digamos que estos tres números son A , B , C y falta B.Entonces, se puede observar que para que los números enteros A , B y C formen un AP,
B debe ser igual a [ A + (C – A)]/2 .Por lo tanto, para cualquier valor de A y C , B se puede calcular usando la fórmula discutida anteriormente. Además, si (C – A) es impar, entonces no existe un valor entero para B.
Entonces, aplique esta fórmula sobre fila, columna y diagonal y encuentre el elemento máximo que formará el elemento máximo.
El mismo enfoque se puede aplicar a la array N*N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum value
// of the missing integer such that the
// count of AP's formed is maximized
int findMissing(vector<vector<int> >& mat)
{
int N = mat.size();
// Stores the occurrence of each
// possible integer value
unordered_map<int, int> mp;
// For 1st Row
int t = abs(mat[N / 2][N / 2 + 1]
- mat[N / 2][N / 2 - 1]);
int A
= min(mat[N / 2][N / 2 + 1],
mat[N / 2][N / 2 - 1]);
if (t % 2 == 0) {
mp[A + t / 2] += 1;
}
// For 1st Col
t = abs(mat[N / 2 + 1][N / 2]
- mat[N / 2][N / 2]);
A = min(mat[N / 2 + 1][N / 2],
mat[N / 2][N / 2]);
if (t % 2 == 0) {
mp[A + t / 2] += 1;
}
// For Left Diagonal
t = abs(mat[N / 2 + 1][N / 2 + 1]
- mat[N / 2 - 1][N / 2 - 1]);
A = min(mat[N / 2 + 1][N / 2 + 1],
mat[N / 2 - 1][N / 2 - 1]);
if (t % 2 == 0) {
mp[A + t / 2] += 1;
}
// For Right Diagonal
t = abs(mat[N / 2 - 1][N / 2 + 1]
- mat[N / 2 + 1][N / 2 - 1]);
A = min(mat[N / 2 - 1][N / 2 + 1],
mat[N / 2 + 1][N / 2 - 1]);
if (t % 2 == 0) {
mp[A + t / 2] += 1;
}
int ans = -1, occur = 0;
// Loop to find the largest integer
// with maximum count
for (auto x : mp) {
if (occur < x.second) {
ans = x.first;
}
if (occur == x.second) {
ans = max(ans, x.first);
}
}
// Return Answer
return ans;
}
// Driver Code
int main()
{
vector<vector<int> > mat
= { { 3, 4, 11 },
{ 10, INT_MAX, 9 },
{ -1, 6, 7 } };
cout << findMissing(mat);
}
Java
// Java code for the above approach
import java.util.*;
class GFG
{
// Function to find the maximum value
// of the missing integer such that the
// count of AP's formed is maximized
static int findMissing(int[][] mat) {
int N = mat.length;
// Stores the occurrence of each
// possible integer value
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
// For 1st Row
int t = Math.abs(mat[N / 2][N / 2 + 1] - mat[N / 2][N / 2 - 1]);
int A = Math.min(mat[N / 2][N / 2 + 1], mat[N / 2][N / 2 - 1]);
if (t % 2 == 0) {
if (mp.containsKey(A + t / 2)) {
mp.put(A + t / 2, mp.get(A + t / 2) + 1);
} else {
mp.put(A + t / 2, 1);
}
}
// For 1st Col
t = Math.abs(mat[N / 2 + 1][N / 2] - mat[N / 2][N / 2]);
A = Math.min(mat[N / 2 + 1][N / 2], mat[N / 2][N / 2]);
if (t % 2 == 0) {
if (mp.containsKey(A + t / 2)) {
mp.put(A + t / 2, mp.get(A + t / 2) + 1);
} else {
mp.put(A + t / 2, 1);
}
}
// For Left Diagonal
t = Math.abs(mat[N / 2 + 1][N / 2 + 1] - mat[N / 2 - 1][N / 2 - 1]);
A = Math.min(mat[N / 2 + 1][N / 2 + 1], mat[N / 2 - 1][N / 2 - 1]);
if (t % 2 == 0) {
if (mp.containsKey(A + t / 2)) {
mp.put(A + t / 2, mp.get(A + t / 2) + 1);
} else {
mp.put(A + t / 2, 1);
}
}
// For Right Diagonal
t = Math.abs(mat[N / 2 - 1][N / 2 + 1] - mat[N / 2 + 1][N / 2 - 1]);
A = Math.min(mat[N / 2 - 1][N / 2 + 1], mat[N / 2 + 1][N / 2 - 1]);
if (t % 2 == 0) {
if (mp.containsKey(A + t / 2)) {
mp.put(A + t / 2, mp.get(A + t / 2) + 1);
} else {
mp.put(A + t / 2, 1);
}
}
int ans = -1, occur = 0;
// Loop to find the largest integer
// with maximum count
for (Map.Entry<Integer, Integer> x : mp.entrySet()) {
if (occur < x.getValue()) {
ans = x.getKey();
}
if (occur == x.getValue()) {
ans = Math.max(ans, x.getKey());
}
}
// Return Answer
return ans;
}
// Driver Code
public static void main(String[] args) {
int[][] mat = { { 3, 4, 11 }, { 10, Integer.MAX_VALUE, 9 }, { -1, 6, 7 } };
System.out.print(findMissing(mat));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 code for the above approach from collections import defaultdict import sys # Function to find the maximum value # of the missing integer such that the # count of AP's formed is maximized def findMissing(mat): N = len(mat) # Stores the occurrence of each # possible integer value mp = defaultdict(int) # For 1st Row t = abs(mat[N // 2][N // 2 + 1] - mat[N // 2][N // 2 - 1]) A = min(mat[N // 2][N // 2 + 1], mat[N // 2][N // 2 - 1]) if (t % 2 == 0): mp[A + t // 2] += 1 # For 1st Col t = abs(mat[N // 2 + 1][N // 2] - mat[N // 2][N // 2]) A = min(mat[N // 2 + 1][N // 2], mat[N // 2][N // 2]) if (t % 2 == 0): mp[A + t // 2] += 1 # For Left Diagonal t = abs(mat[N // 2 + 1][N // 2 + 1] - mat[N // 2 - 1][N // 2 - 1]) A = min(mat[N // 2 + 1][N // 2 + 1], mat[N // 2 - 1][N // 2 - 1]) if (t % 2 == 0): mp[A + t // 2] += 1 # For Right Diagonal t = abs(mat[N // 2 - 1][N // 2 + 1] - mat[N // 2 + 1][N // 2 - 1]) A = min(mat[N // 2 - 1][N // 2 + 1], mat[N // 2 + 1][N // 2 - 1]) if (t % 2 == 0): mp[A + t // 2] += 1 ans = -1 occur = 0 # Loop to find the largest integer # with maximum count for x in mp: if (occur < mp[x]): ans = x if (occur == mp[x]): ans = max(ans, x) # Return Answer return ans # Driver Code if __name__ == "__main__": mat = [[3, 4, 11], [10, sys.maxsize, 9], [-1, 6, 7]] print(findMissing(mat)) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int INT_MAX = 2147483647;
// Function to find the maximum value
// of the missing integer such that the
// count of AP's formed is maximized
static int findMissing(int [,]mat)
{
int N = mat.GetLength(0);
// Stores the occurrence of each
// possible integer value
Dictionary<int, int> mp =
new Dictionary<int, int>();
// For 1st Row
int t = Math.Abs(mat[N / 2, N / 2 + 1]
- mat[N / 2, N / 2 - 1]);
int A
= Math.Min(mat[N / 2, N / 2 + 1],
mat[N / 2, N / 2 - 1]);
if (t % 2 == 0) {
if (mp.ContainsKey(A + t / 2))
{
mp[A + t / 2] = mp[A + t / 2] + 1;
}
else
{
mp.Add(A + t / 2, 1);
}
}
// For 1st Col
t = Math.Abs(mat[N / 2 + 1, N / 2]
- mat[N / 2, N / 2]);
A = Math.Min(mat[N / 2 + 1, N / 2],
mat[N / 2, N / 2]);
if (t % 2 == 0) {
if (mp.ContainsKey(A + t / 2))
{
mp[A + t / 2] = mp[A + t / 2] + 1;
}
else
{
mp.Add(A + t / 2, 1);
}
}
// For Left Diagonal
t = Math.Abs(mat[N / 2 + 1, N / 2 + 1]
- mat[N / 2 - 1, N / 2 - 1]);
A = Math.Min(mat[N / 2 + 1, N / 2 + 1],
mat[N / 2 - 1, N / 2 - 1]);
if (t % 2 == 0) {
if (mp.ContainsKey(A + t / 2))
{
mp[A + t / 2] = mp[A + t / 2] + 1;
}
else
{
mp.Add(A + t / 2, 1);
}
}
// For Right Diagonal
t = Math.Abs(mat[N / 2 - 1, N / 2 + 1]
- mat[N / 2 + 1, N / 2 - 1]);
A = Math.Min(mat[N / 2 - 1, N / 2 + 1],
mat[N / 2 + 1, N / 2 - 1]);
if (t % 2 == 0) {
if (mp.ContainsKey(A + t / 2))
{
mp[A + t / 2] = mp[A + t / 2] + 1;
}
else
{
mp.Add(A + t / 2, 1);
}
}
int ans = -1, occur = 0;
// Loop to find the largest integer
// with maximum count
foreach(KeyValuePair<int, int> x in mp)
{
if (occur < x.Value) {
ans = x.Key;
}
if (occur == x.Value) {
ans = Math.Max(ans, x.Value);
}
}
// Return Answer
return ans;
}
// Driver Code
public static void Main()
{
int [,]mat
= { { 3, 4, 11 },
{ 10, INT_MAX, 9 },
{ -1, 6, 7 } };
Console.Write(findMissing(mat));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the maximum value
// of the missing integer such that the
// count of AP's formed is maximized
function findMissing(mat)
{
let N = mat.length;
// Stores the occurrence of each
// possible integer value
let mp = new Map();
// For 1st Row
let t = Math.abs(mat[Math.floor(N / 2)][Math.floor(N / 2) + 1]
- mat[Math.floor(N / 2)][Math.floor(N / 2) - 1]);
let A
= Math.min(mat[Math.floor(N / 2)][Math.floor(N / 2) + 1],
mat[Math.floor(N / 2)][Math.floor(N / 2) - 1]);
if (t % 2 == 0) {
if (mp.has(A + Math.floor(t / 2)))
mp.set(A + Math.floor(t / 2), mp.get(A + Math.floor(t / 2)) + 1);
else
mp.set(A + Math.floor(t / 2), 1);
}
// For 1st Col
t = Math.abs(mat[Math.floor(N / 2) + 1][Math.floor(N / 2)]
- mat[Math.floor(N / 2)][Math.floor(N / 2)]);
A = Math.min(mat[Math.floor(N / 2) + 1][Math.floor(N / 2)],
mat[Math.floor(N / 2)][Math.floor(N / 2)]);
if (t % 2 == 0) {
if (mp.has(A + Math.floor(t / 2)))
mp.set(A + Math.floor(t / 2), mp.get(A + Math.floor(t / 2)) + 1);
else
mp.set(A + Math.floor(t / 2), 1);
}
// For Left Diagonal
t = Math.abs(mat[Math.floor(N / 2) + 1][Math.floor(N / 2) + 1]
- mat[Math.floor(N / 2) - 1][Math.floor(N / 2) - 1]);
A = Math.min(mat[Math.floor(N / 2) + 1][Math.floor(N / 2) + 1],
mat[Math.floor(N / 2) - 1][Math.floor(N / 2) - 1]);
if (t % 2 == 0) {
if (mp.has(A + Math.floor(t / 2)))
mp.set(A + Math.floor(t / 2), mp.get(A + Math.floor(t / 2)) + 1);
else
mp.set(A + Math.floor(t / 2), 1);
}
// For Right Diagonal
t = Math.abs(mat[Math.floor(N / 2) - 1][Math.floor(N / 2) + 1]
- mat[Math.floor(N / 2) + 1][Math.floor(N / 2) - 1]);
A = Math.min(mat[Math.floor(N / 2) - 1][Math.floor(N / 2) + 1],
mat[Math.floor(N / 2) + 1][Math.floor(N / 2) - 1]);
if (t % 2 == 0) {
if (mp.has(A + Math.floor(t / 2)))
mp.set(A + Math.floor(t / 2), mp.get(A + Math.floor(t / 2)) + 1);
else
mp.set(A + Math.floor(t / 2), 1);
}
let ans = -1, occur = 0;
// Loop to find the largest integer
// with maximum count
for (let [key, val] of mp) {
if (occur < val) {
ans = key;
}
if (occur == val) {
ans = Math.max(ans, key);
}
}
// Return Answer
return ans;
}
// Driver Code
let mat = [[3, 4, 11],
[10, Number.MAX_VALUE, 9],
[-1, 6, 7]];
document.write(findMissing(mat))
// This code is contributed by Potta Lokesh
</script>
Producción
5
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kritirikhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA