What is the time complexity of Make Sum Divisible by P?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Make Sum Divisible by P?

This problem uses Array, Hash Table, Prefix Sum. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Make Sum Divisible by P?

Insight 1: The problem can be reframed as finding a subarray whose sum has the same remainder as the total sum of the array when divided by `p`. Insight 2: Prefix sums and a hash map can efficiently track remainders seen so far and their corresponding indices.

Which companies ask LeetCode 1590. Make Sum Divisible by P in interviews?

This problem is frequently asked at PhonePe, Samsung.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Make Sum Divisible by P - LeetCode 1590 Solution

Make Sum Divisible by P - Complete Solution Guide

Make Sum Divisible by P is LeetCode problem 1590, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an array of positive integers nums , remove the smallest subarray (possibly empty ) such that the sum of the remaining elements is divisible by p . It is not allowed to remove the whole array. Return the length of the smallest subarray that you need to remove, or -1 if it's impossible . A subarray is defined as a contiguous block of elements in the array. Example 1: Input: nums = [3,1,4,2], p = 6 Output: 1 Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We

Detailed Explanation

The problem requires finding the smallest subarray within a given array `nums` of positive integers such that removing this subarray makes the sum of the remaining elements divisible by `p`. The entire array cannot be removed. The input consists of the array `nums` and the divisor `p`. The output is the length of the smallest subarray that needs to be removed, or -1 if it's impossible to make the sum divisible by `p`.

Solution Approach

The solution utilizes the concept of prefix sums and remainders to efficiently identify the smallest subarray to remove. First, it calculates the total sum of the array and its remainder when divided by `p`. If the remainder is 0, the sum is already divisible by `p`, and the answer is 0. Otherwise, it iterates through the array, maintaining a running sum of the elements modulo `p`. For each index, it calculates the remainder needed to be removed (`rem_to_find`) and checks if a prefix remainder exists in the hash map such that the difference between the current index and the index of that prefix remainder equals `rem_to_find`. The hash map stores the prefix remainders and their corresponding indices, allowing for quick lookups. The smallest length of the subarray found is then updated.

Step-by-Step Algorithm

Step 1: Calculate the total sum of the array `nums` and compute `target_rem` as the remainder of the total sum when divided by `p`.
Step 2: If `target_rem` is 0, the array sum is already divisible by `p`, return 0.
Step 3: Initialize a hash map `prefix_rem_map` to store prefix remainders and their indices. Add `(0, -1)` to the map to handle cases where the subarray starts from index 0.
Step 4: Initialize `current_rem` to 0 and `min_len` to the length of `nums`.
Step 5: Iterate through `nums` from index 0 to `n-1`.
Step 6: Update `current_rem` by adding the current element `nums[i]` and taking the modulo by `p`.
Step 7: Calculate `rem_to_find` as the remainder needed to reach divisibility: `(current_rem - target_rem + p) % p`.
Step 8: Check if `rem_to_find` exists as a key in `prefix_rem_map`. If it does, calculate the length of the subarray to remove as `i - prefix_rem_map[rem_to_find]` and update `min_len` if this length is smaller.
Step 9: Add the current remainder `current_rem` and its index `i` to the `prefix_rem_map`.
Step 10: After iterating through the entire array, if `min_len` is still equal to the initial value (length of `nums`), it means no valid subarray was found, return -1. Otherwise, return `min_len`.

Key Insights

Insight 1: The problem can be reframed as finding a subarray whose sum has the same remainder as the total sum of the array when divided by `p`.
Insight 2: Prefix sums and a hash map can efficiently track remainders seen so far and their corresponding indices.
Insight 3: Modulo operations are crucial to keep the numbers within a manageable range, especially given the large constraints.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Prefix Sum.

Companies

Asked at: PhonePe, Samsung.

Make Sum Divisible by P | LeetCode 1590

Medium

Array Hash Table Prefix Sum

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        int target_rem = 0;
        for (int num : nums) {
            target_rem = (target_rem + num) % p;
        }

        if (target_rem == 0) {
            return 0;
        }

        Map<Integer, Integer> prefix_rem_map = new HashMap<>();
        prefix_rem_map.put(0, -1);
        int current_rem = 0;
        int min_len = n;

        for (int i = 0; i < n; i++) {
            current_rem = (current_rem + nums[i]) % p;

            int rem_to_find = (current_rem - target_rem + p) % p;

            if (prefix_rem_map.containsKey(rem_to_find)) {
                min_len = Math.min(min_len, i - prefix_rem_map.get(rem_to_find));
            }

            prefix_rem_map.put(current_rem, i);
        }

        if (min_len >= n) {
            return -1;
        } else {
            return min_len;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1590: Make Sum Divisible by P - Detailed explanation and solution approaches.

Topics

Array Hash Table Prefix Sum

Companies

PhonePeSamsung

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:1590

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Calculate the total sum of the array `nums` and compute `target_rem` as the remainder of the total sum when divided by `p`.
2
Step 2: If `target_rem` is 0, the array sum is already divisible by `p`, return 0.
3
Step 3: Initialize a hash map `prefix_rem_map` to store prefix remainders and their indices. Add `(0, -1)` to the map to handle cases where the subarray starts from index 0.
4
Step 4: Initialize `current_rem` to 0 and `min_len` to the length of `nums`.
5
Step 5: Iterate through `nums` from index 0 to `n-1`.
6
Step 6: Update `current_rem` by adding the current element `nums[i]` and taking the modulo by `p`.
7
Step 7: Calculate `rem_to_find` as the remainder needed to reach divisibility: `(current_rem - target_rem + p) % p`.
8
Step 8: Check if `rem_to_find` exists as a key in `prefix_rem_map`. If it does, calculate the length of the subarray to remove as `i - prefix_rem_map[rem_to_find]` and update `min_len` if this length is smaller.
9
Step 9: Add the current remainder `current_rem` and its index `i` to the `prefix_rem_map`.
10
Step 10: After iterating through the entire array, if `min_len` is still equal to the initial value (length of `nums`), it means no valid subarray was found, return -1. Otherwise, return `min_len`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is linear because we iterate through the array `nums` a constant number of times (twice). The space complexity is linear because the hash map `prefix_rem_map` can grow up to the size of the array in the worst case, when all prefix remainders are unique.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through all possible subarrays, calculate the sum of the remaining elements, and check if it is divisible by `p`. Keep track of the minimum subarray length found so far.

Time: O(n^3), where n is the length of the array `nums`. There are O(n^2) possible subarrays, and calculating the sum of the remaining elements takes O(n) time.Space: O(1)

Trade-offs: The brute force approach is simple to understand but very inefficient for large input sizes. The main solution using prefix sums and a hash map is much more efficient.

✨

Key Insights

1Insight 1: The problem can be reframed as finding a subarray whose sum has the same remainder as the total sum of the array when divided by `p`.
2Insight 2: Prefix sums and a hash map can efficiently track remainders seen so far and their corresponding indices.
3Insight 3: Modulo operations are crucial to keep the numbers within a manageable range, especially given the large constraints.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: The sum of the array is already divisible by `p`. In this case, the `target_rem` will be 0, and the function returns 0 immediately.
Edge case 2: No subarray can be removed to make the sum divisible by `p`. In this case, `min_len` will remain equal to the length of the array, and the function returns -1.
Edge case 3: The subarray to be removed starts at index 0. This is handled by initializing the hash map with {0: -1}.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering the case where the total sum is already divisible by `p`. This leads to incorrect results in such cases.

✗Common mistake 2: Not handling the modulo operation correctly, especially when dealing with negative remainders. It is essential to add `p` to the result of the subtraction before taking the modulo to ensure a positive remainder.

✗Common mistake 3: Integer overflow when calculating the sum of the array. Using long data type helps to avoid this.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data stream processing where only a subset of data needs to satisfy a condition (divisibility). This algorithm can help identify the smallest portion of data to discard.

🏦Real-world scenario 2: Error correction in data transmission. If the total data needs to be divisible by a certain number for error checking, this could find the smallest block to request retransmission of.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 29, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Make Sum Divisible by P"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?