💡 Problem Formulation: Range LCM queries involve finding the Least Common Multiple (LCM) of a range of numbers within an array. For example, given an array [1, 2, 3, 4, 5] and a query range from index 1 to 3, the desired output is the LCM of numbers 2, 3, and 4, which is 12.
Method 1: Naive Approach Using Iteration
This method involves a brute force approach for calculating the LCM of a range by iterating through the entire range for each query. The LCM is calculated using the greatest common divisor (GCD) method for every pair of numbers.
Here’s an example:
from math import gcd
def lcm(a, b):
return a * b // gcd(a, b)
def range_lcm(arr, query):
range_lcm = arr[query[0]]
for i in range(query[0]+1, query[1]+1):
range_lcm = lcm(range_lcm, arr[i])
return range_lcm
array = [1, 2, 3, 4, 5]
query_range = (1, 3)
print(range_lcm(array, query_range))Output: 12
This function calculates the LCM of a range of elements in an array by iterating through it. It uses a helper function lcm() to find the LCM of two numbers, and progressively calculates the LCM for the entire range.
Method 2: Preprocessing with Segment Tree
Segment Tree is a tree data structure that allows for storing information about array intervals efficiently. This method involves preprocessing the array with a Segment Tree where each node stores the LCM of an interval, thus optimizing the LCM queries.
Here’s an example:
from math import gcd
def lcm(a, b):
return a * b // gcd(a, b)
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n)
self.build(data, 1, 0, self.n - 1)
def build(self, data, v, tl, tr):
if tl == tr:
self.tree[v] = data[tl]
else:
tm = (tl + tr) // 2
self.build(data, v*2, tl, tm)
self.build(data, v*2+1, tm+1, tr)
self.tree[v] = lcm(self.tree[v*2], self.tree[v*2+1])
def query(self, v, tl, tr, l, r):
if l > r:
return 1
if l == tl and r == tr:
return self.tree[v]
tm = (tl + tr) // 2
return lcm(self.query(v*2, tl, tm, l, min(r, tm)),
self.query(v*2+1, tm+1, tr, max(l, tm+1), r))
data = [1, 2, 3, 4, 5]
seg_tree = SegmentTree(data)
print(seg_tree.query(1, 0, len(data)-1, 1, 3))Output: 12
The SegmentTree class is initialized with an input array and creates the tree structure with the appropriate LCM values. The query() method efficiently retrieves the LCM for any given range.
Method 3: Preprocessing with Sparse Table
The Sparse Table algorithm is another preprocessing method that allows for querying the LCM of intervals in an array. It constructs a table where each entry contains the LCM of an interval, which can be combined to produce the LCM of different ranges.
Here’s an example:
from math import gcd, log2, floor
def lcm(a, b):
return a * b // gcd(a, b)
def build_sparsetable(arr):
n = len(arr)
k = floor(log2(n)) + 1
st = [[0] * n for _ in range(k)]
for j in range(n):
st[0][j] = arr[j]
for i in range(1, k):
for j in range(n - (1 << i) + 1):
st[i][j] = lcm(st[i-1][j], st[i-1][j+(1<<(i-1))])
return st
def query_lcm(st, l, r):
ans = 1
j = floor(log2(r - l + 1))
ans = lcm(st[j][l], st[j][r-(1<<j)+1])
return ans
array = [1, 2, 3, 4, 5]
st = build_sparsetable(array)
print(query_lcm(st, 1, 3))Output: 12
This Sparse Table based approach uses dynamic programming to precompute the LCMs of ranges that are of size 2^k, allowing for fast range LCM queries by combining these precomputed values.
Method 4: Dynamic Programming
Dynamic programming method involves precomputing a table with LCMs of all pairs of elements. This allows subsequent queries to get the LCM of any range by just accessing the precomputed values without additional computations.
Here’s an example:
from math import gcd
def lcm(a, b):
return a * b // gcd(a, b)
def precompute_lcm(arr):
n = len(arr)
dp = [[1] * n for _ in range(n)]
for i in range(n):
for j in range(i, n):
if j == i:
dp[i][j] = arr[i]
else:
dp[i][j] = lcm(dp[i][j-1], arr[j])
return dp
def get_range_lcm(dp, l, r):
return dp[l][r]
array = [1, 2, 3, 4, 5]
dp = precompute_lcm(array)
print(get_range_lcm(dp, 1, 3))Output: 12
The function precompute_lcm() creates a 2D array where dp[i][j] stores the LCM of the subarray from index i to j. The function get_range_lcm() then uses this table to find the LCM for any given query range quickly.
Bonus One-Liner Method 5: Functional Approach with Reduce
The functional approach utilizes Python’s functools.reduce() to apply a function of two arguments cumulatively to the range of numbers specified in the query, which in this case is calculating the LCM.
Here’s an example:
from math import gcd from functools import reduce array = [1, 2, 3, 4, 5] query_range = (1, 3) lcm = lambda x, y: x * y // gcd(x, y) result = reduce(lcm, array[query_range[0]:query_range[1]+1]) print(result)
Output: 12
By combining functools.reduce() with a lambda function that computes the LCM, we can efficiently solve the range LCM queries in a concise, one-liner fashion.
Summary/Discussion
- Method 1: Naive Approach. Strengths: Easy to understand and implement. Weaknesses: Inefficient for multiple queries, leading to high time complexity.
- Method 2: Segment Tree. Strengths: Efficient for multiple queries on large data sets. Weaknesses: Complex implementation and more memory usage due to tree structure.
- Method 3: Sparse Table. Strengths: Faster querying after preprocessing. Weaknesses: Slower preprocessing and limited to non-modifiable arrays.
- Method 4: Dynamic Programming. Strengths: Fast retrieval for any range after precomputation. Weaknesses: Requires significant memory for storing precomputed LCMs.
- Bonus Method 5: Functional with Reduce. Strengths: Very concise code, easy readability. Weaknesses: Not as intuitive for those not familiar with functional programming concepts.