Make Sum Divisible by P | Simplest Explanation | Full Dry Run | Leetcode 1590 | codestorywithMIK

Подписаться 69 тыс.

Просмотров 13 тыс.

50% 1

Whatsapp Community Link : www.whatsapp.c...
This is the 112th Video of our Playlist "Array 1D/2D : Popular Interview Problems" by codestorywithMIK
Similar Problems :
Leetcode - 1074 : • Number of Submatrices ...
Leetcode - 974 : • Subarray Sums Divisibl...
In this video we will try to solve a good Array Cumulative Sum related Problem : Make Sum Divisible by P | Simplest Explanation | Full Dry Run | Leetcode 1590 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Make Sum Divisible by P | Simplest Explanation | Full Dry Run | Leetcode 1590 | codestorywithMIK
Company Tags : will soon update
My solutions on Github(C++ & JAVA) - github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
The solution aims to find the smallest subarray that, when removed, makes the sum of the remaining array divisible by a given integer p. Here’s how it works:
Calculate Total Modulo: First, compute the total sum of the array modulo p. This determines the target remainder that needs to be removed to make the remaining sum divisible by p.
Early Exit: If the total sum is already divisible by p (target == 0), the function immediately returns 0, as no subarray needs to be removed.
Iterate through the Array:
Maintain a prefix sum (curr) modulo p while iterating through the array.
Use a hash map (map) to store the indices of seen remainders to efficiently find subarrays with a specific remainder.
Check for Subarray:
For each element, calculate the remainder remain that, if removed, would make the remaining sum divisible by p.
If this remainder has been seen before, update the result with the length of the smallest subarray.
Return Result:
If a valid subarray is found, return its length. Otherwise, return -1.
This approach leverages prefix sums and hash maps for efficient subarray length calculation, making it run in linear time O(n).
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

Опубликовано:

9 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 79

@harshalyallewar 7 дней назад

target is not remainder always, suppose your p is 8 and remainder is 3 , so you may think that our target sum is 3 but you dont know bro sum 3 is contained in array or not , there might case where summ 3 is not present as subarray but but 8+3=11 or 8+8+3=19 etc (n*p+3) might be there in subarrray sum that we can remove so ultimately removing n*p+remainer alsoo makes whole array divisible by p, remvoing reaminder is not only way to making array divisible by p , removing multiple of p +remainder can also make array divisble by p /In modular arithmetic, this means we need to find a subarray whose sum modulo p is congruent to remainder. (that subarray might contains multiple of p + remainder, we can not say that only removing remainder will make arr divisble by p ,but removing multiple of p + remainder will also make array divisible by p) we dont have to care about multple of p in prefix sums as long as they can be divisble so we will keep storing prefix sums modulo p and when checking also prefix sum module p - targetSUm(which is remainder) = prev value if value available in hashmap then we can remove this subarray so we calc length; to handle negative prev value we add p to it

@codestorywithMIK 7 дней назад

I agree with your point. Appreciate your input. ♥️👍🏻

@gui-codes 7 дней назад

yep right.

@Step_to_heaven2004 6 дней назад

bhaiya aap coderforces v karte ho kya

@harshalyallewar 6 дней назад

@@Step_to_heaven2004 nhi bhai

@raveenakumari6724 6 дней назад

I understood your point but how is it implemented in the code please explain @codestorywithMIK bhaiya

@ujjwalsharma6773 7 дней назад

bhaiya pls take care of your health and thank you for your efforts. truly appreciated

@dhirajkumawat108 7 дней назад

Yes now I believe in consistency is the key Because today I got 100Day badges on Leetcode, So happy ☺☺☺☺

@md.taohidimamkhantamim9747 7 дней назад

Get well soon brother. Love from Bangladesh..

@MD_SAMEER___ 7 дней назад

Get well soon brother ❤ May Allah grant you good health 🤲🏻

@naikajsevak6090 7 дней назад

today's problem is quite tricky ,i feel demotivating

@codestorywithMIK 7 дней назад

Hi there, Please don’t feel demotivated. I also could give my 100% today due to health issue. Don’t worry, 1 Qn can’t decide our knowledge right. Straight up and keep moving 😇💪💪💪

@sojwalgosavi7871 7 дней назад

Consistency is the key not gonna lie... As MIK told ...we just think of a problem and try to convert it to a story...we might be able to solve somewhat portion....I did the same...and I just thought....and within 5 minutes I reached to the point where I found the way...I was able to boil this down to prefix sum problem... like I was 90 percent correct...just had tough time in hashmap building 😢

@souravjoshi2293 7 дней назад

Get well soon MIK. I was able to almost do this problem on my own. Now it's all clear. thank you

@gauravmundhada1647 7 дней назад

Perfection ka dusra naam MIK❤

@footballcreativeeverywhere260 7 дней назад

long long minSubarray(vector &nums ,long long target){ long long mn = 1e7; int i =0; int j=0; long long sum =0; while(j < nums.size()){ sum += nums[j]; while(sum >= target){ if(sum == target) mn = min(mn ,1LL* j-i+1); sum -= nums[i]; i++; } j++; } return mn ; } use sliding window to find target

@Shubhammi1100 7 дней назад

what is the point of writing solutions here

@wearevacationuncoverers 7 дней назад

0:20 Thank you. Keep adding motivation part always in your videos. this helps a lot. And great explanation. Get well soon legend

@gui-codes 7 дней назад

Those who are asking why sliding window is not suited for this : Sliding window complicated hoga and it will not be possible to get the right solution. The remainder of a (prefix_sum % p) can jump unpredictably, making it hard to track using just two pointers as in a sliding window approach. Also, The solution using a hash map is helpful because we need to efficiently check if a specific remainder (curr - target + p)%p has appeared before in the prefix sums. Let's see below sliding window someone wrote : class Solution { public: int minSubarray(vector& nums, int p) { long long total = 0; int n = nums.size(); for (int i = 0; i < n; i++) { total += nums[i]; } if(total < p){ return -1; } if (total % p == 0) { return 0; } int minlen=INT_MAX; int current=0; int i=0; int j=0; int target = total % p; int sum = 0; while(jtarget){ sum-=nums[i]; i++; } if(sum==target){ minlen = min(minlen, j-i+1); } j++; } } if(minlen==INT_MAX){ return -1; } return minlen; } }; But it fails for this test case [26,19,11,14,18,4,7,1,30,23,19,8,10,6,26,3] p = 26 The approach is assuming that removing a subarray whose sum is equal to total % p would always make the remaining array's sum divisible by p, but this logic does not work for all cases due to modular arithmetic properties. Let's break down the test case to understand why it fails: Input: - nums = [26,19,11,14,18,4,7,1,30,23,19,8,10,6,26,3]` - p = 26 1. Calculate the total sum of nums : SUM = 26 + 19 + 11 + 14 + 18 + 4 + 7 + 1 + 30 + 23 + 19 + 8 + 10 + 6 + 26 + 3 = 225 2. Find target remainder: SUM % p = 225%26 = 17 This means that if we want the remaining elements' sum to be divisible by `p = 26`, we need to find a subarray whose sum has a remainder of `17` modulo `26`. Why the Sliding Window Approach Fails The sliding window implementation in the code is trying to find a subarray whose sum is exactly equal to `target = 17`. This approach is incorrect because: 1. It Ignores Modular Arithmetic Rules: Instead of searching for a subarray whose sum is exactly `target`, the goal is to find a subarray whose sum % p is target. Due to this, a simple comparison ( `sum == target`) does not guarantee that the remaining sum will be divisible by `p`. 2. Can't decide Window Shrinking: The logic for shrinking the window (`while (sum > target)`) is wrong because it assumes that a larger sum should be reduced until it equals `target`. However, the correct condition should check whether the remainder of the sum is `target`. This causes the approach to miss valid subarrays or incorrectly shrink the window.

@Love-xs9mk 7 дней назад

This code of sliding window working properly but giving tle at 138 testcase (only 4 left😢😢 ) class Solution { public: int minSubarray(vector& nums, int p) { int n = nums.size(); long long int totSum = 0; for(int ele : nums){ totSum += ele; } if(totSum

@user-tj4kc9re9t 2 дня назад

Exactly what i was looking for thanks man meow

@gauravbanerjee2898 6 дней назад

Thanks a lot bhaiya ❤❤

@EB-ot8uu 7 дней назад

THanks for the dry run. It's clear. Take care also bro

@SaurabhSinghyadav-r4y 7 дней назад

Get well soon Sir ❤

@anubhavsharma398 4 дня назад

thanks bhaiya for these wonderful solutions... Can you help me how your record good audio on ipad as I also want to start recording on my ipad?

@anirudhaiysola118 6 дней назад

Can we do sliding window here? we need to find the smallest subarray with value sum%p

@ganeshjaggineni4097 7 дней назад

NICE SUPER EXCELLENT MOTIVATED

@devarajusushanthi2144 7 дней назад

please do keep/explain, brute force and optimal solutions like you used keep earlier

@codestorywithMIK 7 дней назад

Sure thing ♥️ Will take care of it definitely

@marvelousmohitindore5621 6 дней назад

@@codestorywithMIK yes please

@harshitpathak5376 7 дней назад

Bhai .. agr humme at the end isme minimum length sub array with given target find krna hai to sliding window ku nhi laga skte ? Please help

@abhishek_0513 7 дней назад

Bhaiya Take care and Bhaiya Is your System design course on RU-vid sufficient for freshmen interviews, or are there any prerequisites before watching both basic and intermediate course of yours.

@wqffeqf 7 дней назад

bro what if we find only curr-target means what if we just solve this question using sum not using modulo. then it will become very easy. pls reply

@sahilrout2758 6 дней назад

no it will not work

@Sanjay-kj7up 7 дней назад

No worries broo.. take care😊

@yashbhardwaj3944 7 дней назад

Please provide GFG potd solution also

@prantikbarik5503 7 дней назад

Bhaiya can you please make a video on 1632 leetcode i.e Rank Transform of a matrix, its hard and no one on youtube has proper explanation on this, pls. Really love uour content❤

@39_jatinjain4 7 дней назад

Let’s say we have an array [1,6,9] and p=9 and after processing first element we get (1-7+9)%9 which is 3 i want to ask what’s the significance of finding 3 only??

@ankanbrahmachary6581 6 дней назад

i think here we are trying to find the smallest subarray which leaves a remainder of target when divided by p and not a subarray of sum target ... if we remove a subarray with remainder target , then the rest of the array is guarenteed to be a divisible by p

@codestorywithMIK 6 дней назад

Yes 👌 Please see the pinned comment ♥️

@monugit9 7 дней назад

Get well soon

@surjaysoni2935 7 дней назад

No problem sir! Take proper medication and stay safe!!

@GeniusCoder-m7p 7 дней назад

BHAIYA GET WELL SOON......

@kartikkaushik4743 7 дней назад

Hi mik There are many person out there who don't know where should they start and how they should they begin with the problems in DSA Can you pls create the vedio for it if it's possible ?

@codestorywithMIK 7 дней назад

Please try this - ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-2Jshfog1ETg.htmlsi=YrthYwVczY2R3-35 Hope this helps ♥️🙏

@kartikkaushik4743 7 дней назад

Thanks mik

@nik3889 7 дней назад

bhaiya 22:24 pr apne 2 ko jo ki remainder h map m dala h or baki iteration m aapne sum ko map m dala h yeh kya shi h ya aapne by mistake likh diya h

@codestorywithMIK 7 дней назад

Apologies if I made a mistake. We have to input remainder in map.

@gui-codes 7 дней назад

Take care bhai. Health is more important.

@riteshtiwari7657 7 дней назад

after giving lots of efforts only 126/142 test cases passes

@sahilrout2758 6 дней назад

same bro even i did with sliding window and manage to pass only 129 test cases

@mohit.xy26 7 дней назад

Brother can you make videos for other subjects like Aptitude , and some other subjects which are asked in interviews please.

@vamshi-249 6 дней назад

Why not sliding window

@Step_to_heaven2004 7 дней назад

bhaiyaa samajh nhi aayaa

@codestorywithMIK 6 дней назад

Sorry to hear that. Can you first try the other 2 problems that I have mentioned in the description ? That should help. Once I am well, I will plan to add more details for this problem in a separate video ♥️🙏

@shabananoor9423 7 дней назад

❤❤

@deb4656 7 дней назад

Why we are doing mod p

@jewelchakraborty9717 7 дней назад

I have a doubt, can anybody clear it? Why are we using mod p here - prev % p = (curr - target) % p. why not just keep prev = curr - target. When i keep this, why do i get wrong results for the following example - [4, 11, 13, 9]. Please help somebody.

@jewelchakraborty9717 5 дней назад

can anyone please help me clear this doubt

@codestorywithMIK 5 дней назад

Please see pinned comment ♥️

@Engineering.Wallah 7 дней назад

class Solution { public: int minSubarray(vector& nums, int p) { int n=nums.size(),psum=0; vectorprefix; prefix.push_back(0); for(auto x:nums){ psum+=x; prefix.push_back(psum); } int rem=psum%p; if(rem==0) return 0; unordered_mapmp; mp[0]=-1; int i=0,ans=INT_MAX; for(auto x:prefix){ if(mp.count(x%rem)>0){ if(mp[x]!=-1 && prefix[i]-prefix[mp[x%rem]]==rem){ ans=min(ans,i-mp[x%rem]); } } mp[x%rem]=i; i++; } return ans==INT_MAX?-1:ans; } }; Why this is not accepted

@Love-xs9mk 7 дней назад

can anyone help me to remove tle of this code only 4 test cases failed logic of window sliding class Solution { public: int minSubarray(vector& nums, int p) { int n = nums.size(); long long int totSum = 0; for(int ele : nums){ totSum += ele; } if(totSum

@sauravkumar-ln7zh 7 дней назад

Why is everyone trying to solve with Hashmap. Why not with a sliding window. While doing with sliding window I am able to pass 126 testcase. Can somebody tell me why this code not passing rest the testcase class Solution { public: int minSubarray(vector& nums, int p) { long long total = 0; int n = nums.size(); for (int i = 0; i < n; i++) { total += nums[i]; } if(total < p){ return -1; } if (total % p == 0) { return 0; } int minlen=INT_MAX; int current=0; int i=0; int j=0; int target = total % p; int sum = 0; while(jtarget){ sum-=nums[i]; i++; } if(sum==target){ minlen = min(minlen, j-i+1); } j++; } } if(minlen==INT_MAX){ return -1; } return minlen; } };

@pokeindia5361 7 дней назад

Bhai galat approach h

@KartikGarg-m7h 7 дней назад

@@pokeindia5361 galat kyo h it wll checking the subarray which sum is squal to target hich is needed to remove ?

@sauravkumar-ln7zh 7 дней назад

@@pokeindia5361Why any reason?

@harshalyallewar 7 дней назад

@gui-codes 7 дней назад

Bhai, sliding window complicated hoga and it will not be possible to get the right solution. the remainder of a (prefix_sum)%p can change non-monotonically, it is challenging to manage with just two pointers, as a sliding window would. Also, The solution using a hash map works because we need to efficiently check if a specific remainder (curr - target + p)%p has appeared before in the prefix sums.

@sulabhsamrat5129 7 дней назад

Bhaiya also add from brute force approach

@dayashankarlakhotia4943 7 дней назад

public int minSubarray (int[]nums,int p){ int n=nums.length,sum=0; for(int num:nums){ sum=(sum+num)%p; } int target =sum%p; if(target==0) return 0; Mapmpp=new HashMap(); int ans=n,mod=0; for(int i=0;i

@KartikGarg-m7h 7 дней назад

why this is not working int minSubarray(vector& nums, int k ) { int n = nums.size(); long long prefix = 0; for( auto i : nums ) prefix += i ; int need = prefix % k ; int sum = 0 ; int i =0 , j=0 ; int ans = n ; while( j < n ) { if( sum > need ) sum -= nums[i++]; else if( sum < need ) sum += nums[j++]; else if( sum == need || sum % k == need ) { cout

@MayankRathore-qi7qv 7 дней назад

bhaiya mera ek doubt hain mein dsa karta hoon kuch ek aad question hote bhi hain lekin kuch hote nhi mera aada code shi hota lekin company ke question fast way mein solve karne hote hain lkin mujhe thinking karne mein hi 15 minute lag jaate baaki time code likhne mein kya strategy banao smgj nhi aa raha question toh kar raha hoon dry run bhi karta hoon 2-3 dry kar raha hoon fir bhi nhi hoi raha kya karu kaise karu kuch suggestion di jiye i need guidance pls