Check whether Arithmetic Progression can be formed from the given array
Given an array of n integers. The task is to check whether an arithmetic progression can be formed using all the given elements. If possible print “Yes”, else print “No”.
Examples:
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
Method 1 (Simple)
A simple solution is to first find the smallest element, then find second smallest element and find the difference between these two. Let this difference be d. After finding the difference, find third smallest, fourth smallest and so on. After finding every i-th smallest (from third onward), find the difference between value of current element and value of previous element. If difference is not same as d, return false. If all elements have same difference, return true. Time complexity of this solution is O(n2)
Method 2(Use Sorting)
The idea is to sort the given array. After sorting, check if differences between consecutive elements are same or not. If all differences are same, Arithmetic Progression is possible.
Below is the implementation of this approach:
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> |
Yes
Time Complexity: O(n Log n).
Auxiliary Space: O(1)
Method 3(Use Hashing)
- Find out the smallest and second smallest elements
- Find difference between the two elements. d = second_smallest – smallest
- Store all elements in a hashmap and return “NO” if duplicate element found (can be done together with step 1).
- Now start from “second smallest element + d” and one by one check n-2 terms of Arithmetic Progression in hashmap. If any value of progression is missing, return false.
- Return “YES” after end of the loop.
Below is the implementation of this method.
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 // 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 // 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 # 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 // 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 // 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> |
Yes
Time Complexity: O(n)
Auxiliary Space: O(n)
Thanks to Chenna Rao for suggesting this method,
Method 4(Using counting sort)
We can reduce space required in method 3 if given array can be modified.
- Find smallest and second smallest elements.
- Find d = second_smallest – smallest
- Subtract smallest element from all elements.
- Now if given array represent AP, all elements should be of form i*d where i varies from 0 to n-1.
- One by one divide all reduced elements with d. If any element is not divisible by d, return false.
- Now if array represents AP, it must be a permutation of numbers from 0 to n-1. We can easily check this using counting sort.
C++
// C++ program to check if a given array // can form arithmetic progression #include <bits/stdc++.h> using namespace std; // Checking if array is permutation // of 0 to n-1 using counting sort bool countingsort( int arr[], int n) { int count[n] = { 0 }; // Counting the frequency for ( int i = 0; i < n; i++) { count[arr[i]]++; } // Check if each frequency is 1 only for ( int i = 0; i <= n-1; i++) { if (count[i] != 1) return false ; } return true ; } // Returns true if a permutation of arr[0..n-1] // can form arithmetic progression bool checkIsAP( int arr[], int n) { int smallest = INT_MAX, second_smallest = INT_MAX; for ( int i = 0; i < n; i++) { // Find the smallest 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]; } // Find the difference between smallest and second // smallest int diff = second_smallest - smallest; for ( int i = 0; i < n; i++) { arr[i]=arr[i]-smallest; } for ( int i=0;i<n;i++) { if (arr[i]%diff!=0) { return false ; } else { arr[i]=arr[i]/diff; } } // If array represents AP, it must be a // permutation of numbers from 0 to n-1. // Check this using counting sort. if (countingsort(arr,n)) return true ; else return false ; } // 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 Pushpesh Raj } |
Java
// Java program to check if a given array // can form arithmetic progression import java.io.*; class GFG { // Checking if array is permutation // of 0 to n-1 using counting sort static boolean countingsort( int arr[], int n) { int [] count = new int [n]; for ( int i = 0 ; i < n; i++) count[i] = 0 ; // Counting the frequency for ( int i = 0 ; i < n; i++) { count[arr[i]]++; } // Check if each frequency is 1 only for ( int i = 0 ; i <= n- 1 ; i++) { if (count[i] != 1 ) return false ; } return true ; } // Returns true if a permutation of arr[0..n-1] // can form arithmetic progression static boolean checkIsAP( int arr[], int n) { int smallest = Integer.MAX_VALUE, second_smallest = Integer.MAX_VALUE ; for ( int i = 0 ; i < n; i++) { // Find the smallest 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]; } // Find the difference between smallest and second // smallest int diff = second_smallest - smallest; for ( int i = 0 ; i < n; i++) { arr[i] = arr[i] - smallest; } for ( int i = 0 ; i < n; i++) { if (arr[i] % diff != 0 ) { return false ; } else { arr[i] = arr[i]/diff; } } // If array represents AP, it must be a // permutation of numbers from 0 to n-1. // Check this using counting sort. if (countingsort(arr,n)) return true ; else return false ; } // 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 Utkarsh |
Python3
# Python program to check if a given array # can form arithmetic progression import sys # Checking if array is permutation # of 0 to n-1 using counting sort def countingsort( arr, n): count = [ 0 ] * n; # Counting the frequency for i in range ( 0 , n): count[arr[i]] + = 1 ; # Check if each frequency is 1 only for i in range ( 0 , n - 1 ): if (count[i] ! = 1 ): return False ; return True ; # Returns true if a permutation of arr[0..n-1] # can form arithmetic progression def checkIsAP( arr, n): smallest = sys.maxsize; second_smallest = sys.maxsize; for i in range ( 0 ,n): # Find the smallest and # update second smallest if (arr[i] < smallest) : second_smallest = smallest; smallest = arr[i]; # Find second smallest elif (arr[i] ! = smallest and arr[i] < second_smallest): second_smallest = arr[i]; # Find the difference between smallest and second # smallest diff = second_smallest - smallest; for i in range ( 0 ,n): arr[i] = arr[i] - smallest; for i in range ( 0 ,n): if (arr[i] % diff! = 0 ): return False ; else : arr[i] = ( int )(arr[i] / diff); # If array represents AP, it must be a # permutation of numbers from 0 to n-1. # Check this using counting sort. if (countingsort(arr,n)): return True ; else : return False ; # Driven Program arr = [ 20 , 15 , 5 , 0 , 10 ]; n = len (arr); if (checkIsAP(arr, n)): print ( "Yes" ); else : print ( "NO" ); # This code is contributed by ratiagrawal. |
Javascript
// Javascript program to check if a given array // can form arithmetic progression // Checking if array is permutation // of 0 to n-1 using counting sort function countingsort( arr, n) { let count= new Array(n).fill(0); // Counting the frequency for (let i = 0; i < n; i++) { count[arr[i]]++; } // Check if each frequency is 1 only for (let i = 0; i <= n-1; i++) { if (count[i] != 1) return false ; } return true ; } // Returns true if a permutation of arr[0..n-1] // can form arithmetic progression function checkIsAP( arr, n) { let smallest = Number.MAX_SAFE_INTEGER, second_smallest = Number.MAX_SAFE_INTEGER; for (let i = 0; i < n; i++) { // Find the smallest 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]; } // Find the difference between smallest and second // smallest let diff = second_smallest - smallest; for (let i = 0; i < n; i++) { arr[i]=arr[i]-smallest; } for (let i=0;i<n;i++) { if (arr[i]%diff!=0) { return false ; } else { arr[i]=arr[i]/diff; } } // If array represents AP, it must be a // permutation of numbers from 0 to n-1. // Check this using counting sort. if (countingsort(arr,n)) return true ; else return false ; } // Driven Program let arr = [20, 15, 5, 0, 10 ]; let n = arr.length; (checkIsAP(arr, n)) ? (console.log( "Yes\n" )) : (console.log( "No\n" )); // // This code was contributed by poojaagrawal2. |
C#
using System; class GFG { // Checking if array is permutation // of 0 to n-1 using counting sort static bool CountingSort( int [] arr, int n) { // Counting the frequency int [] count = new int [n]; for ( int i = 0; i < n; i++) { count[arr[i]]++; } // Check if each frequency is 1 only for ( int i = 0; i <= n - 1; i++) { if (count[i] != 1) { return false ; } } return true ; } // Returns true if a permutation of arr[0..n-1] // can form arithmetic progression static bool CheckIsAP( int [] arr, int n) { // Find the smallest and // update second smallest int smallest = int .MaxValue; int secondSmallest = int .MaxValue; for ( int i = 0; i < n; i++) { if (arr[i] < smallest) { secondSmallest = smallest; smallest = arr[i]; } else if (arr[i] != smallest && arr[i] < secondSmallest) { secondSmallest = arr[i]; } } int diff = secondSmallest - smallest; for ( int i = 0; i < n; i++) { arr[i] = arr[i] - smallest; } for ( int i = 0; i < n; i++) { if (arr[i] % diff != 0) { return false ; } else { arr[i] = arr[i] / diff; } } // If array represents AP, it must be a // permutation of numbers from 0 to n-1. // Check this using counting sort. if (CountingSort(arr, n)) { return true ; } else { return false ; } } // Driven Program static void Main( string [] args) { int [] arr = new int [] { 20, 15, 5, 0, 10 }; int n = arr.Length; Console.WriteLine(CheckIsAP(arr, n) ? "Yes" : "No" ); } } |
Yes
Time Complexity – O(n)
Auxiliary Space – O(n)
Method 5( Hashing with Single Pass)
The basic idea is to find the common difference of the AP by finding out the maximum and the minimum element of the array. After that start from the maximum value and keep on decreasing the value by the common difference alongside checking that whether this new value is present in the hashmap or not . If at any point the value isn’t present in the hashset , break the loop . The ideal situation after the loop breaking is that all n elements have been covered and if yes , then return true else return false.
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> |
true
Time Complexity – O(n)
Auxiliary Space – O(n)