Given an array A[] of size N. Solve Q queries. Find the product in the range [L, R] under modulo P ( P is Prime).
Examples:
Input : A[] = {1, 2, 3, 4, 5, 6}
L = 2, R = 5, P = 229
Output : 120
Input : A[] = {1, 2, 3, 4, 5, 6},
L = 2, R = 5, P = 113
Output : 7
Brute Force
For each of the queries, traverse each element in the range [L, R] and calculate the product under modulo P. This will answer each query in O(N).
PHP
<?php // Product in range Queries in O(N) // Function to calculate // Product in the given range. function calculateProduct($A, $L, $R, $P) { // As our array is 0 based as // and L and R are given as 1 // based index. $L = $L - 1; $R = $R - 1; $ans = 1; for ($i = $L; $i <= $R; $i++) { $ans = $ans * $A[$i]; $ans = $ans % $P; } return $ans; } // Driver code $A = array( 1, 2, 3, 4, 5, 6 ); $P = 229; $L = 2; $R = 5; echo calculateProduct($A, $L, $R, $P)," " ; $L = 1; $R = 3; echo calculateProduct($A, $L, $R, $P)," " ; // This code is contributed by ajit. ?> |
Output :
120 6
Please refer complete article on Products of ranges in an array for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
