DP 44. Largest Divisible Subset | Longest Increasing Subsequence
Vložit
- čas přidán 11. 07. 2024
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3rON1Ef
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the Largest divisible Subset, but please make sure to watch DP 41 and DP 42 prior to this video.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
Thanks man, though the observation was pretty simple, and the bias that I knew LIS was needed for this problem, I was able to do it by myself(though I had to refer to the notes for some of the printing details :P),your first 3 videos of LIS have been phenomenal!
I hope to solve problems like in unknown environment as well.
Wow, intuitive and simple. Understood clearly, thanks!
Not yet at these problems, just saw the notification and came to say thank you for your efforts Striver! 🔥👍🏼
UNDERSTOOD...........Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
main good thing with your videos is the depth of every question uh discuss which nobody does in even paid courses
What an amazing approach , no one assumed LIS would be tweaked such that we can solve LDS in such a simple way . Thankyou so much Striver
yeah
Crystal Clear Sir!!!
Understood! Amazing!! Thank you very much as always!!
hey bro /sis , please see my comment above and solve my doubt please , sort by recent comments and see my comment
Immediately after you told that we will sort and use lis idea, I was able to solve this on my own. Thank you striver for making me this capable
Thank You!
Understood!!!
Thanks Striver. Understood.
To summarize the changes:
1) sort the array
2) change comparison (arr[prev] < arr[i]) to modulo (arr[i] % arr[prev])
3) return the temp array
I am summarizing because I forgot to sort the array when I tried and later realized that change.
I guess there is a thumb rule, in case of subset type of probs, never hesitate to sort
Understood totally 💥😌
understood thank you so much.
Understoooood the intuition ......... thanks 😊
nice question and completely understood
Understood, sir. Thank you very much.
no need to reverse temp as we have to find subset ,not subsequence
Mera TLE aara h
Can y share ur code
Yeah 👍
class Solution {
public:
vector largestDivisibleSubset(vector& a) {
int n = a.size();
sort(a.begin() , a.end());
vector dp(n,1) , prev(n);
for(int i= 0;i
Thanks Striver
understood striver bhai
Hey Thanks for this series striver🥰!! I just have a small doubt, I know this rule that if a/b and b/c that means a/c also. Do we need this condition to be also satisfied that a < b < c ? Can you once confirm? I know this is very basic maths but still🙂
Yes
i think because of these we sort arr ????
@@takeUforward hey bro, please see my comment above and solve my doubt please , sort by recent comments and see my comment
hey sis , please see my comment above and solve my doubt please , sort by recent comments and see my comment
Recursion solution, kind of same as combination sum - 1.
// Array is sorted and then recursion function is called.
private static void recursion(int idx, int prevIdx, int[] arr, List list, List output, int n) {
if(idx == n) {
if(list.size() > output.size()) {
output.clear();
output.addAll(list);
}
return;
}
if(prevIdx == -1 || arr[idx] % arr[prevIdx] == 0) {
list.add(arr[idx]);
recursion(idx + 1, idx, arr, list, output, n);
list.remove(list.size()-1);
}
recursion(idx+1, prevIdx, arr, list, output, n);
}
Understood thank u very much
Understood!!Thank you
Understood Sir, Thank you very much
very easy beacuse you explain very smartly
Understood 😊
Thanks!
why we nened to sort it cant it be like every time check with previous only and then add in the set
Understood ❤
Understood, thanks
UNDERSTOOD
UNDERSTOOD!!!!🔥🔥🔥🔥
Loved the content!
Understood !!
understood
As always "understood" ❤️
Understood.
Understood
understood and cant we solve it like this:
traverse through the sorted array and for each element just run a loop until log(max/a[i]) and check if a[i]*pow(2,j) is present or not using map or anything it will take nlogn
understood!
Understood !!!!
understood!!!
🎯 Key Takeaways for quick navigation:
00:13 🧠 *Understand the importance of understanding longest increasing subsequence before tackling the largest divisible subset problem.*
03:37 🎯 *To solve the largest divisible subset problem, grasp the concepts of subset, divisibility, and finding the largest possible subset.*
05:55 💡 *By sorting the array, you can simplify the process of identifying divisible pairs within the subset.*
08:24 🔄 *Transform the problem of finding the longest divisible subsequence into a variation of the longest increasing subsequence.*
11:29 🛠️ *Key insight: Sort the array to ensure divisibility relationships between elements, crucial for the solution logic to work.*
13:57 ⏰ *Time complexity of the solution is O(n^2) due to nested loops, with an additional O(n) for tracking back the longest subset.*
Made with HARPA AI
understood,able to solve by own
Thank you for amaging contents.
time complexity: O(n2)+O(nlogn)+O(n)
understand
Ye last wala code nahi chal rha mere mei, Leetcode pe,
jo code blog mei diya hai usme last for loop undo nested loops ke bahar hai wo chal rha hai
understood sir🙏❤
Understood
Hi!. Could any one please tell me how do i think of sorting the array? I knew this had to be done in some way similar to the LIS problem but it did not come to my mind that i need to sort it. Why does it work when sorted? Please and Thank You!
since they asked for subset ,the order of the elements does not matter so we can sort them
if they asked a longest divisible subsequence they we cant do sorting.in fact while solving i assumed subset as subsequence and tried it without sorting and i didnt get the right answer
understood❤❤
Hey man!Really enjoying your vidies... can u please tell me if the java code is available yet?Would be really helpful..."US"..
understood striver
If we are still traversing all the previous indexes for each index then why do we need to sort it? If 16 is before 8, and count at 16 is 2 then for 8 it will be 3 irrespective the order of occurence. Can someone explain where am I missing?
Let's say we have [16 1 18]
count will be : [ 1 2 3 ] which indicates, taking last element as 18, max length of LDS can be formed 3 which is incorrect.
Bcz max length of LDS is 2. Either [16 1] or [1 18]
So you need to sort otherwise it'll give you WA.
Understood !
isme agar sroted nahi bhi ho then also if we add in they array jisme hum store kar rahe den also who logic apply ho jayega nah pls ek baar batana
No then it will not give correct subset... As (16,1,8 ) != (1,8,16)
1%16 will give remainder =1 ;
8%1 will give 0..
But in sorted 8%1 ==0 and also 16%8 ==0
US striver Thanks
What is the importance of initialising the hash array to the respective i values ? Since we will have the lastIndex we will just be jumping to the correct indexes of hash array. Without it the solution is failing, any help is appreciated
The Test Case: arr = {20, 19, 11, 25, 21}
Ok, realised what was wrong if we didn't initialise the hash array and if no elements are exactly divisible the hash array will have all elements 0. But the while loop will execute one time before terminating and we get a wrong answer
UNDERSTTOOOOOOOOOOODDDDDDDDDDDDDDDDDDDD!
understood✨
Understood !!!!!!
Thought process of sorting: If the biggest numbers gets divided by the incoming greater number or the vice-versa, then all other smaller elements in the array will be divisible.
Understood Striver💯💯
Understood 💯💯💯
This could be done in O(nlogn) also by simultaneously creating parent array during binary searching the upper_bound
how do u print it
@@shivamkumar5857yes its not possible to print it
Understood Sir!
No need to reverse the temp vector in end ................. as it has asked for subset in any order
Recursive sol for those who were trying to solve like me ..... (C++)
#include
void solve(vector&arr,int n,int idx,int prev_idx,vector&ans,vector&output){
if(idx == n){
if(output.size()>ans.size()){
ans = output;
}
return;
}
if(prev_idx == -1 || arr[idx]%prev_idx==0){
solve(arr,n,idx+1,prev_idx,ans,output);
output.push_back(arr[idx]);
solve(arr,n,idx+1,arr[idx],ans,output);
output.pop_back();
}
else{
solve(arr,n,idx+1,prev_idx,ans,output);
}
}
vector divisibleSet(vector &arr){
sort(arr.begin(),arr.end());
vectorans;
vectoroutput;
int n = arr.size();
solve(arr,n,0,-1,ans,output);
return ans;
}
Is is gives TLE, because it is not Memoize ?
In the if loop (line no.: 10) at 12:24 can we omit the second condition of the if loop (i.e. 1+dp[prev]>dp[i] )?
Btw amazing explanation Understood
idea is to find largest such subset. that means the length should be more
Yes also we if the condition satisifies arr[ind]%arr[j]==0 so dp[ind]=dp[j]+1 and hash[ind]=j and break
There is no need to check others so break out of the loop after that
Understood Sir.
Understood. Actually, we can do it without using hash array. By traversing the dp array and starting from the index which have max value and then moving to the left and checking if ( dp[i] == dp[mx] + 1 and arr[mx]%arr[i] == 0 ) then do { ans.push_back(arr[i]); mx = i; i--; }
i think we can't because there can be duplicate values in dp and we don't know which indices includes our answer.
hey bro /sis , please see my comment above and solve my doubt please , sort by recent comments and see my comment
no we can't may be its value is equal but not divides
Yes , we can follow this approach too
DP Revision:
Done and dusted in DP revision :)
(11 mins, exact code without watching the video earlier any before)
Nov'20, 2023 03:45 pm
bhaai kya baat he,...............
me bhi try karta hu lekin mujse nahi ho raha kuchhh tip de sakte he ky??
@@jayrathod7957 Kuchh logo ko kam time lagta h, kuchh ko maybe jyada lag skta h. But, believe me, if you are consistent enough, you will crack it one day.
#understood
understood sir
no need to reverse at the end since we can print in any order
Understood bhaiya !!!
Understood 🎉
Can someone please share the recursive code for this problem
have you got ?
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
n = len(nums)
nums.sort()
ans = []
def recur(i, path):
nonlocal ans
if i == n:
ans.append(path)
return ans
notTake = recur(i+1, path)
if (((len(path) > 0 and (path[-1] % nums[i] == 0 or nums[i] % path[-1] == 0)) or len(path) == 0)) and nums[i] not in path:
# print(path, nums[i])
take = recur(i+1, path + [nums[i]])
return
recur(0, [])
res = []
# print(ans)
for arr in ans:
if len(arr) > len(res):
res = arr
# print(res)
return res
Though this will give u TLE!
Understood🙂🙃
Understood++
🔥
US
Today's question
UnderStood💥
Love from Pak🙂🕌
Understood🥰
Understood😀😀
You are legend bhayya
Thanks bro
"UNDERSTOOD"
Sir there is no java code in notes
understood:-)
"us"
US!
US Bhaiya
us
Us
please submit it in leetcode
You forgot the additional time complexity for sorting the array
additional but still N^2 is greater than NlogN
@@dolbyagarwal9316 yess
US❤