LeetCode 1590: Make Sum Divisible by P Solution
Master LeetCode problem 1590 (Make Sum Divisible by P), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1590. Make Sum Divisible by P
Problem Explanation
Explanation:
To solve this problem, we can use the concept of prefix sums and modulo arithmetic. First, we calculate the total sum of the elements in the given array. Then, we find the target sum that we need to reach to make the remaining elements divisible by p.
Next, we iterate through the array and calculate the prefix sum modulo p at each index. We store these remainders in a HashMap along with their corresponding indices. If the current prefix sum modulo p is x and we need to reach the target remainder y, we can remove the subarray between the current index and the index stored in the HashMap where the remainder was ((x - y) % p + p) % p.
If at any point the prefix sum modulo p is equal to the target remainder y, we can consider the subarray from the beginning up to the current index as the subarray to be removed.
Finally, we return the length of the smallest subarray that needs to be removed or -1 if it's impossible.
- Time complexity: O(n)
- Space complexity: O(n)
:
Solution Code
class Solution {
public int minSubarray(int[] nums, int p) {
int n = nums.length;
int target = 0;
for (int num : nums) {
target = (target + num) % p;
}
if (target == 0) {
return 0;
}
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int prefixSum = 0;
int minLen = n;
int currMod = 0;
for (int i = 0; i < n; i++) {
prefixSum = (prefixSum + nums[i]) % p;
int targetMod = (prefixSum - target + p) % p;
if (map.containsKey(targetMod)) {
minLen = Math.min(minLen, i - map.get(targetMod));
}
map.put(currMod, i);
currMod = prefixSum;
}
return minLen == n ? -1 : minLen;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1590 (Make Sum Divisible by P)?
This page provides optimized solutions for LeetCode problem 1590 (Make Sum Divisible by P) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1590 (Make Sum Divisible by P)?
The time complexity for LeetCode 1590 (Make Sum Divisible by P) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1590 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1590 in Java, C++, or Python.