Dada una array N x M mat[][] donde todos los elementos son números naturales a partir de 1 y son continuos excepto 1 elemento, encuentre ese elemento.
Ejemplos :
Entrada : mat[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 11, 12, 13}}
N = 3, M = 4
Salida : 10
Explicación : El número que falta es 10 en la fila n.° 3.Entrada : mat[][] = {{1, 2, 3},
{5, 6, 7},
{8, 9, 10}}
N = 3, M = 3
Salida : 4
Enfoque : el problema se puede resolver comprobando los múltiplos de M en el último elemento de cada fila de la array; si no coincide, el elemento que falta está en esa fila. Aplica la búsqueda lineal y encuéntralo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
#define Max 1000
// Function to return Missing
// Element from matrix Mat
int check(int Mat[][Max], int N, int M)
{
// Edge Case
if (Mat[0][0] != 1)
return 1;
// Initialize last element of
// first row
int X = Mat[0][0] + M - 1;
for (int i = 0; i < N; i++) {
// If last element of respective row
// matches respective multiples of X
if (Mat[i][M - 1] == X)
X = X + M;
// Else missing element
// is in that row
else {
// Initializing first element
// of the row
int Y = X - M + 1;
// Initializing column index
int j = 0;
// Linear Search
while (Y <= X) {
if (Mat[i][j] == Y) {
Y++;
j++;
}
else
return Y;
}
}
}
}
// Driver Code
int main()
{
int N = 3;
int M = 4;
int Mat[][Max] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 11, 12, 13 } };
cout << check(Mat, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to return Missing
// Element from matrix Mat
static int check(int Mat[][], int N, int M)
{
// Edge Case
if (Mat[0][0] != 1)
return 1;
// Initialize last element of
// first row
int X = Mat[0][0] + M - 1;
for (int i = 0; i < N; i++) {
// If last element of respective row
// matches respective multiples of X
if (Mat[i][M - 1] == X)
X = X + M;
// Else missing element
// is in that row
else {
// Initializing first element
// of the row
int Y = X - M + 1;
// Initializing column index
int j = 0;
// Linear Search
while (Y <= X) {
if (Mat[i][j] == Y) {
Y++;
j++;
}
else
return Y;
}
}
}
return 0;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
int M = 4;
int Mat[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 11, 12, 13 } };
System.out.print(check(Mat, N, M));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 program for the above approach # Function to return Missing # Element from matrix Mat def check(Mat, N, M): # Edge Case if (Mat[0][0] != 1): return 1 # Initialize last element of # first row X = Mat[0][0] + M - 1; for i in range(N): # If last element of respective row # matches respective multiples of X if (Mat[i][M - 1] == X): X = X + M # Else missing element # is in that row else: # Initializing first element # of the row Y = X - M + 1 # Initializing column index j = 0; # Linear Search while (Y <= X): if (Mat[i][j] == Y): Y = Y + 1 j = j + 1 else: return Y # Driver Code if __name__ == "__main__": N, M = 3, 4 Mat = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 11, 12, 13]] ans = check(Mat, N, M) print(ans) # This code is contributed by Abhishek Thakur.
C#
// C# program for the above approach
using System;
class GFG {
// Function to return Missing
// Element from matrix Mat
static int check(int [,] Mat, int N, int M)
{
// Edge Case
if (Mat[0, 0] != 1)
return 1;
// Initialize last element of
// first row
int X = Mat[0, 0] + M - 1;
for (int i = 0; i < N; i++) {
// If last element of respective row
// matches respective multiples of X
if (Mat[i, M - 1] == X)
X = X + M;
// Else missing element
// is in that row
else {
// Initializing first element
// of the row
int Y = X - M + 1;
// Initializing column index
int j = 0;
// Linear Search
while (Y <= X) {
if (Mat[i, j] == Y) {
Y++;
j++;
}
else
return Y;
}
}
}
return 0;
}
// Driver Code
public static void Main()
{
int N = 3;
int M = 4;
int[, ] Mat = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 11, 12, 13 } };
Console.Write(check(Mat, N, M));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
let Max = 1000
// Function to return Missing
// Element from matrix Mat
function check(Mat, N, M) {
// Edge Case
if (Mat[0][0] != 1)
return 1;
// Initialize last element of
// first row
let X = Mat[0][0] + M - 1;
for (let i = 0; i < N; i++) {
// If last element of respective row
// matches respective multiples of X
if (Mat[i][M - 1] == X)
X = X + M;
// Else missing element
// is in that row
else {
// Initializing first element
// of the row
let Y = X - M + 1;
// Initializing column index
let j = 0;
// Linear Search
while (Y <= X) {
if (Mat[i][j] == Y) {
Y++;
j++;
}
else
return Y;
}
}
}
}
// Driver Code
let N = 3;
let M = 4;
let Mat = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 11, 12, 13]];
document.write(check(Mat, N, M));
// This code is contributed by Potta Lokesh
</script>
Producción
10
Complejidad de Tiempo : O(N + M)
Espacio Auxiliar : O(1)
Enfoque eficiente : el enfoque eficiente consiste en comprobar los múltiplos del último elemento de las filas mediante un algoritmo de búsqueda binaria . Si no coincide, el elemento que falta está en esa fila o en las filas anteriores y si coincide, el elemento que falta está en las siguientes filas. Primero, encuentre esa fila usando la búsqueda binaria y luego aplique la búsqueda binaria en esa fila de la misma manera para encontrar la columna.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
#define Max 1000
// Function to return Missing
// Element from matrix MAt
int check(int Mat[][Max], int N, int M)
{
// Edge Case
if (Mat[0][0] != 1)
return 1;
// Initialize last element of
// first row
int X = Mat[0][0] + M - 1;
int m, l = 0, h = N - 1;
// Checking for row
while (l < h) {
// Avoiding overflow
m = l + (h - l) / 2;
if (Mat[m][M - 1] == X * (m + 1))
l = m + 1;
else
h = m;
}
// Set the required row index and
// last element of previous row
int R = h;
X = X * h;
l = 0, h = M - 1;
// Checking for column
while (l < h) {
// Avoiding overflow
m = l + (h - l) / 2;
if (Mat[R][m] == X + (m + 1))
l = m + 1;
else
h = m;
}
// Returning Missing Element
return X + h + 1;
}
// Driver Code
int main()
{
int N = 3;
int M = 4;
int Mat[][Max] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 11, 12, 13 } };
cout << check(Mat, N, M);
return 0;
}
Java
// Java program to implement the above approach
import java.util.*;
class GFG{
// Function to return Missing
// Element from matrix MAt
static int check(int Mat[][], int N, int M)
{
// Edge Case
if (Mat[0][0] != 1)
return 1;
// Initialize last element of
// first row
int X = Mat[0][0] + M - 1;
int m, l = 0, h = N - 1;
// Checking for row
while (l < h) {
// Avoiding overflow
m = l + (h - l) / 2;
if (Mat[m][M - 1] == X * (m + 1))
l = m + 1;
else
h = m;
}
// Set the required row index and
// last element of previous row
int R = h;
X = X * h;
l = 0;
h = M - 1;
// Checking for column
while (l < h) {
// Avoiding overflow
m = l + (h - l) / 2;
if (Mat[R][m] == X + (m + 1))
l = m + 1;
else
h = m;
}
// Returning Missing Element
return X + h + 1;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
int M = 4;
int Mat[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 11, 12, 13 } };
System.out.print(check(Mat, N, M));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program to implement the above approach # Function to return Missing # Element from matrix MAt def check(Mat, N, M): # Edge Case if (Mat[0][0] != 1): return 1; # Initialize last element of # first row X = Mat[0][0] + M - 1; m = 0; l = 0 h = N - 1; # Checking for row while (l < h): # Avoiding overflow m = l + (h - l) // 2; if (Mat[m][M - 1] == X * (m + 1)): l = m + 1; else: h = m; # Set the required row index and # last element of previous row R = h; X = X * h; l = 0; h = M - 1; # Checking for column while (l < h): # Avoiding overflow m = l + (h - l) // 2; if (Mat[R][m] == X + (m + 1)): l = m + 1; else: h = m; # Returning Missing Element return X + h + 1; # Driver Code if __name__ == '__main__': N = 3; M = 4; Mat = [[ 1, 2, 3, 4 ],[ 5, 6, 7, 8 ],[ 9, 11, 12, 13 ]] ; print(check(Mat, N, M)); # This code is contributed by Rajput-Ji
C#
// C# program to implement the above approach
using System;
public class GFG{
// Function to return Missing
// Element from matrix MAt
static int check(int [,]Mat, int N, int M)
{
// Edge Case
if (Mat[0,0] != 1)
return 1;
// Initialize last element of
// first row
int X = Mat[0,0] + M - 1;
int m, l = 0, h = N - 1;
// Checking for row
while (l < h) {
// Avoiding overflow
m = l + (h - l) / 2;
if (Mat[m,M - 1] == X * (m + 1))
l = m + 1;
else
h = m;
}
// Set the required row index and
// last element of previous row
int R = h;
X = X * h;
l = 0;
h = M - 1;
// Checking for column
while (l < h) {
// Avoiding overflow
m = l + (h - l) / 2;
if (Mat[R,m] == X + (m + 1))
l = m + 1;
else
h = m;
}
// Returning Missing Element
return X + h + 1;
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
int M = 4;
int [,]Mat = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 11, 12, 13 } };
Console.Write(check(Mat, N, M));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to implement the above approach
// Function to return Missing
// Element from matrix MAt
function check(Mat , N , M) {
// Edge Case
if (Mat[0][0] != 1)
return 1;
// Initialize last element of
// first row
var X = Mat[0][0] + M - 1;
var m, l = 0, h = N - 1;
// Checking for row
while (l < h) {
// Afunctioning overflow
m = l + parseInt((h - l) / 2);
if (Mat[m][M - 1] == X * (m + 1))
l = m + 1;
else
h = m;
}
// Set the required row index and
// last element of previous row
var R = h;
X = X * h;
l = 0;
h = M - 1;
// Checking for column
while (l < h) {
// Afunctioning overflow
m = l + parseInt((h - l) / 2);
if (Mat[R][m] == X + (m + 1))
l = m + 1;
else
h = m;
}
// Returning Missing Element
return X + h + 1;
}
// Driver Code
var N = 3;
var M = 4;
var Mat = [ [ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 11, 12, 13 ] ];
document.write(check(Mat, N, M));
// This code is contributed by Rajput-Ji
</script>
Producción
10
Complejidad de tiempo : O (log N + log M)
Espacio auxiliar : O (1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA