Række LCM-forespørgsler
Givet en matrix arr[] af heltal af størrelse N og en matrix af Q-forespørgsler forespørgsel[], hvor hver forespørgsel er af typen [L R], der angiver området fra indeks L til indeks R, er opgaven at finde LCM for alle numrene i området for alle forespørgslerne.
Eksempler:
Input: arr[] = {5 7 5 2 10 12 11 17 14 1 44}
forespørgsel[] = {{2 5} {5 10} {0 10}}
Produktion: 6015708 78540
Forklaring: I den første forespørgsel LCM(5 2 10 12) = 60
I den anden forespørgsel LCM(12 11 17 14 1 44) = 15708
I den sidste forespørgsel LCM(5 7 5 2 10 12 11 17 14 1 44) = 78540Input: arr[] = {2 4 8 16} forespørgsel[] = {{2 3} {0 1}}
Produktion: 16 4
Naiv tilgang: Tilgangen er baseret på følgende matematiske idé:
Matematisk LCM(l r) = LCM(arr[l] arr[l+1] . . . arr[r-1] arr[r]) og
LCM(a b) = (a*b) / GCD(ab)
Så gå gennem arrayet for hver forespørgsel og beregn svaret ved at bruge ovenstående formel for LCM.
Tidskompleksitet: O(N * Q)
Hjælpeplads: O(1)
RangeLCM-forespørgsler ved hjælp af Segmenttræ :
Da antallet af forespørgsler kan være stort, ville den naive løsning være upraktisk. Denne tid kan reduceres
Der er ingen opdateringshandling i dette problem. Så vi kan indledningsvis bygge et segmenttræ og bruge det til at besvare forespørgslerne i logaritmisk tid.
Hver node i træet skal gemme LCM-værdien for det pågældende segment, og vi kan bruge den samme formel som ovenfor til at kombinere segmenterne.
Følg nedenstående trin for at implementere ideen:
- Byg et segmenttræ fra det givne array.
- Gå gennem forespørgslerne. For hver forespørgsel:
- Find det pågældende område i segmenttræet.
- Brug ovennævnte formel til at kombinere segmenterne og beregne LCM for dette område.
- Udskriv svaret for det segment.
Nedenfor er implementeringen af ovenstående tilgang.
C++ // LCM of given range queries using Segment Tree #include using namespace std ; #define MAX 1000 // allocate space for tree int tree [ 4 * MAX ]; // declaring the array globally int arr [ MAX ]; // Function to return gcd of a and b int gcd ( int a int b ) { if ( a == 0 ) return b ; return gcd ( b % a a ); } // utility function to find lcm int lcm ( int a int b ) { return a * b / gcd ( a b ); } // Function to build the segment tree // Node starts beginning index of current subtree. // start and end are indexes in arr[] which is global void build ( int node int start int end ) { // If there is only one element in current subarray if ( start == end ) { tree [ node ] = arr [ start ]; return ; } int mid = ( start + end ) / 2 ; // build left and right segments build ( 2 * node start mid ); build ( 2 * node + 1 mid + 1 end ); // build the parent int left_lcm = tree [ 2 * node ]; int right_lcm = tree [ 2 * node + 1 ]; tree [ node ] = lcm ( left_lcm right_lcm ); } // Function to make queries for array range )l r). // Node is index of root of current segment in segment // tree (Note that indexes in segment tree begin with 1 // for simplicity). // start and end are indexes of subarray covered by root // of current segment. int query ( int node int start int end int l int r ) { // Completely outside the segment returning // 1 will not affect the lcm; if ( end < l || start > r ) return 1 ; // completely inside the segment if ( l <= start && r >= end ) return tree [ node ]; // partially inside int mid = ( start + end ) / 2 ; int left_lcm = query ( 2 * node start mid l r ); int right_lcm = query ( 2 * node + 1 mid + 1 end l r ); return lcm ( left_lcm right_lcm ); } // driver function to check the above program int main () { // initialize the array arr [ 0 ] = 5 ; arr [ 1 ] = 7 ; arr [ 2 ] = 5 ; arr [ 3 ] = 2 ; arr [ 4 ] = 10 ; arr [ 5 ] = 12 ; arr [ 6 ] = 11 ; arr [ 7 ] = 17 ; arr [ 8 ] = 14 ; arr [ 9 ] = 1 ; arr [ 10 ] = 44 ; // build the segment tree build ( 1 0 10 ); // Now we can answer each query efficiently // Print LCM of (2 5) cout < < query ( 1 0 10 2 5 ) < < endl ; // Print LCM of (5 10) cout < < query ( 1 0 10 5 10 ) < < endl ; // Print LCM of (0 10) cout < < query ( 1 0 10 0 10 ) < < endl ; return 0 ; }
Java // LCM of given range queries // using Segment Tree class GFG { static final int MAX = 1000 ; // allocate space for tree static int tree [] = new int [ 4 * MAX ] ; // declaring the array globally static int arr [] = new int [ MAX ] ; // Function to return gcd of a and b static int gcd ( int a int b ) { if ( a == 0 ) { return b ; } return gcd ( b % a a ); } // utility function to find lcm static int lcm ( int a int b ) { return a * b / gcd ( a b ); } // Function to build the segment tree // Node starts beginning index // of current subtree. start and end // are indexes in arr[] which is global static void build ( int node int start int end ) { // If there is only one element // in current subarray if ( start == end ) { tree [ node ] = arr [ start ] ; return ; } int mid = ( start + end ) / 2 ; // build left and right segments build ( 2 * node start mid ); build ( 2 * node + 1 mid + 1 end ); // build the parent int left_lcm = tree [ 2 * node ] ; int right_lcm = tree [ 2 * node + 1 ] ; tree [ node ] = lcm ( left_lcm right_lcm ); } // Function to make queries for // array range )l r). Node is index // of root of current segment in segment // tree (Note that indexes in segment // tree begin with 1 for simplicity). // start and end are indexes of subarray // covered by root of current segment. static int query ( int node int start int end int l int r ) { // Completely outside the segment returning // 1 will not affect the lcm; if ( end < l || start > r ) { return 1 ; } // completely inside the segment if ( l <= start && r >= end ) { return tree [ node ] ; } // partially inside int mid = ( start + end ) / 2 ; int left_lcm = query ( 2 * node start mid l r ); int right_lcm = query ( 2 * node + 1 mid + 1 end l r ); return lcm ( left_lcm right_lcm ); } // Driver code public static void main ( String [] args ) { // initialize the array arr [ 0 ] = 5 ; arr [ 1 ] = 7 ; arr [ 2 ] = 5 ; arr [ 3 ] = 2 ; arr [ 4 ] = 10 ; arr [ 5 ] = 12 ; arr [ 6 ] = 11 ; arr [ 7 ] = 17 ; arr [ 8 ] = 14 ; arr [ 9 ] = 1 ; arr [ 10 ] = 44 ; // build the segment tree build ( 1 0 10 ); // Now we can answer each query efficiently // Print LCM of (2 5) System . out . println ( query ( 1 0 10 2 5 )); // Print LCM of (5 10) System . out . println ( query ( 1 0 10 5 10 )); // Print LCM of (0 10) System . out . println ( query ( 1 0 10 0 10 )); } } // This code is contributed by 29AjayKumar
Python # LCM of given range queries using Segment Tree MAX = 1000 # allocate space for tree tree = [ 0 ] * ( 4 * MAX ) # declaring the array globally arr = [ 0 ] * MAX # Function to return gcd of a and b def gcd ( a : int b : int ): if a == 0 : return b return gcd ( b % a a ) # utility function to find lcm def lcm ( a : int b : int ): return ( a * b ) // gcd ( a b ) # Function to build the segment tree # Node starts beginning index of current subtree. # start and end are indexes in arr[] which is global def build ( node : int start : int end : int ): # If there is only one element # in current subarray if start == end : tree [ node ] = arr [ start ] return mid = ( start + end ) // 2 # build left and right segments build ( 2 * node start mid ) build ( 2 * node + 1 mid + 1 end ) # build the parent left_lcm = tree [ 2 * node ] right_lcm = tree [ 2 * node + 1 ] tree [ node ] = lcm ( left_lcm right_lcm ) # Function to make queries for array range )l r). # Node is index of root of current segment in segment # tree (Note that indexes in segment tree begin with 1 # for simplicity). # start and end are indexes of subarray covered by root # of current segment. def query ( node : int start : int end : int l : int r : int ): # Completely outside the segment # returning 1 will not affect the lcm; if end < l or start > r : return 1 # completely inside the segment if l <= start and r >= end : return tree [ node ] # partially inside mid = ( start + end ) // 2 left_lcm = query ( 2 * node start mid l r ) right_lcm = query ( 2 * node + 1 mid + 1 end l r ) return lcm ( left_lcm right_lcm ) # Driver Code if __name__ == '__main__' : # initialize the array arr [ 0 ] = 5 arr [ 1 ] = 7 arr [ 2 ] = 5 arr [ 3 ] = 2 arr [ 4 ] = 10 arr [ 5 ] = 12 arr [ 6 ] = 11 arr [ 7 ] = 17 arr [ 8 ] = 14 arr [ 9 ] = 1 arr [ 10 ] = 44 # build the segment tree build ( 1 0 10 ) # Now we can answer each query efficiently # Print LCM of (2 5) print ( query ( 1 0 10 2 5 )) # Print LCM of (5 10) print ( query ( 1 0 10 5 10 )) # Print LCM of (0 10) print ( query ( 1 0 10 0 10 )) # This code is contributed by # sanjeev2552
C# // LCM of given range queries // using Segment Tree using System ; using System.Collections.Generic ; class GFG { static readonly int MAX = 1000 ; // allocate space for tree static int [] tree = new int [ 4 * MAX ]; // declaring the array globally static int [] arr = new int [ MAX ]; // Function to return gcd of a and b static int gcd ( int a int b ) { if ( a == 0 ) { return b ; } return gcd ( b % a a ); } // utility function to find lcm static int lcm ( int a int b ) { return a * b / gcd ( a b ); } // Function to build the segment tree // Node starts beginning index // of current subtree. start and end // are indexes in []arr which is global static void build ( int node int start int end ) { // If there is only one element // in current subarray if ( start == end ) { tree [ node ] = arr [ start ]; return ; } int mid = ( start + end ) / 2 ; // build left and right segments build ( 2 * node start mid ); build ( 2 * node + 1 mid + 1 end ); // build the parent int left_lcm = tree [ 2 * node ]; int right_lcm = tree [ 2 * node + 1 ]; tree [ node ] = lcm ( left_lcm right_lcm ); } // Function to make queries for // array range )l r). Node is index // of root of current segment in segment // tree (Note that indexes in segment // tree begin with 1 for simplicity). // start and end are indexes of subarray // covered by root of current segment. static int query ( int node int start int end int l int r ) { // Completely outside the segment // returning 1 will not affect the lcm; if ( end < l || start > r ) { return 1 ; } // completely inside the segment if ( l <= start && r >= end ) { return tree [ node ]; } // partially inside int mid = ( start + end ) / 2 ; int left_lcm = query ( 2 * node start mid l r ); int right_lcm = query ( 2 * node + 1 mid + 1 end l r ); return lcm ( left_lcm right_lcm ); } // Driver code public static void Main ( String [] args ) { // initialize the array arr [ 0 ] = 5 ; arr [ 1 ] = 7 ; arr [ 2 ] = 5 ; arr [ 3 ] = 2 ; arr [ 4 ] = 10 ; arr [ 5 ] = 12 ; arr [ 6 ] = 11 ; arr [ 7 ] = 17 ; arr [ 8 ] = 14 ; arr [ 9 ] = 1 ; arr [ 10 ] = 44 ; // build the segment tree build ( 1 0 10 ); // Now we can answer each query efficiently // Print LCM of (2 5) Console . WriteLine ( query ( 1 0 10 2 5 )); // Print LCM of (5 10) Console . WriteLine ( query ( 1 0 10 5 10 )); // Print LCM of (0 10) Console . WriteLine ( query ( 1 0 10 0 10 )); } } // This code is contributed by Rajput-Ji
JavaScript < script > // LCM of given range queries using Segment Tree const MAX = 1000 // allocate space for tree var tree = new Array ( 4 * MAX ); // declaring the array globally var arr = new Array ( MAX ); // Function to return gcd of a and b function gcd ( a b ) { if ( a == 0 ) return b ; return gcd ( b % a a ); } //utility function to find lcm function lcm ( a b ) { return Math . floor ( a * b / gcd ( a b )); } // Function to build the segment tree // Node starts beginning index of current subtree. // start and end are indexes in arr[] which is global function build ( node start end ) { // If there is only one element in current subarray if ( start == end ) { tree [ node ] = arr [ start ]; return ; } let mid = Math . floor (( start + end ) / 2 ); // build left and right segments build ( 2 * node start mid ); build ( 2 * node + 1 mid + 1 end ); // build the parent let left_lcm = tree [ 2 * node ]; let right_lcm = tree [ 2 * node + 1 ]; tree [ node ] = lcm ( left_lcm right_lcm ); } // Function to make queries for array range )l r). // Node is index of root of current segment in segment // tree (Note that indexes in segment tree begin with 1 // for simplicity). // start and end are indexes of subarray covered by root // of current segment. function query ( node start end l r ) { // Completely outside the segment returning // 1 will not affect the lcm; if ( end < l || start > r ) return 1 ; // completely inside the segment if ( l <= start && r >= end ) return tree [ node ]; // partially inside let mid = Math . floor (( start + end ) / 2 ); let left_lcm = query ( 2 * node start mid l r ); let right_lcm = query ( 2 * node + 1 mid + 1 end l r ); return lcm ( left_lcm right_lcm ); } //driver function to check the above program //initialize the array arr [ 0 ] = 5 ; arr [ 1 ] = 7 ; arr [ 2 ] = 5 ; arr [ 3 ] = 2 ; arr [ 4 ] = 10 ; arr [ 5 ] = 12 ; arr [ 6 ] = 11 ; arr [ 7 ] = 17 ; arr [ 8 ] = 14 ; arr [ 9 ] = 1 ; arr [ 10 ] = 44 ; // build the segment tree build ( 1 0 10 ); // Now we can answer each query efficiently // Print LCM of (2 5) document . write ( query ( 1 0 10 2 5 ) + '
' ); // Print LCM of (5 10) document . write ( query ( 1 0 10 5 10 ) + '
' ); // Print LCM of (0 10) document . write ( query ( 1 0 10 0 10 ) + '
' ); // This code is contributed by Manoj. < /script>
Produktion
60 15708 78540
Tidskompleksitet: O(Log N * Log n), hvor N er antallet af elementer i arrayet. Den anden log n angiver den tid, der kræves for at finde LCM. Denne tidskompleksitet er for hver forespørgsel. Den samlede tidskompleksitet er O(N + Q*Log N*log n), dette skyldes, at der kræves O(N) tid for at bygge træet og derefter besvare forespørgslerne.
Hjælpeplads: O(N) hvor N er antallet af elementer i arrayet. Denne plads er påkrævet til opbevaring af segmenttræet.
Relateret emne: Segmenttræ
Fremgangsmåde #2: Brug af matematik
Vi definerer først en hjælpefunktion lcm() for at beregne det mindste fælles multiplum af to tal. Derefter itererer vi for hver forespørgsel gennem subarrayet af arr defineret af forespørgselsområdet og beregner LCM ved hjælp af lcm()-funktionen. LCM-værdien gemmes i en liste, der returneres som det endelige resultat.
Segmenttræ
Fremgangsmåde #2: Brug af matematik
Algoritme
Segmenttræ
Fremgangsmåde #2: Brug af matematik
1. Definer en hjælpefunktion lcm(a b) til at beregne det mindste fælles multiplum af to tal.
2. Definer en funktion range_lcm_queries(arr-forespørgsler), der tager en array-arr og en liste over forespørgselsområder-forespørgsler som input.
3. Opret en tom listeresultater for at gemme LCM-værdierne for hver forespørgsel.
4. Udtræk venstre og højre indeks l og r for hver forespørgsel i forespørgsler.
5. Indstil lcm_val til værdien af arr[l].
6. For hvert indeks i i området l+1 til r opdater lcm_val til at være LCM for lcm_val og arr[i] ved hjælp af lcm()-funktionen.
7. Tilføj lcm_val til resultatlisten.
8. Returner resultatlisten.
Fremgangsmåde #2: Brug af matematik
C++ Java #include
Python /*package whatever //do not write package name here */ import java.util.ArrayList ; import java.util.List ; public class GFG { public static int gcd ( int a int b ) { if ( b == 0 ) return a ; return gcd ( b a % b ); } public static int lcm ( int a int b ) { return a * b / gcd ( a b ); } public static List < Integer > rangeLcmQueries ( List < Integer > arr List < int []> queries ) { List < Integer > results = new ArrayList <> (); for ( int [] query : queries ) { int l = query [ 0 ] ; int r = query [ 1 ] ; int lcmVal = arr . get ( l ); for ( int i = l + 1 ; i <= r ; i ++ ) { lcmVal = lcm ( lcmVal arr . get ( i )); } results . add ( lcmVal ); } return results ; } public static void main ( String [] args ) { List < Integer > arr = List . of ( 5 7 5 2 10 12 11 17 14 1 44 ); List < int []> queries = List . of ( new int [] { 2 5 } new int [] { 5 10 } new int [] { 0 10 }); List < Integer > results = rangeLcmQueries ( arr queries ); for ( int result : results ) { System . out . print ( result + ' ' ); } System . out . println (); } }
C# from math import gcd def lcm ( a b ): return a * b // gcd ( a b ) def range_lcm_queries ( arr queries ): results = [] for query in queries : l r = query lcm_val = arr [ l ] for i in range ( l + 1 r + 1 ): lcm_val = lcm ( lcm_val arr [ i ]) results . append ( lcm_val ) return results # example usage arr = [ 5 7 5 2 10 12 11 17 14 1 44 ] queries = [( 2 5 ) ( 5 10 ) ( 0 10 )] print ( range_lcm_queries ( arr queries )) # output: [60 15708 78540]
JavaScript using System ; using System.Collections.Generic ; class GFG { // Function to calculate the greatest common divisor (GCD) // using Euclidean algorithm static int GCD ( int a int b ) { if ( b == 0 ) return a ; return GCD ( b a % b ); } // Function to calculate the least common multiple (LCM) // using GCD static int LCM ( int a int b ) { return a * b / GCD ( a b ); } static List < int > RangeLcmQueries ( List < int > arr List < Tuple < int int >> queries ) { List < int > results = new List < int > (); foreach ( var query in queries ) { int l = query . Item1 ; int r = query . Item2 ; int lcmVal = arr [ l ]; for ( int i = l + 1 ; i <= r ; i ++ ) { lcmVal = LCM ( lcmVal arr [ i ]); } results . Add ( lcmVal ); } return results ; } static void Main () { List < int > arr = new List < int > { 5 7 5 2 10 12 11 17 14 1 44 }; List < Tuple < int int >> queries = new List < Tuple < int int >> { Tuple . Create ( 2 5 ) Tuple . Create ( 5 10 ) Tuple . Create ( 0 10 ) }; List < int > results = RangeLcmQueries ( arr queries ); foreach ( var result in results ) { Console . Write ( result + ' ' ); } Console . WriteLine (); } }
// JavaScript Program for the above approach // function to find out gcd function gcd ( a b ) { if ( b === 0 ) { return a ; } return gcd ( b a % b ); } // function to find out lcm function lcm ( a b ) { return ( a * b ) / gcd ( a b ); } function rangeLcmQueries ( arr queries ) { const results = []; for ( const query of queries ) { const l = query [ 0 ]; const r = query [ 1 ]; let lcmVal = arr [ l ]; for ( let i = l + 1 ; i <= r ; i ++ ) { lcmVal = lcm ( lcmVal arr [ i ]); } results . push ( lcmVal ); } return results ; } // Driver code to test above function const arr = [ 5 7 5 2 10 12 11 17 14 1 44 ]; const queries = [[ 2 5 ] [ 5 10 ] [ 0 10 ]]; const results = rangeLcmQueries ( arr queries ); for ( const result of results ) { console . log ( result + ' ' ); } console . log (); // THIS CODE IS CONTRIBUTED BY PIYUSH AGARWAL
Produktion
[60 15708 78540]
Tidskompleksitet: O(log(min(ab))). For hvert forespørgselsinterval itererer vi gennem en subarray af størrelse O(n), hvor n er længden af arr. Derfor er tidskompleksiteten af den overordnede funktion O(qn log(min(a_i))), hvor q er antallet af forespørgsler, og a_i er det i-te element i arr.
Rumkompleksitet: O(1), da vi kun gemmer nogle få heltal ad gangen. Den plads, der bruges af input-arr og forespørgsler, tages ikke i betragtning.
