Another Casual Coder

This problem requires finding out all the subsets of a small set S. For each subset S', you need to determine whether: Product(S') == Product(S - S') == Target Hence you need to find all S'. Subsets generation trick, as explained before on post I with the same title, does the trick here for an exponential-time solution, but since |S| is small (12), it works just fine. Bonus points for early termination whenever we reach a dead end. Code is down below, cheers, ACC. Partition Array into Two Equal Product Subsets - LeetCode You are given an integer array  nums  containing  distinct  positive integers and an integer  target . Determine if you can partition  nums  into two  non-empty   disjoint   subsets , with each element belonging to  exactly one  subset, such that the product of the elements in each subset is equal to  target . Return  true  if such a partition exists and  false  otherwise. A  subse...

Another application of MRP with caching. The caveat here is that using BigInteger implementation of MRP Test leads to TLE. Converting to Long does the trick. There is still usage of BigInteger for modular exponentiation (otherwise you'd have to implement your own, which can be a little tricky), but that doesn't seem to add much overhead to the solution. It is also interesting to use OpenAI ChatGPT 4.0 model to ask and learn for the detailed time complexity of this algorithm. It is amazing to see how fast MPR is - an impressive LogN. Answer from the bot is down below, as well s my code. Cheers, ACC. Analysis from OpenAI ChatGPT Model 4.0: Time Complexity: 🔸 Worst Case: O(n² log m) (where m is the largest number formed from the substring) 🔸 With caching and typical inputs, it behaves closer to O(n²) . Sum of Largest Prime Substrings - LeetCode Given a string  s , find the sum of the  3 largest unique  prime numbers  that can be formed using any of its   subs...

In this example a simple prefix sum approach does the job. Some caveats to keep in mind. First, there is no reason to use a hash table - in this case two simple prefix sum arrays work. Second, watch for overflow, since you're going to be adding up numbers that can grow up to 10^10, use long instead of int. Finally, the calculation of prefix sum is usually straightforward, following the pattern: PrefixSum[i] == PrefixSum[Last] - PrefixSum[i] Code is down below, cheers, keep coding. ACC Equal Sum Grid Partition I - LeetCode You are given an  m x n  matrix  grid  of positive integers. Your task is to determine if it is possible to make  either one horizontal or one vertical cut  on the grid such that: Each of the two resulting sections formed by the cut is  non-empty . The sum of the elements in both sections is  equal . Return  true  if such a partition exists; otherwise return  false .   Example 1: Input:   grid = [[1,4],[2...