Kontrollera om aritmetisk progression kan bildas från den givna matrisen
Prova det på GfG Practice 
Produktion
Produktion
Med tanke på en mängd n heltal. Uppgiften är att kontrollera om en aritmetisk progression kan bildas med alla givna element. Om möjligt skriv ut 'Ja' annars skriv ut 'Nej'.
Exempel:
Ingång: arr[] = {0 12 4 8}
Utgång: Ja
Ordna om given matris som {0 4 8 12} som bildar en aritmetisk fortsättning.
Ingång: arr[] = {12 40 11 20}
Utgång: Inga
Använda sortering - O(n log n) tid
Tanken är att sortera den givna arrayen. Kontrollera efter sortering om skillnaderna mellan på varandra följande element är samma eller inte. Om alla skillnader är samma aritmetisk progression är möjlig. Vänligen hänvisa - Program för att kontrollera aritmetisk progression för genomförandet av detta tillvägagångssätt.
Använda räknesortering - O(n) Tid och O(n) Mellanrum
Vi kan minska det utrymme som krävs i metod 3 om en given array kan modifieras.
- Hitta minsta och näst minsta element.
- Hitta d = näst_minst - minsta
- Subtrahera minsta element från alla element.
- Om nu en given array representerar AP bör alla element ha formen i*d där i varierar från 0 till n-1.
- En efter en dela alla reducerade element med d. Om något element inte är delbart med d returneras false.
- Om nu array representerar AP måste det vara en permutation av tal från 0 till n-1. Vi kan enkelt kontrollera detta med hjälp av räknesortering.
Nedan är implementeringen av denna metod:
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.
Produktion
Yes
Tidskomplexitet - O(n)
Hjälputrymme - O(n)
Hashing med Single Pass - O(n) Time och O(n) Space
Den grundläggande idén är att hitta den gemensamma skillnaden mellan AP genom att ta reda på det maximala och det minsta elementet i arrayen. Börja sedan från det maximala värdet och fortsätt att minska värdet med den gemensamma skillnaden tillsammans med att kontrollera om detta nya värde finns i hashmapen eller inte. Om värdet vid något tillfälle inte finns i hashsetet, bryt slingan . Den ideala situationen efter slingbrytningen är att alla n element har täckts och om ja returnerar true annars returnerar 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 ))
Produktion
trueSkapa frågesport
