Verilen diziden Aritmetik İlerlemenin oluşturulup oluşturulamayacağını kontrol edin
GfG Practice'de deneyin 
Çıkış
Çıkış
Bir dizi göz önüne alındığında N tamsayılar. Görev, verilen tüm öğeler kullanılarak aritmetik bir ilerlemenin oluşturulup oluşturulamayacağını kontrol etmektir. Mümkünse 'Evet' yazdırın, aksi halde 'Hayır' yazdırın.
Örnekler:
Giriş: dizi[] = {0 12 4 8}
Çıkış: Evet
Verilen diziyi aritmetik ilerleme oluşturan {0 4 8 12} olarak yeniden düzenleyin.
Giriş: dizi[] = {12 40 11 20}
Çıkış: HAYIR
Sıralamayı Kullanma - O(n Log n) Zaman
Buradaki fikir verilen diziyi sıralamaktır. Sıralamadan sonra ardışık elemanlar arasındaki farkların aynı olup olmadığını kontrol edin. Tüm farklar aynı ise Aritmetik İlerleme mümkündür. Lütfen bakın - Aritmetik İlerlemeyi Kontrol Etme Programı Bu yaklaşımın uygulanması için.
Sayma sıralamasını kullanma - O(n) Zaman ve O(n) Uzay
Verilen dizi değiştirilebiliyorsa, yöntem 3'te gereken alanı azaltabiliriz.
- En küçük ve ikinci en küçük elemanları bulun.
- d = ikinci_en küçük - en küçük olanı bulun
- En küçük elemanı tüm elemanlardan çıkarın.
- Şimdi, eğer verilen dizi AP'yi temsil ediyorsa, tüm öğeler i*d biçiminde olmalıdır; burada i, 0'dan n-1'e kadar değişir.
- Tüm indirgenmiş elemanları birer birer d ile bölün. Herhangi bir öğe d'ye bölünemiyorsa false değerini döndürür.
- Şimdi eğer dizi AP'yi temsil ediyorsa, 0'dan n-1'e kadar sayıların bir permütasyonu olmalıdır. Sayma sıralamasını kullanarak bunu kolayca kontrol edebiliriz.
Aşağıda bu yöntemin uygulanması yer almaktadır:
C++ // C++ program to check if a given array // can form arithmetic progression #include 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
Python # 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.
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' ); } }
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 ( 'Yesn' )) : ( console . log ( 'Non' )); // // This code was contributed by poojaagrawal2.
Çıkış
Yes
Zaman Karmaşıklığı - O(n)
Yardımcı Alan - O(n)
Tek Geçişli Hashing - O(n) Zaman ve O(n) Uzay
Temel fikir, dizinin maksimum ve minimum elemanlarını bularak AP'nin ortak farkını bulmaktır. Bundan sonra maksimum değerden başlayın ve bu yeni değerin hashmap'te mevcut olup olmadığını kontrol etmenin yanı sıra değeri ortak fark kadar azaltmaya devam edin. Herhangi bir noktada değer hashset'te mevcut değilse döngüyü kırın. Döngünün kırılmasından sonraki ideal durum, tüm n elemanın kapsanması ve eğer evet ise o zaman true değerini döndürme, aksi halde false değerini döndürmedir.
C++ // C++ program for above approach #include 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 TERMS OF AP PRESENT IN THE HASHSET 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 TERMS OF AP PRESENT IN THE HASHSET while ( set . contains ( max )) { count ++ ; max = max - diff ; } if ( count == arr . length ) return true ; return false ; } }
Python 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 TERMS OF AP PRESENT IN THE HASHSET 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 TERMS OF AP PRESENT IN THE HASHSET 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 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 TERMS OF AP PRESENT IN THE HASHSET 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 console . log ( checkIsAP ( arr n ))
Çıkış
trueTest Oluştur
