Problem link: Range Product
Solution:
Given N and K, we have to find how many integers of K subarray has maximum product which starting index of the subarray is minimum. Also all the integers will be power of 2.
So, at first we will store the power of all the integers in an array. Then we will simply use brute force to check for maximum subarray summation (As we took only power, so we will check for summation here).
Why we took the power? Why we didn't simply multiply? As the multiplication's value will be far greater than long long in C++ data type, we simply can't do that. Also in the problem description there is no mention about modulo operator, so we definitely can't multiply. So we took out the power of 2's and add them to get our maximum muliplication subarray.
Solution:
Given N and K, we have to find how many integers of K subarray has maximum product which starting index of the subarray is minimum. Also all the integers will be power of 2.
So, at first we will store the power of all the integers in an array. Then we will simply use brute force to check for maximum subarray summation (As we took only power, so we will check for summation here).
Why we took the power? Why we didn't simply multiply? As the multiplication's value will be far greater than long long in C++ data type, we simply can't do that. Also in the problem description there is no mention about modulo operator, so we definitely can't multiply. So we took out the power of 2's and add them to get our maximum muliplication subarray.
No comments:
Post a Comment