Dada una array de números sin ordenar, escriba una función que devuelva verdadero si la array consta de números consecutivos.
Ejemplos:
a) Si la array es {5, 2, 3, 1, 4}, entonces la función debería devolver verdadero porque la array tiene números consecutivos del 1 al 5. b) Si la array es {
83 , 78, 80, 81, 79, 82}, entonces la función debería devolver verdadero porque el arreglo tiene números consecutivos del 78 al 83.
c) Si el arreglo es {34, 23, 52, 12, 3}, entonces la función debería devolver falso porque el Los elementos no son consecutivos.
d) Si la array es {7, 6, 5, 5, 3, 4}, entonces la función debería devolver falso porque 5 y 5 no son consecutivos.
Método 1 (Usar Ordenar)
1) Ordenar todos los elementos.
2) Haga un escaneo lineal de la array ordenada. Si la diferencia entre el elemento actual y el siguiente elemento es distinta de 1, devuelve falso. Si todas las diferencias son 1, devuelve verdadero.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to Check if array
// elements are consecutive
bool areConsecutive(int arr[], int n)
{
//Sort the array
sort(arr,arr+n);
// checking the adjacent elements
for(int i=1;i<n;i++)
{
if(arr[i]!=arr[i-1]+1)
{
return false;
}
}
return true;
}
/* Driver program to test above functions */
int main()
{
int arr[]= {5, 4, 2, 3, 1, 6};
int n = sizeof(arr)/sizeof(arr[0]);
if(areConsecutive(arr, n) == true)
cout<<" Array elements are consecutive ";
else
cout<<" Array elements are not consecutive ";
return 0;
}
// This code is contributed by Aarti_Rathi
Java
// Java implementation of the approach
import java.util.Arrays;
class AreConsecutive {
/* The function checks if the array elements are consecutive
If elements are consecutive, then returns true, else returns
false */
boolean areConsecutive(int arr[], int n)
{
//Sort the array
Arrays.sort(arr);
// checking the adjacent elements
for(int i=1;i<n;i++)
{
if(arr[i]!=arr[i-1]+1)
{
return false;
}
}
return true;
}
public static void main(String[] args)
{
AreConsecutive consecutive = new AreConsecutive();
int arr[] = {5, 4, 2, 3, 1, 6};
int n = arr.length;
if (consecutive.areConsecutive(arr, n) == true)
System.out.println("Array elements are consecutive");
else
System.out.println("Array elements are not consecutive");
}
}
// This code is contributed by Aarti_Rathi
Python
# The function checks if the array elements
# are consecutive. If elements are consecutive,
# then returns true, else returns false
def areConsecutive(arr, n):
# Sort the array
arr.sort()
# checking the adjacent elements
for i in range (1,n):
if(arr[i]!=arr[i-1]+1):
return False;
return True;
# Driver Code
arr = [5, 4, 2, 3, 1, 6]
n = len(arr)
if(areConsecutive(arr, n) == True):
print("Array elements are consecutive ")
else:
print("Array elements are not consecutive ")
# This code is contributed by Aarti_Rathi
C#
using System;
class GFG {
// Function to Check if array
// elements are consecutive
static bool areConsecutive(int []arr, int n)
{
//Sort the array
Array.Sort(arr);
// checking the adjacent elements
for(int i=1;i<n;i++)
{
if(arr[i]!=arr[i-1]+1)
{
return false;
}
}
return true;
}
/* Driver program to test above
functions */
public static void Main()
{
int []arr = {5, 4, 2, 3, 1, 6};
int n = arr.Length;
if (areConsecutive(arr, n) == true)
Console.Write("Array elements "
+ "are consecutive");
else
Console.Write("Array elements "
+ "are not consecutive");
}
}
// This code is contributed by Aarti_Rathi
Javascript
//JS code to implement the approach
// The function checks if the array elements
// are consecutive. If elements are consecutive,
// then returns true, else returns false
function areConsecutive(arr, n)
{
// Sort the array
arr.sort();
// checking the adjacent elements
for (var i = 1; i < n; i++)
if(arr[i]!=arr[i-1]+1)
return false;
return true;
}
// Driver Code
var arr = [5, 4, 2, 3, 1, 6];
var n = arr.length;
if(areConsecutive(arr, n) == true)
console.log("Array elements are consecutive ");
else
console.log("Array elements are not consecutive ");
// This code is contributed by phasing17
Producción
Array elements are consecutive
Complejidad de tiempo: O(n log n)
Complejidad de espacio: O(1)
Método 2 (Usar array visitada)
La idea es verificar las siguientes dos condiciones. Si las dos condiciones siguientes son verdaderas, devuelva verdadero.
1) max – min + 1 = n donde max es el elemento máximo en la array, min es el elemento mínimo en la array y n es el número de elementos en la array.
2) Todos los elementos son distintos.
Para verificar si todos los elementos son distintos, podemos crear una array visited[] de tamaño n. Podemos asignar el i-ésimo elemento de la array de entrada arr[] a la array visitada usando arr[i] – min como índice en visited[].
C++
#include<stdio.h>
#include<stdlib.h>
/* Helper functions to get minimum and maximum in an array */
int getMin(int arr[], int n);
int getMax(int arr[], int n);
/* The function checks if the array elements are consecutive
If elements are consecutive, then returns true, else returns
false */
bool areConsecutive(int arr[], int n)
{
if ( n < 1 )
return false;
/* 1) Get the minimum element in array */
int min = getMin(arr, n);
/* 2) Get the maximum element in array */
int max = getMax(arr, n);
/* 3) max - min + 1 is equal to n, then only check all elements */
if (max - min + 1 == n)
{
/* Create a temp array to hold visited flag of all elements.
Note that, calloc is used here so that all values are initialized
as false */
bool *visited = (bool *) calloc (n, sizeof(bool));
int i;
for (i = 0; i < n; i++)
{
/* If we see an element again, then return false */
if ( visited[arr[i] - min] != false )
return false;
/* If visited first time, then mark the element as visited */
visited[arr[i] - min] = true;
}
/* If all elements occur once, then return true */
return true;
}
return false; // if (max - min + 1 != n)
}
/* UTILITY FUNCTIONS */
int getMin(int arr[], int n)
{
int min = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] < min)
min = arr[i];
return min;
}
int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
/* Driver program to test above functions */
int main()
{
int arr[]= {5, 4, 2, 3, 1, 6};
int n = sizeof(arr)/sizeof(arr[0]);
if(areConsecutive(arr, n) == true)
printf(" Array elements are consecutive ");
else
printf(" Array elements are not consecutive ");
getchar();
return 0;
}
Java
class AreConsecutive
{
/* The function checks if the array elements are consecutive
If elements are consecutive, then returns true, else returns
false */
boolean areConsecutive(int arr[], int n)
{
if (n < 1)
return false;
/* 1) Get the minimum element in array */
int min = getMin(arr, n);
/* 2) Get the maximum element in array */
int max = getMax(arr, n);
/* 3) max - min + 1 is equal to n, then only check all elements */
if (max - min + 1 == n)
{
/* Create a temp array to hold visited flag of all elements.
Note that, calloc is used here so that all values are initialized
as false */
boolean visited[] = new boolean[n];
int i;
for (i = 0; i < n; i++)
{
/* If we see an element again, then return false */
if (visited[arr[i] - min] != false)
return false;
/* If visited first time, then mark the element as visited */
visited[arr[i] - min] = true;
}
/* If all elements occur once, then return true */
return true;
}
return false; // if (max - min + 1 != n)
}
/* UTILITY FUNCTIONS */
int getMin(int arr[], int n)
{
int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
min = arr[i];
}
return min;
}
int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
/* Driver program to test above functions */
public static void main(String[] args)
{
AreConsecutive consecutive = new AreConsecutive();
int arr[] = {5, 4, 2, 3, 1, 6};
int n = arr.length;
if (consecutive.areConsecutive(arr, n) == true)
System.out.println("Array elements are consecutive");
else
System.out.println("Array elements are not consecutive");
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Helper functions to get Minimum and
# Maximum in an array
# The function checks if the array elements
# are consecutive. If elements are consecutive,
# then returns true, else returns false
def areConsecutive(arr, n):
if ( n < 1 ):
return False
# 1) Get the Minimum element in array */
Min = min(arr)
# 2) Get the Maximum element in array */
Max = max(arr)
# 3) Max - Min + 1 is equal to n,
# then only check all elements */
if (Max - Min + 1 == n):
# Create a temp array to hold visited
# flag of all elements. Note that, calloc
# is used here so that all values are
# initialized as false
visited = [False for i in range(n)]
for i in range(n):
# If we see an element again,
# then return false */
if (visited[arr[i] - Min] != False):
return False
# If visited first time, then mark
# the element as visited */
visited[arr[i] - Min] = True
# If all elements occur once,
# then return true */
return True
return False # if (Max - Min + 1 != n)
# Driver Code
arr = [5, 4, 2, 3, 1, 6]
n = len(arr)
if(areConsecutive(arr, n) == True):
print("Array elements are consecutive ")
else:
print("Array elements are not consecutive ")
# This code is contributed by mohit kumar
C#
using System;
class GFG {
/* The function checks if the array elements
are consecutive If elements are consecutive,
then returns true, else returns false */
static bool areConsecutive(int []arr, int n)
{
if (n < 1)
return false;
/* 1) Get the minimum element in array */
int min = getMin(arr, n);
/* 2) Get the maximum element in array */
int max = getMax(arr, n);
/* 3) max - min + 1 is equal to n, then
only check all elements */
if (max - min + 1 == n)
{
/* Create a temp array to hold visited
flag of all elements. Note that, calloc
is used here so that all values are
initialized as false */
bool []visited = new bool[n];
int i;
for (i = 0; i < n; i++)
{
/* If we see an element again, then
return false */
if (visited[arr[i] - min] != false)
return false;
/* If visited first time, then mark
the element as visited */
visited[arr[i] - min] = true;
}
/* If all elements occur once, then
return true */
return true;
}
return false; // if (max - min + 1 != n)
}
/* UTILITY FUNCTIONS */
static int getMin(int []arr, int n)
{
int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
min = arr[i];
}
return min;
}
static int getMax(int []arr, int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
/* Driver program to test above functions */
public static void Main()
{
int []arr = {5, 4, 2, 3, 1, 6};
int n = arr.Length;
if (areConsecutive(arr, n) == true)
Console.Write("Array elements are"
+ " consecutive");
else
Console.Write("Array elements are"
+ " not consecutive");
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP Program for above approach
// The function checks if the array elements
// are consecutive. If elements are consecutive,
// then returns true, else returns false
function areConsecutive($arr, $n)
{
if ( $n < 1 )
return false;
// 1) Get the minimum element in array
$min = getMin($arr, $n);
// 2) Get the maximum element in array
$max = getMax($arr, $n);
// 3) $max - $min + 1 is equal to $n,
// then only check all elements
if ($max - $min + 1 == $n)
{
// Create a temp array to hold
// visited flag of all elements.
$visited = array();
for ($i = 0; $i < $n; $i++)
{
$visited[$i] = false;
}
for ($i = 0; $i < $n; $i++)
{
// If we see an element again,
// then return false
if ( $visited[$arr[$i] - $min] != false )
return false;
// If visited first time, then mark
// the element as visited
$visited[$arr[$i] - $min] = true;
}
// If all elements occur once,
// then return true
return true;
}
return false; // if ($max - $min + 1 != $n)
}
// UTILITY FUNCTIONS
function getMin($arr, $n)
{
$min = $arr[0];
for ($i = 1; $i < $n; $i++)
if ($arr[$i] < $min)
$min = $arr[$i];
return $min;
}
function getMax($arr, $n)
{
$max = $arr[0];
for ($i = 1; $i < $n; $i++)
if ($arr[$i] > $max)
$max = $arr[$i];
return $max;
}
// Driver Code
$arr = array(5, 4, 2, 3, 1, 6);
$n = count($arr);
if(areConsecutive($arr, $n) == true)
echo "Array elements are consecutive ";
else
echo "Array elements are not consecutive ";
// This code is contributed by rathbhupendra
?>
Javascript
<script>
/* The function checks if the array elements are consecutive
If elements are consecutive, then returns true, else returns
false */
function areConsecutive(arr,n)
{
if (n < 1)
return false;
/* 1) Get the minimum element in array */
let min = getMin(arr, n);
/* 2) Get the maximum element in array */
let max = getMax(arr, n);
/* 3) max - min + 1 is equal to n, then only check all elements */
if (max - min + 1 == n)
{
/* Create a temp array to hold visited flag of all elements.
Note that, calloc is used here so that all values are initialized
as false */
let visited = new Array(n);
for(let i=0;i<n;i++)
{
visited[i]=false;
}
let i;
for (i = 0; i < n; i++)
{
/* If we see an element again, then return false */
if (visited[arr[i] - min] != false)
{
return false;
}
/* If visited first time, then mark the element as visited */
visited[arr[i] - min] = true;
}
/* If all elements occur once, then return true */
return true;
}
return false; // if (max - min + 1 != n)
}
/* UTILITY FUNCTIONS */
function getMin(arr, n)
{
let min = arr[0];
for (let i = 1; i < n; i++)
{
if (arr[i] < min)
min = arr[i];
}
return min;
}
function getMax(arr,n)
{
let max = arr[0];
for (let i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
/* Driver program to test above functions */
let arr=[5, 4, 2, 3, 1, 6]
let n = arr.length;
if (areConsecutive(arr, n))
{
document.write("Array elements are consecutive");
}
else
{
document.write("Array elements are not consecutive");
}
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Array elements are consecutive
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Método 3 (Marcar los elementos de la array visitados como negativos)
Este método tiene una complejidad de tiempo O(n) y un espacio adicional de O(1), pero cambia la array original y solo funciona si todos los números son positivos. Sin embargo, podemos obtener la array original agregando un paso adicional. Es una extensión del método 2 y tiene los mismos dos pasos.
1) max – min + 1 = n donde max es el elemento máximo en la array, min es el elemento mínimo en la array y n es el número de elementos en la array.
2) Todos los elementos son distintos.
En este método, la implementación del paso 2 difiere del método 2. En lugar de crear una nueva array, modificamos la array de entrada arr[] para realizar un seguimiento de los elementos visitados. La idea es recorrer la array y para cada índice i (donde 0 ≤ i < n), hacer arr[arr[i] – min]] como un valor negativo. Si volvemos a ver un valor negativo, entonces hay repetición.
C++
#include<stdio.h>
#include<stdlib.h>
/* Helper functions to get minimum and maximum in an array */
int getMin(int arr[], int n);
int getMax(int arr[], int n);
/* The function checks if the array elements are consecutive
If elements are consecutive, then returns true, else returns
false */
bool areConsecutive(int arr[], int n)
{
if ( n < 1 )
return false;
/* 1) Get the minimum element in array */
int min = getMin(arr, n);
/* 2) Get the maximum element in array */
int max = getMax(arr, n);
/* 3) max - min + 1 is equal to n then only check all elements */
if (max - min + 1 == n)
{
int i;
for(i = 0; i < n; i++)
{
int j;
if (arr[i] < 0)
j = -arr[i] - min;
else
j = arr[i] - min;
// if the value at index j is negative then
// there is repetition
if (arr[j] > 0)
arr[j] = -arr[j];
else
return false;
}
/* If we do not see a negative value then all elements
are distinct */
return true;
}
return false; // if (max - min + 1 != n)
}
/* UTILITY FUNCTIONS */
int getMin(int arr[], int n)
{
int min = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] < min)
min = arr[i];
return min;
}
int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
/* Driver program to test above functions */
int main()
{
int arr[]= {1, 4, 5, 3, 2, 6};
int n = sizeof(arr)/sizeof(arr[0]);
if(areConsecutive(arr, n) == true)
printf(" Array elements are consecutive ");
else
printf(" Array elements are not consecutive ");
getchar();
return 0;
}
Java
class AreConsecutive
{
/* The function checks if the array elements are consecutive
If elements are consecutive, then returns true, else returns
false */
boolean areConsecutive(int arr[], int n)
{
if (n < 1)
return false;
/* 1) Get the minimum element in array */
int min = getMin(arr, n);
/* 2) Get the maximum element in array */
int max = getMax(arr, n);
/* 3) max-min+1 is equal to n then only check all elements */
if (max - min + 1 == n)
{
int i;
for (i = 0; i < n; i++)
{
int j;
if (arr[i] < 0)
j = -arr[i] - min;
else
j = arr[i] - min;
// if the value at index j is negative then
// there is repetition
if (arr[j] > 0)
arr[j] = -arr[j];
else
return false;
}
/* If we do not see a negative value then all elements
are distinct */
return true;
}
return false; // if (max-min+1 != n)
}
/* UTILITY FUNCTIONS */
int getMin(int arr[], int n)
{
int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
min = arr[i];
}
return min;
}
int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
/* Driver program to test above functions */
public static void main(String[] args)
{
AreConsecutive consecutive = new AreConsecutive();
int arr[] = {5, 4, 2, 3, 1, 6};
int n = arr.length;
if (consecutive.areConsecutive(arr, n) == true)
System.out.println("Array elements are consecutive");
else
System.out.println("Array elements are not consecutive");
}
}
// This code is contributed by Mayank Jaiswal
Python 3
# Helper functions to get minimum and
# maximum in an array
# The function checks if the array
# elements are consecutive. If elements
# are consecutive, then returns true,
# else returns false
def areConsecutive(arr, n):
if ( n < 1 ):
return False
# 1) Get the minimum element in array
min = getMin(arr, n)
# 2) Get the maximum element in array
max = getMax(arr, n)
# 3) max - min + 1 is equal to n
# then only check all elements
if (max - min + 1 == n):
for i in range(n):
if (arr[i] < 0):
j = -arr[i] - min
else:
j = arr[i] - min
# if the value at index j is negative
# then there is repetition
if (arr[j] > 0):
arr[j] = -arr[j]
else:
return False
# If we do not see a negative value
# then all elements are distinct
return True
return False # if (max - min + 1 != n)
# UTILITY FUNCTIONS
def getMin(arr, n):
min = arr[0]
for i in range(1, n):
if (arr[i] < min):
min = arr[i]
return min
def getMax(arr, n):
max = arr[0]
for i in range(1, n):
if (arr[i] > max):
max = arr[i]
return max
# Driver Code
if __name__ == "__main__":
arr = [1, 4, 5, 3, 2, 6]
n = len(arr)
if(areConsecutive(arr, n) == True):
print(" Array elements are consecutive ")
else:
print(" Array elements are not consecutive ")
# This code is contributed by ita_c
C#
using System;
class GFG {
/* The function checks if the array
elements are consecutive If elements
are consecutive, then returns true,
else returns false */
static bool areConsecutive(int []arr, int n)
{
if (n < 1)
return false;
/* 1) Get the minimum element in
array */
int min = getMin(arr, n);
/* 2) Get the maximum element in
array */
int max = getMax(arr, n);
/* 3) max-min+1 is equal to n then
only check all elements */
if (max - min + 1 == n)
{
int i;
for (i = 0; i < n; i++)
{
int j;
if (arr[i] < 0)
j = -arr[i] - min;
else
j = arr[i] - min;
// if the value at index j
// is negative then
// there is repetition
if (arr[j] > 0)
arr[j] = -arr[j];
else
return false;
}
/* If we do not see a negative
value then all elements
are distinct */
return true;
}
// if (max-min+1 != n)
return false;
}
/* UTILITY FUNCTIONS */
static int getMin(int []arr, int n)
{
int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
min = arr[i];
}
return min;
}
static int getMax(int []arr, int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
/* Driver program to test above
functions */
public static void Main()
{
int []arr = {5, 4, 2, 3, 1, 6};
int n = arr.Length;
if (areConsecutive(arr, n) == true)
Console.Write("Array elements "
+ "are consecutive");
else
Console.Write("Array elements "
+ "are not consecutive");
}
}
// This code is contributed by nitin mittal.
PHP
<?php
/* The function checks if the array elements
are consecutive If elements are consecutive,
then returns true, else returns false */
function areConsecutive( $arr, $n)
{
if ( $n < 1 )
return false;
/* 1) Get the minimum element in array */
$min = getMin($arr, $n);
/* 2) Get the maximum element in array */
$max = getMax($arr, $n);
/* 3) max - min + 1 is equal to n then
only check all elements */
if ($max - $min + 1 == $n)
{
$i;
for($i = 0; $i < $n; $i++)
{
$j;
if ($arr[$i] < 0)
$j = -$arr[$i] - $min;
else
$j = $arr[$i] - $min;
// if the value at index j is
// negative then there is
// repetition
if ($arr[$j] > 0)
$arr[$j] = -$arr[$j];
else
return false;
}
/* If we do not see a negative value
then all elements are distinct */
return true;
}
return false; // if (max - min + 1 != n)
}
/* UTILITY FUNCTIONS */
function getMin( $arr, $n)
{
$min = $arr[0];
for ( $i = 1; $i < $n; $i++)
if ($arr[$i] < $min)
$min = $arr[$i];
return $min;
}
function getMax( $arr, $n)
{
$max = $arr[0];
for ( $i = 1; $i < $n; $i++)
if ($arr[$i] > $max)
$max = $arr[$i];
return $max;
}
/* Driver program to test above functions */
$arr= array(1, 4, 5, 3, 2, 6);
$n = count($arr);
if(areConsecutive($arr, $n) == true)
echo " Array elements are consecutive ";
else
echo " Array elements are not consecutive ";
// This code is contributed by anuj_67.
?>
Javascript
<script>
/* The function checks if the array elements are consecutive
If elements are consecutive, then returns true, else returns
false */
function areConsecutive(arr,n)
{
if (n < 1)
return false;
/* 1) Get the minimum element in array */
let min = getMin(arr, n);
/* 2) Get the maximum element in array */
let max = getMax(arr, n);
/* 3) max-min+1 is equal to n then only check all elements */
if (max - min + 1 == n)
{
let i;
for (i = 0; i < n; i++)
{
let j;
if (arr[i] < 0)
j = -arr[i] - min;
else
j = arr[i] - min;
// if the value at index j is negative then
// there is repetition
if (arr[j] > 0)
arr[j] = -arr[j];
else
return false;
}
/* If we do not see a negative value then all elements
are distinct */
return true;
}
return false; // if (max-min+1 != n)
}
/* UTILITY FUNCTIONS */
function getMin(arr,n)
{
let min = arr[0];
for (let i = 1; i < n; i++)
{
if (arr[i] < min)
min = arr[i];
}
return min;
}
function getMax(arr,n)
{
let max = arr[0];
for (let i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
/* Driver program to test above functions */
let arr=[5, 4, 2, 3, 1, 6];
let n = arr.length;
if (areConsecutive(arr, n) == true)
document.write("Array elements are consecutive");
else
document.write("Array elements are not consecutive");
// This code is contributed by unknown2108
</script>
Producción
Array elements are consecutive
Tenga en cuenta que este método podría no funcionar para números negativos. Por ejemplo, devuelve falso para {2, 1, 0, -3, -1, -2}.
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Método 4 (usando la propiedad XOR)
Este método tiene una complejidad de tiempo O (n) y un espacio extra O (1), no cambia la array original y funciona siempre.
- Como los elementos deben ser consecutivos, encontremos el elemento mínimo o el elemento máximo en la array.
- Ahora, si tomamos xor de dos elementos iguales, dará como resultado cero (a^a = 0).
- Supongamos que la array es {-2, 0, 1, -3, 4, 3, 2, -1}, ahora si hacemos xor en todos los elementos de la array con el elemento mínimo y seguimos aumentando el elemento mínimo, la xor resultante se convertirá en 0 solo si los elementos son consecutivo
C
//Code is contributed by Dhananjay Dhawale @chessnoobdj
#include<stdio.h>
#include<stdlib.h>
/* UTILITY FUNCTIONS */
int getMin(int arr[], int n)
{
int min = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] < min)
min = arr[i];
return min;
}
int areConsecutive(int arr[], int n)
{
int min_ele = getMin(arr, n), num = 0;
for(int i=0; i<n; i++){
num ^= min_ele^arr[i];
min_ele += 1;
}
if(num == 0)
return 1;
return 0;
}
/* Driver program to test above functions */
int main()
{
int arr[]= {1, 4, 5, 3, 2, 6};
int n = sizeof(arr)/sizeof(arr[0]);
if(areConsecutive(arr, n) == 1)
printf(" Array elements are consecutive ");
else
printf(" Array elements are not consecutive ");
getchar();
return 0;
}
C++
//Code is contributed by Dhananjay Dhawale @chessnoobdj
#include <iostream>
#include <algorithm>
using namespace std;
bool areConsecutive(int arr[], int n)
{
int min_ele = *min_element(arr, arr+n), num = 0;
for(int i=0; i<n; i++){
num ^= min_ele^arr[i];
min_ele += 1;
}
if(num == 0)
return 1;
return 0;
}
/* Driver program to test above functions */
int main()
{
int arr[]= {1, 4, 5, 3, 2, 6};
int n = sizeof(arr)/sizeof(arr[0]);
if(areConsecutive(arr, n) == true)
printf(" Array elements are consecutive ");
else
printf(" Array elements are not consecutive ");
getchar();
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
import java.util.Collections;
class AreConsecutive {
boolean areConsecutive(int arr[], int n)
{
int min_ele = Arrays.stream(arr).min().getAsInt();
int num = 0;
for(int i=0; i<n; i++){
num = num ^ min_ele ^ arr[i];
min_ele += 1;
}
if(num == 0)
return true;
return false;
}
public static void main(String[] args)
{
AreConsecutive consecutive = new AreConsecutive();
int arr[] = {5, 4, 2, 3, 1, 6};
int n = arr.length;
if (consecutive.areConsecutive(arr, n) == true)
System.out.println("Array elements are consecutive");
else
System.out.println("Array elements are not consecutive");
}
}
// This code is contributed by Aarti_Rathi
Python3
# Function to Check if array
# elements are consecutive
def areConsecutive(arr, n):
min_ele = arr.index(min(arr))
num = 0
for i in range(0, n):
num ^= arr[min_ele] ^ arr[i]
arr[min_ele] += 1
if num == 0:
return True
return False
# Driver program to test above
# functions
if __name__ == "__main__":
arr = [1, 4, 5, 3, 2, 6]
n = len(arr)
if areConsecutive(arr, n) == True:
print(" Array elements are consecutive ", end=' ')
else:
print(" Array elements are not consecutive ", end=' ')
# This code is contributed by Aarti_Rathi
C#
using System;
using System.Linq;
class GFG {
// Function to Check if array
// elements are consecutive
static bool areConsecutive(int []arr, int n)
{
int min_ele = arr.Min();
int num = 0;
for(int i=0; i<n; i++){
num ^= min_ele^arr[i];
min_ele += 1;
}
if(num == 0)
return true;
return false;
}
/* Driver program to test above
functions */
public static void Main()
{
int []arr = {5, 4, 2, 3, 1, 6};
int n = arr.Length;
if (areConsecutive(arr, n) == true)
Console.Write("Array elements "
+ "are consecutive");
else
Console.Write("Array elements "
+ "are not consecutive");
}
}
// This code is contributed by Aarti_Rathi
Javascript
// Javascript Program
var areConsecutive = function(arr)
{
var min_ele = Math.min.apply(Math, arr);
var num = 0;
for(var i = 0; i < arr.length; i++){
num = num ^ min_ele ^ arr[i];
min_ele += 1;
}
if(num == 0)
return 1;
return 0;
}
/* Driver program to test above functions */
arr = [1, 2, 3, 4, 5, 6];
if(areConsecutive(arr) == 1){
console.log(" Array elements are consecutive ");}
else
console.log(" Array elements are not consecutive ");
// This code is contributed by Sajal Aggarwal.
Producción
Array elements are consecutive
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Artículos relacionados: Comprobar si los elementos de la array son consecutivos en el tiempo O(n) y en el espacio O(1) (maneja números tanto positivos como negativos)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA