DP 44. Largest Divisible Subset | Longest Increasing Subsequence

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

[@akshayaashok8794]

This solution was really unexpected!! Nice to see that code for printing Longest increasing subsequence can be tweaked to solve longest divisible subsequence if we sort the array. Thank you so much!!! Understood.

[@your_name96]

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.

[@ritikshandilya7075]

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

[@priyanshkumariitd]

yeah

[@Aryan-tg3uu]

Not yet at these problems, just saw the notification and came to say thank you for your efforts Striver! 🔥👍🏼

[@sauravchandra10]

Wow, intuitive and simple. Understood clearly, thanks!

[@gautamgrover1087]

main good thing with your videos is the depth of every question uh discuss which nobody does in even paid courses

[@stith_pragya]

UNDERSTOOD...........Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@ganeshkamath89]

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.

[@your_name96]

I guess there is a thumb rule, in case of subset type of probs, never hesitate to sort

[@Dontpushyour_luck]

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

[@nigam_sharma]

🎯 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

[@cinime]

Understood! Amazing!! Thank you very much as always!!

[@sundeepkumar3871]

hey bro /sis , please see my comment above and solve my doubt please , sort by recent comments and see my comment

[@tasneemayham974]

Crystal Clear Sir!!!

[@rohanrastogi1077]

no need to reverse temp as we have to find subset ,not subsequence

[@siddhaarthsingh7414]

Mera TLE aara h Can y share ur code

[@krishnavamsichinnapareddy]

Yeah 👍

[@kainathussain6973]

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

[@aj9706]

Thanks!

[@UECAshutoshKumar]

Thank You! Understood!!!

[@harshitsen5479]

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); }

[@DevashishJose]

understood thank you so much.

[@chanchalroy3417]

Understood totally 💥😌

[@kms8320]

nice question and completely understood

[@disunique6107]

Understoooood the intuition ......... thanks 😊

[@gauravtiwari6104]

understood striver bhai

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@stl8857]

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

[@deepaliaggarwal6429]

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🙂

[@takeUforward]

Yes

[@ankishkhandelwal1061]

i think because of these we sort arr ????

[@sundeepkumar3871]

@@takeUforward hey bro, please see my comment above and solve my doubt please , sort by recent comments and see my comment

[@sundeepkumar3871]

hey sis , please see my comment above and solve my doubt please , sort by recent comments and see my comment

[@adebisisheriff159]

Thanks Striver

[@prabhakaran5542]

Understood ❤

[@earningonlinevip8147]

very easy beacuse you explain very smartly

[@sangammishra3670]

why we nened to sort it cant it be like every time check with previous only and then add in the set

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@studynewthings1727]

Understood.

[@yeswanthh5068]

Understood thank u very much

[@arihantjammar8888]

Understood 😊

[@sameersahu4569]

Understood!!Thank you

[@chiragbansod8252]

UNDERSTOOD

[@akshaali28]

Loved the content!

[@user-nb1ye5tf1r]

I read comments, and i was able to solve this problem.

[@pragyanandsingh6673]

Understood !!

[@abhinanda7049]

understood

[@Harshit126]

Understood, thanks

[@shreeshdivyamsinha126]

Understood

[@lakshaysharma6550]

UNDERSTOOD!!!!🔥🔥🔥🔥

[@srinathv1412]

Understood !!!!

[@user-rm7jm5tl3w]

time complexity: O(n2)+O(nlogn)+O(n)

[@ujjalsaha428]

As always "understood" ❤️

[@anujbajpai5791]

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?

[@LearningYouth]

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.

[@sayantanacharya2040]

Hey man!Really enjoying your vidies... can u please tell me if the java code is available yet?Would be really helpful..."US"..

[@vaishnavithakur6460]

understood!!!

[@sujalgupta6100]

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

[@jayagarwal9759]

understood!

[@subhajitdey135]

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.

[@iamnoob7593]

US striver Thanks

[@m-bk4um]

understand

[@harshitgoyal9341]

No need to reverse the temp vector in end ................. as it has asked for subset in any order

[@SNX03]

This could be done in O(nlogn) also by simultaneously creating parent array during binary searching the upper_bound

[@shivamkumar5857]

how do u print it

[@vikramket]

​@@shivamkumar5857yes its not possible to print it

[@krishanpratap3286]

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

[@disunique6107]

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

[@rishabhgupta9846]

understood,able to solve by own

[@JoySaha-jg1qi]

Thank you for amaging contents.

[@sangharshpipare666]

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

[@srikarvinjamara2003]

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!

[@sahulraj9536]

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

[@asm9450]

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

[@rohankumarshah5679]

idea is to find largest such subset. that means the length should be more

[@gurmeetsingh2016]

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

[@utkrishtsingh5520]

Understood

[@user-tg9kx3ze5p]

no need to reverse at the end since we can print in any order

[@giraffe4375]

understood striver

[@_hulk748]

understood sir🙏❤

[@dhairyachauhan6622]

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; }

[@suryakiran2970]

Is is gives TLE, because it is not Memoize ?

[@adityasaxena6971]

Understood Striver💯💯

[@tikshavarshney213]

Understood !

[@jinishshah627]

UNDERSTTOOOOOOOOOOODDDDDDDDDDDDDDDDDDDD!

[@VipinKumar-us1sr]

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--; }

[@vishalgupta957]

i think we can't because there can be duplicate values in dp and we don't know which indices includes our answer.

[@sundeepkumar3871]

hey bro /sis , please see my comment above and solve my doubt please , sort by recent comments and see my comment

[@rishabhgupta9846]

no we can't may be its value is equal but not divides

[@ashutoshpandey1639]

Yes , we can follow this approach too

[@amansamal8233]

understood❤❤

[@rohalkurup1350]

Understood !!!!!!

[@googleit2490]

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

[@jayrathod7957]

bhaai kya baat he,............... me bhi try karta hu lekin mujse nahi ho raha kuchhh tip de sakte he ky??

[@googleit2490]

@@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.

[@parshchoradia9909]

Understood Sir!

[@ITArchanaGK]

understood✨

[@original_gangsta_]

Understood 💯💯💯

[@aditithakur6226]

Understood Sir.

[@manikiran949]

Understood++

[@ganeshmula4508]

understood sir

[@Superheroic_Anime]

Understood bhaiya !!!

[@VikashYadav-px8ei]

Understood 🎉

[@venkateshvenky2880]

#understood

[@enigma2777]

Can someone please share the recursive code for this problem

[@HimanshuGupta-ni3pk]

have you got ?

[@riyakumari8377]

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!

[@HeroHunter07]

Today's question

[@codewithom11]

Understood🙂🙃

[@codingp110]

US!

[@RohitKumar-dy2gc]

US

[@harshbardhanon4901]

Love from Pak🙂🕌

[@preetkatiyar969]

Sir there is no java code in notes

[@manasranjanmahapatra3729]

UnderStood💥

[@imilanprj]

🔥

[@mriduljain6809]

Understood😀😀

[@priyanshvatsal9791]

Understood🥰

[@rayyansyed2998]

"us"

[@arkasheikh3539]

"UNDERSTOOD"

[@splinkerp2222]

You are legend bhayya

[@ojasdighe991]

Thanks bro

[@Skm-mq1sw]

US Bhaiya

[@keertilata20]

You forgot the additional time complexity for sorting the array

[@dolbyagarwal9316]

additional but still N^2 is greater than NlogN

[@keertilata20]

@@dolbyagarwal9316 yess

[@priyanshuchandrakar172]

us

[@addityasharma6426]

understood:-)

[@arnabroy2995]

US❤