Dada una array de n enteros. La tarea es verificar si se puede formar una progresión aritmética usando todos los elementos dados. Si es posible escriba “Sí”, de lo contrario escriba “No”.
Ejemplos:
Input : arr[] = {0, 12, 4, 8}
Output : Yes
Rearrange given array as {0, 4, 8, 12}
which forms an arithmetic progression.
Input : arr[] = {12, 40, 11, 20}
Output : No
Método 1 (Simple)
Una solución simple es encontrar primero el elemento más pequeño, luego encontrar el segundo elemento más pequeño y encontrar la diferencia entre estos dos. Sea esta diferencia d. Después de encontrar la diferencia, encuentre el tercero más pequeño, el cuarto más pequeño y así sucesivamente. Después de encontrar cada i-ésimo más pequeño (desde el tercero en adelante), encuentre la diferencia entre el valor del elemento actual y el valor del elemento anterior. Si la diferencia no es igual a d, devuelve falso. Si todos los elementos tienen la misma diferencia, devuelve verdadero. La complejidad temporal de esta solución es O(n 2 )
Método 2 (Usar clasificación)
La idea es ordenar la array dada. Después de ordenar, verifique si las diferencias entre elementos consecutivos son iguales o no. Si todas las diferencias son iguales, la progresión aritmética es posible.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to check if a given array
// can form arithmetic progression
#include<bits/stdc++.h>
using namespace std;
// Returns true if a permutation of arr[0..n-1]
// can form arithmetic progression
bool checkIsAP(int arr[], int n)
{
if (n == 1)
return true;
// Sort array
sort(arr, arr + n);
// After sorting, difference between
// consecutive elements must be same.
int d = arr[1] - arr[0];
for (int i=2; i<n; i++)
if (arr[i] - arr[i-1] != d)
return false;
return true;
}
// Driven Program
int main()
{
int arr[] = { 20, 15, 5, 0, 10 };
int n = sizeof(arr)/sizeof(arr[0]);
(checkIsAP(arr, n))? (cout << "Yes" << endl) :
(cout << "No" << endl);
return 0;
}
Java
// Java program to check if a given array
// can form arithmetic progression
import java.util.Arrays;
class GFG {
// Returns true if a permutation of
// arr[0..n-1] can form arithmetic
// progression
static boolean checkIsAP(int arr[], int n)
{
if (n == 1)
return true;
// Sort array
Arrays.sort(arr);
// After sorting, difference between
// consecutive elements must be same.
int d = arr[1] - arr[0];
for (int i = 2; i < n; i++)
if (arr[i] - arr[i-1] != d)
return false;
return true;
}
//driver code
public static void main (String[] args)
{
int arr[] = { 20, 15, 5, 0, 10 };
int n = arr.length;
if(checkIsAP(arr, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to check if a given
# array can form arithmetic progression
# Returns true if a permutation of arr[0..n-1]
# can form arithmetic progression
def checkIsAP(arr, n):
if (n == 1): return True
# Sort array
arr.sort()
# After sorting, difference between
# consecutive elements must be same.
d = arr[1] - arr[0]
for i in range(2, n):
if (arr[i] - arr[i-1] != d):
return False
return True
# Driver code
arr = [ 20, 15, 5, 0, 10 ]
n = len(arr)
print("Yes") if(checkIsAP(arr, n)) else print("No")
# This code is contributed by Anant Agarwal.
C#
// C# program to check if a given array
// can form arithmetic progression
using System;
class GFG {
// Returns true if a permutation of
// arr[0..n-1] can form arithmetic
// progression
static bool checkIsAP(int []arr, int n)
{
if (n == 1)
return true;
// Sort array
Array.Sort(arr);
// After sorting, difference between
// consecutive elements must be same.
int d = arr[1] - arr[0];
for (int i = 2; i < n; i++)
if (arr[i] - arr[i - 1] != d)
return false;
return true;
}
//Driver Code
public static void Main ()
{
int []arr = {20, 15, 5, 0, 10};
int n = arr.Length;
if(checkIsAP(arr, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to check if
// a given array can form
// arithmetic progression
// Returns true if a permutation
// of arr[0..n-1] can form
// arithmetic progression
function checkIsAP($arr, $n)
{
if ($n == 1)
return true;
// Sort array
sort($arr);
// After sorting, difference
// between consecutive elements
// must be same.
$d = $arr[1] - $arr[0];
for ($i = 2; $i < $n; $i++)
if ($arr[$i] -
$arr[$i - 1] != $d)
return false;
return true;
}
// Driver Code
$arr = array(20, 15, 5, 0, 10);
$n = count($arr);
if(checkIsAP($arr, $n))
echo "Yes";
else
echo "No";
// This code is contributed
// by Sam007
?>
Javascript
<script>
// Javascript program to check if a given array
// can form arithmetic progression
// Returns true if a permutation of arr[0..n-1]
// can form arithmetic progression
function checkIsAP(arr, n)
{
if (n == 1)
return true;
// Sort array
arr.sort((a, b) => a - b);
// After sorting, difference between
// consecutive elements must be same.
let d = arr[1] - arr[0];
for (let i=2; i<n; i++)
if (arr[i] - arr[i-1] != d)
return false;
return true;
}
// Driven Program
let arr = [ 20, 15, 5, 0, 10 ];
let n = arr.length;
(checkIsAP(arr, n))? (document.write("Yes" + "<br>")) :
(document.write("No" + "<br>"));
// This code is contributed by Mayank Tyagi
</script>
Producción
Yes
Complejidad Temporal: O(n Log n).
Espacio Auxiliar: O(1)
Método 3 (usar hashing)
- Descubra los elementos más pequeños y segundos más pequeños
- Encuentra diferentes entre los dos elementos. d = segundo_más pequeño – más pequeño
- Almacene todos los elementos en un hashmap y devuelva «NO» si se encuentra un elemento duplicado (se puede hacer junto con el paso 1).
- Ahora comience desde el «segundo elemento más pequeño + d» y verifique uno por uno los términos n-2 de Progresión aritmética en hashmap. Si falta algún valor de progresión, devuelve falso.
- Devuelva «SÍ» después del final del bucle.
A continuación se muestra la implementación de este método.
C++
// C++ program to check if a given array
// can form arithmetic progression
#include <bits/stdc++.h>
using namespace std;
// Returns true if a permutation of arr[0..n-1]
// can form arithmetic progression
bool checkIsAP(int arr[], int n)
{
unordered_map<int, int> hm;
int smallest = INT_MAX, second_smallest = INT_MAX;
for (int i = 0; i < n; i++) {
// Find the smallest and and
// update second smallest
if (arr[i] < smallest) {
second_smallest = smallest;
smallest = arr[i];
}
// Find second smallest
else if (arr[i] != smallest
&& arr[i] < second_smallest)
second_smallest = arr[i];
// Check if the duplicate element found or not
if (hm.find(arr[i]) == hm.end())
hm[arr[i]]++;
// If duplicate found then return false
else
return false;
}
// Find the difference between smallest and second
// smallest
int diff = second_smallest - smallest;
// As we have used smallest and
// second smallest,so we
// should now only check for n-2 elements
for (int i = 0; i < n - 1; i++) {
if (hm.find(second_smallest) == hm.end())
return false;
second_smallest += diff;
}
return true;
}
// Driven Program
int main()
{
int arr[] = { 20, 15, 5, 0, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
(checkIsAP(arr, n)) ? (cout << "Yes" << endl)
: (cout << "No" << endl);
return 0;
// This code is contributed by Raman Jha
}
Java
// Java program to check if a given array
// can form arithmetic progression
import java.util.HashMap;
class GFG {
// Returns true if a permutation of arr[0..n-1]
// can form arithmetic progression
static boolean checkIsAP(int arr[], int n) {
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int smallest = Integer.MAX_VALUE, second_smallest = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
// Find the smallest and and
// update second smallest
if (arr[i] < smallest) {
second_smallest = smallest;
smallest = arr[i];
}
// Find second smallest
else if (arr[i] != smallest
&& arr[i] < second_smallest)
second_smallest = arr[i];
// Check if the duplicate element found or not
if (!hm.containsKey(arr[i])) {
hm.put(arr[i], 1);
}
// If duplicate found then return false
else
return false;
}
// Find the difference between smallest and second
// smallest
int diff = second_smallest - smallest;
// As we have used smallest and
// second smallest,so we
// should now only check for n-2 elements
for (int i = 0; i < n - 1; i++) {
if (!hm.containsKey(second_smallest))
return false;
second_smallest += diff;
}
return true;
}
// Driven Program
public static void main(String args[]) {
int arr[] = { 20, 15, 5, 0, 10 };
int n = arr.length;
if (checkIsAP(arr, n)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
;
}
}
// This code is contributed by gfgking
Python3
# Python3 program to check if a given array
# can form arithmetic progression
# Returns true if a permutation of arr[0..n-1]
# can form arithmetic progression
def checkIsAP(arr, n):
hm = {}
smallest = float('inf')
second_smallest = float('inf')
for i in range(n):
# Find the smallest and and
# update second smallest
if (arr[i] < smallest):
second_smallest = smallest
smallest = arr[i]
# Find second smallest
else if (arr[i] != smallest and
arr[i] < second_smallest):
second_smallest = arr[i]
# Check if the duplicate element found or not
if arr[i] not in hm:
hm[arr[i]] = 1
# If duplicate found then return false
else:
return False
# Find the difference between smallest
# and second smallest
diff = second_smallest - smallest
# As we have used smallest and
# second smallest,so we
# should now only check for n-2 elements
for i in range(n-1):
if (second_smallest) not in hm:
return False
second_smallest += diff
return True
# Driver code
arr = [ 20, 15, 5, 0, 10 ]
n = len(arr)
if (checkIsAP(arr, n)):
print("Yes")
else:
print("No")
# This code is contributed by rohitsingh07052
C#
// C# program to check if a given array
// can form arithmetic progression
using System;
using System.Collections.Generic;
class GFG
{
// Returns true if a permutation of arr[0..n-1]
// can form arithmetic progression
public static bool checkIsAP(int[] arr, int n) {
Dictionary<int, int> hm = new Dictionary<int, int>();
int smallest = Int32.MaxValue, second_smallest = Int32.MaxValue;
for (int i = 0; i < n; i++) {
// Find the smallest and and
// update second smallest
if (arr[i] < smallest) {
second_smallest = smallest;
smallest = arr[i];
}
// Find second smallest
else if (arr[i] != smallest
&& arr[i] < second_smallest)
second_smallest = arr[i];
// Check if the duplicate element found or not
if (!hm.ContainsKey(arr[i])) {
hm[arr[i]]= 1;
}
// If duplicate found then return false
else
return false;
}
// Find the difference between smallest and second
// smallest
int diff = second_smallest - smallest;
// As we have used smallest and
// second smallest,so we
// should now only check for n-2 elements
for (int i = 0; i < n - 1; i++) {
if (!hm.ContainsKey(second_smallest))
return false;
second_smallest += diff;
}
return true;
}
// Driven Program
public static void Main(string[] args) {
int[] arr = { 20, 15, 5, 0, 10 };
int n = arr.Length;
if (checkIsAP(arr, n)) {
Console.WriteLine("Yes");
} else {
Console.WriteLine("No");
}
}
}
// This code is contributed by Pushpesh raj
Javascript
<script>
// Javascript program to check if a given array
// can form arithmetic progression
// Returns true if a permutation of arr[0..n-1]
// can form arithmetic progression
function checkIsAP(arr, n)
{
var hm = new Map();
var smallest = 1000000000, second_smallest = 1000000000;
for (var i = 0; i < n; i++) {
// Find the smallest and and
// update second smallest
if (arr[i] < smallest) {
second_smallest = smallest;
smallest = arr[i];
}
// Find second smallest
else if (arr[i] != smallest
&& arr[i] < second_smallest)
second_smallest = arr[i];
// Check if the duplicate element found or not
if (!hm.has(arr[i]))
{
hm.set(arr[i], 1);
}
// If duplicate found then return false
else
return false;
}
// Find the difference between smallest and second
// smallest
var diff = second_smallest - smallest;
// As we have used smallest and
// second smallest,so we
// should now only check for n-2 elements
for (var i = 0; i < n - 1; i++) {
if (!hm.has(second_smallest))
return false;
second_smallest += diff;
}
return true;
}
// Driven Program
var arr = [20, 15, 5, 0, 10 ];
var n = arr.length;
(checkIsAP(arr, n)) ? (document.write( "Yes"))
: (document.write( "No" ));
// This code is contributed by famously.
</script>
Producción
Yes
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n)
Gracias a Chenna Rao por sugerir este método.
Método 4 (usando la ordenación por conteo)
Podemos reducir el espacio requerido en el método 3 si se puede modificar la array dada.
- Encuentra los elementos más pequeños y segundos más pequeños.
- Encuentre d = segundo_más pequeño – más pequeño
- Resta el elemento más pequeño de todos los elementos.
- Ahora, si la array dada representa AP, todos los elementos deben tener la forma i*d donde i varía de 0 a n-1.
- Uno por uno divide todos los elementos reducidos con d. Si algún elemento no es divisible por d, devuelve falso.
- Ahora, si la array representa AP, debe ser una permutación de números de 0 a n-1. Podemos verificar esto fácilmente usando la ordenación por conteo.
Método 5 (Hashing con Single Pass)
La idea básica es encontrar la diferencia común del AP averiguando el elemento máximo y mínimo de la array. Después de eso, comience desde el valor máximo y continúe disminuyendo el valor por la diferencia común mientras verifica si este nuevo valor está presente en el mapa hash o no. Si en algún momento el valor no está presente en el hashset, rompa el ciclo. La situación ideal después de que se rompa el bucle es que se hayan cubierto todos los n elementos y, en caso afirmativo, devuelva verdadero; de lo contrario, devuelva falso.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
bool checkIsAP(int arr[], int n)
{
unordered_set<int> st;
int maxi = INT_MIN;
int mini = INT_MAX;
for (int i=0;i<n;i++) {
maxi = max(arr[i], maxi);
mini = min(arr[i], mini);
st.insert(arr[i]);
}
// FINDING THE COMMON DIFFERENCE
int diff = (maxi - mini) / (n - 1);
int count = 0;
// CHECK IF PRESENT IN THE HASHSET OR NOT
while (st.find(maxi)!=st.end()) {
count++;
maxi = maxi - diff;
}
if (count == n)
return true;
return false;
}
// Driver Code
int main()
{
int arr[] = { 0, 12, 4, 8 };
int n = 4;
cout << boolalpha << checkIsAP(arr, n);
return 0;
}
// This code is contributed by Rohit Pradhan
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
public static void main(String[] args)
{
int[] arr = { 0, 12, 4, 8 };
int n = arr.length;
System.out.println(checkIsAP(arr, n));
}
static boolean checkIsAP(int arr[], int n)
{
HashSet<Integer> set = new HashSet<Integer>();
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i : arr) {
max = Math.max(i, max);
min = Math.min(i, min);
set.add(i);
}
// FINDING THE COMMON DIFFERENCE
int diff = (max - min) / (n - 1);
int count = 0;
// CHECK IF PRESENT IN THE HASHSET OR NOT
while (set.contains(max)) {
count++;
max = max - diff;
}
if (count == arr.length)
return true;
return false;
}
}
Python3
import sys def checkIsAP(arr, n): Set = set() Max = -sys.maxsize - 1 Min = sys.maxsize for i in arr: Max = max(i, Max) Min = min(i, Min) Set.add(i) # FINDING THE COMMON DIFFERENCE diff = (Max - Min) // (n - 1) count = 0 # CHECK IF PRESENT IN THE HASHSET OR NOT while (Max in Set): count += 1 Max = Max - diff if (count == len(arr)): return True return False # driver code arr = [ 0, 12, 4, 8 ] n = len(arr) print(checkIsAP(arr, n)) # This code is contributed by shinjanpatra
C#
using System;
using System.Collections.Generic;
public class GFG
{
// C# program for above approach
static bool checkIsAP(int[] arr, int n)
{
HashSet<int> st = new HashSet<int>();
int maxi = int.MinValue;
int mini = int.MaxValue;
for (int i = 0; i < n; i++) {
maxi = Math.Max(arr[i], maxi);
mini = Math.Min(arr[i], mini);
st.Add(arr[i]);
}
// FINDING THE COMMON DIFFERENCE
int diff = (maxi - mini) / (n - 1);
int count = 0;
// CHECK IF PRESENT IN THE HASHSET OR NOT
while (st.Contains(maxi)) {
count++;
maxi = maxi - diff;
}
if (count == n) {
return true;
}
return false;
}
// Driver Code
internal static void Main()
{
int[] arr = { 0, 12, 4, 8 };
int n = 4;
Console.Write(checkIsAP(arr, n));
}
// This code is contributed by Aarti_Rathi
}
Javascript
<script>
function checkIsAP(arr, n){
set = new Set()
let Max = Number.MIN_VALUE
let Min = Number.MAX_VALUE
for(let i of arr){
Max = Math.max(i, Max)
Min = Math.min(i, Min)
set.add(i)
}
// FINDING THE COMMON DIFFERENCE
let diff = Math.floor((Max - Min) / (n - 1))
let count = 0
// CHECK IF PRESENT IN THE HASHSET OR NOT
while (set.has(Max)){
count += 1
Max = Max - diff
}
if (count == arr.length)
return true
return false
}
// driver code
let arr = [ 0, 12, 4, 8 ]
let n = arr.length
document.write(checkIsAP(arr, n))
// This code is contributed by shinjanpatra
</script>
Producción
true
Tiempo Complejidad – O(n)
Espacio Auxiliar – O(n)
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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