Ellenőrizze, hogy az adott tömbből aritmetikai progresszió képezhető-e
Próbáld ki a GfG Practice-n 
Kimenet
Kimenet
Adott egy tömb n egész számok. A feladat annak ellenőrzése, hogy az összes megadott elem felhasználásával alkotható-e aritmetikai sorozat. Ha lehetséges, nyomtasson „Igen”-t, ellenkező esetben „Nem”-t.
Példák:
Bemenet: arr[] = {0 12 4 8}
Kimenet: Igen
Rendezzük át az adott tömböt a következőre: 0 4 8 12}, ami aritmetikai progressziót képez.
Bemenet: arr[] = {12 40 11 20}
Kimenet: Nem
Rendezés használata - O(n Log n) idő
Az ötlet az adott tömb rendezése. A rendezés után ellenőrizze, hogy az egymást követő elemek közötti különbségek azonosak-e vagy sem. Ha minden különbség azonos, lehetséges az aritmetikai haladás. Kérjük, olvassa el - Program az aritmetikai haladás ellenőrzésére ennek a megközelítésnek a megvalósításához.
Számláló rendezés használata - O(n) idő és O(n) tér
A 3. módszerben csökkenthetjük a területigényt, ha az adott tömb módosítható.
- Keresse meg a legkisebb és a második legkisebb elemeket.
- Keresse meg d = második_legkisebb – legkisebb
- Vonja ki a legkisebb elemet az összes elemből.
- Ha az adott tömb AP-t képvisel, minden elemnek i*d formájúnak kell lennie, ahol i 0 és n-1 között változik.
- Egyenként osszuk el az összes redukált elemet d-vel. Ha bármely elem nem osztható d-vel, akkor hamis értéket ad vissza.
- Ha a tömb az AP-t képviseli, akkor számok permutációjának kell lennie 0-tól n-1-ig. Ezt egyszerűen ellenőrizhetjük a számláló rendezés segítségével.
Az alábbiakban bemutatjuk ennek a módszernek a megvalósítását:
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.
Kimenet
Yes
Időbonyolultság – O(n)
Segédtér – O(n)
Kivonatolás egyszeri lépéssel – O(n) idő és O(n) tér
Az alapötlet az, hogy megtaláljuk az AP közös különbségét a tömb maximális és minimális elemének meghatározásával. Ezután kezdje a maximális értéktől, és folytassa az érték csökkentését a közös különbséggel, miközben ellenőrizze, hogy ez az új érték jelen van-e a hashmapban vagy sem. Ha az érték bármely ponton nincs jelen a hashsetben, szakítsa meg a hurkot. Az ideális helyzet a huroktörés után az, hogy mind az n elemet lefedjük, és ha igen, akkor adjuk vissza az igazat, ellenkező esetben a false értéket adjuk vissza.
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 ))
Kimenet
trueKvíz létrehozása
