Largest Component Size by Common Factor | LeetCode 952 | C++, Java, Python

LeetCode Solutions: • LeetCode Solutions | L...
August LeetCoding Challenge: • Playlist
Github Link: github.com/Kno...
*** Best Books For Data Structures & Algorithms for Interviews:*********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
*****************************************************************************
August LeetCoding Challenge | Problem 30 | Pancake Sorting | 30 August,
Facebook Coding Interview question,
google coding interview question,
leetcode,
Largest Component Size by Common Factor,
Largest Component Size by Common Factor c++,
Largest Component Size by Common Factor Java,
Largest Component Size by Common Factor python,
Largest Component Size by Common Factor solution,
952. Largest Component Size by Common Factor,
#CodingInterview #LeetCode #AugustCodingChallenge #Google #Amazon #unionFind

[@himanshuyadav0600]

Best Explanation...

[@KPSingh-vs2ym]

I followed gcd approach with modulo operator in Java with connected components. But it’s time limit is exceeding.

[@kabir_pathak]

i did the same. Getting TLE because n

[@BarkaDog]

Yeah it won't work

[@ppujari]

What kind of software, are you using to write mimic the blackboard experience? This is very nice.

[@subhambanerjee6334]

it is PowerPoint I think

[@KnowledgeCenter]

Yes. powerpoint.

[@Ice-2706]

Sir, I have implemented the same algorithm but again it is giving TLE ( 74 / 100 ) test cases passed

[@rt_developer]

Yeah ! Every video has same lecture ! But the test cases are not passing beyond 75 .Don't know Why !

[@shubhamkumargupta3478]

I was thinking about this, if 2 is a factor of any number then lcm(a,2)

[@acxd]

Do you have any other videos for learning basics of Union Find / DSU.

[@KnowledgeCenter]

I haven't added yet. Was planning to add to the Graphs playlist soon.

[@acxd]

@@KnowledgeCenter oh great , waiting for it🙏

[@crankyinmv]

Thanks.
I missed this problem after trying a combo of Union find and set. I was running each number against all the other numbers instead of running each number against all the GROUPS. I got a correct answer, but hit TLE on a problem with 15K numbers. I modified to run numbers against groups and succeeded with a 62.5% speed. I factored a little differently in that I only took unique prime factors. That may be a useful optimization to consider.
BTW: On videos explaining tricky problems like this is where I really noticed YT interrupting me with inane ads. I'm so sick of Fred Armissen.

[@keshavbansal880]

Fab man... thankssss!!

[@pardeepsharma6502]

Similar question: leetcode.com/problems/accounts-merge/

[@isha2567]

While finding factors, we stop at the sqrt, then how do we get 21 at th-cam.com/video/DNfNZwilaC4/w-d-xo.html

[@KnowledgeCenter]

We do 2 unions for each factor till sqrt(x).
For each factor f till sqrt(x):
- Union(f, x), and
- Union(x/f, x)
So, for 63, when we got f = 3, we did union(3, 63) and also union(63/3, 3) i.e., union(21, 3).
Union operation merges them to same partition.

[@isha2567]

@@KnowledgeCenter Thank you sir :)