Patikrinkite, ar iš pateikto masyvo galima sudaryti aritmetinę progresiją
Išbandykite „GfG Practice“. 
Išvestis
Išvestis
Atsižvelgiant į masyvą n sveikieji skaičiai. Užduotis – patikrinti, ar naudojant visus pateiktus elementus galima sudaryti aritmetinę progresiją. Jei įmanoma, spausdinkite „Taip“, kitaip spausdinkite „Ne“.
Pavyzdžiai:
Įvestis: arr[] = {0 12 4 8}
Išvestis: Taip
Pertvarkykite pateiktą masyvą į {0 4 8 12}, kuris sudaro aritmetinę progresiją.
Įvestis: arr[] = {12 40 11 20}
Išvestis: Nr
Rūšiavimo naudojimas – O(n Log n) laikas
Idėja yra surūšiuoti pateiktą masyvą. Po rūšiavimo patikrinkite, ar skirtumai tarp nuoseklių elementų yra vienodi, ar ne. Jei visi skirtumai yra vienodi, galima aritmetinė progresija. Žiūrėkite - Programa, skirta patikrinti aritmetinę progresiją šio požiūrio įgyvendinimui.
Naudojant skaičiavimo rūšiavimą - O(n) laikas ir O(n) erdvė
Galime sumažinti erdvę, reikalingą 3 metodui, jei galima pakeisti nurodytą masyvą.
- Raskite mažiausius ir antrą mažiausią elementus.
- Rasti d = antras_mažiausias – mažiausias
- Iš visų elementų atimkite mažiausią elementą.
- Dabar, jei pateiktas masyvas reiškia AP, visi elementai turėtų būti i*d formos, kur i svyruoja nuo 0 iki n-1.
- Padalinkite visus redukuotus elementus po vieną su d. Jei kuris nors elementas nedalomas iš d, grąžinama false.
- Dabar, jei masyvas reiškia AP, tai turi būti skaičių permutacija nuo 0 iki n-1. Tai galime lengvai patikrinti naudodami skaičiavimo rūšiavimą.
Žemiau pateikiamas šio metodo įgyvendinimas:
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.
Išvestis
Yes
Laiko sudėtingumas – O(n)
Pagalbinė erdvė – O(n)
Maišos keitimas su vienu leidimu – O(n) laikas ir O(n) erdvė
Pagrindinė idėja yra rasti bendrą AP skirtumą, išsiaiškinus didžiausią ir mažiausią masyvo elementą. Po to pradėkite nuo didžiausios vertės ir toliau mažinkite reikšmę bendru skirtumu, kartu patikrindami, ar ši nauja reikšmė yra maišos diagramoje, ar ne. Jei bet kuriuo momentu reikšmės maišos rinkinyje nėra, nutraukite kilpą. Ideali situacija po ciklo nutraukimo yra ta, kad visi n elementų yra padengti, o jei taip, tada grąžinkite teisingą, kitaip grąžinkite false.
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 ))
Išvestis
trueSukurti viktoriną
