2 Keys Keyboard - Leetcode 650 - Python

[@harshshah1818]

I have always appreciated this guy for daily solutions of Leetcode. He may continue to do it

[@loke_mc8053]

Where are you bro? pls come back

[@ayanpatel_98]

waiting for LC.664 Strange Printer

[@rishikantshukla4754]

Why are you not uploading the videos ?

[@jeremytsai6987]

I'm not sure why you haven't updated in a while, but I hope everything is going well for you.

[@ParodyCSEDept]

I am being honest.. Had I not known about DP, I might have solved this in O(sqrt(n)) time and O(1) space but here I am getting excited over solving this in O(n^2) time and O(n) space :)

[@greatfate]

always think of greedy before DP brother

[@ParodyCSEDept]

@@greatfate Yeah I'll keep that in mind

[@tranminhquang4541]

It's simply the sum of all prime factors of the number n . For example , n = 24 = 2 * 2 * 2 * 3 . So we need 2 + 2 + 2 + 3 = 9 steps.

[@firezdog]

blows your mind when you realize this

[@pratyushthakur8478]

I got till using dp but started overthinking after that and fumbled. leetcode L streak strong

[@Dyxuki]

waiting for LC.664 :D

[@user-tt3lb1yy6i]

NEETCODE CHAAN!!!! SAVE ME!!!

[@alperkaya8919]

I just used recursion, not even dp or memoization. It gives you straight up answer without thinking much. And lesser you think it will be easier for you to implement in an interview.

[@DeveshSoni-u6s]

I did it by utilizing the sum of Prime Factors Imagine 12 12=2*2*3 so answer is 2+3+2=7 if n=2-->2 if n=5-->5 no dp needed

[@АльбусДамблодр]

come back solving leetcode daily problems pllls

[@omega_sine]

I managed to derive the prime factor solution by myself, pretty proud of that. But the dp solution is also good to know.

[@Apeuda]

wow nice! for me i did the dp solution myself. tho i still dont get how the prime factorization solution works. all i know is if n is a prime number, then the result is going to be n

[@meetverma4812]

always remember wherever we can use memoization there's mostly (if not always ) a dp solution that can be computed with O(N) space...

[@shahperzia1121]

@@Apeuda prime factorization solution is same as dp. For example 210 = 1 * 2 * 3 * 5 * 7 DP solution 1 -> 2 : 2 steps (prime) 2 -> 6: 3 steps (prime) 6 -> 30 : 5 steps (prime) 30 -> 210 : 7 steps (prime) answer = 2 + 3 + 5 + 7 = sum( prime factors of 210 ) = 17

[@addiegupta]

Todays (20th Augs) daily challenge so annoying even NeetCode skipped it

[@DNKF]

He has done it.

[@addiegupta]

@@DNKF ah i see he has done it earlier 1 year ago

[@shreyasevelar8561]

Hey! Have you stopped this series where you solve the daily challenges?

[@AJK-a2j00k4]

The second part was 🔥🔥🔥

[@vayunjain9289]

We could find the largest factor(f) of n and add n/f to and the ans and then set n = f. Do this while n>1 and if n is prime then return ans+n. This got accepted in leetcode.

[@FlexGC]

What? Wouldn't the largest factor of n just be n×1 which means it's n?

[@33galactus]

Interesting. Please share your code.

[@vayunjain9289]

​@@FlexGCSorry I meant largest factor

[@vayunjain9289]

​@@33galactus class Solution { public: int minSteps(int n) { if(n == 1) return 0; int ans = 0; while(n>1){ int temp = n; int factor = -1; for(int i=2;i*i

[@nihalbhandary162]

yes I used the same approach. I find the largest factor starting from smaller one. def minSteps(self, n: int) -> int: def helper(n,g): if n==1: return 0 while n%g!=0: g+=1 div=n//g if div>1: return helper(div,g) + g return g return helper(n,2)

[@meetverma4812]

I came with the memoization solution and knew there must be a dp solution as well but could figure it out but you gave me the idea on the drawing board and eventually I solved it in linear space... Big thumbs up for ur explanation navneet 💚

[@pastori2672]

wow really didnt expect you to skip the most optimal solution, especially one that involves math

[@aizad786iqbal]

please make a video on math approach too, if possible

[@krupakarreddy1758]

The DP solution just went over my head 🙃🤯 .How do you even come up with these DP solutions..sometimes they are very hard to understand and forget about even trying to think the approach😵‍💫

[@sarmohanty]

he doesn't always figure them out... he looks at the editorial

[@firezdog]

I have to admit i have a very spotty record solving DP problems I haven't already seen too haha

[@krupakarreddy1758]

@@sarmohanty yeah maybe... I tried debugging the code... But didn't understand a little also🥲

[@guruprasath2862]

We need your help

[@ShinAkuma]

Just do this bro. public int minSteps(int n) { if (n == 1) { return 0; } int count = 0; int factor = 2; while (n > 1) { while (n % factor == 0) { n = n/factor; count += factor; } ++factor; } return count; }

[@michaelroditis1952]

Just because I like shorter solutions I must say something, the first if statement is redundant. If n is equal to 1, then 0 will be returned nonetheless

[@ShinAkuma]

@@michaelroditis1952 true. I didn't care much after it got accepted.

[@michaelroditis1952]

@@ShinAkuma yeah and it would work the same so no need

[@abdulamaan4784]

i brute forced the exponential soln without caching, and just tried to speed it up with compiler flags and other hacks, and leetcode actually accepted it XD i did go back and try memoisation, which my friend helped me out with

[@stoppls1709]

lmao, worked for me without doing anything extra beats 5% too xD

[@m.m.m.4198]

I really enjoy your video! I'm considering getting Neetcode Pro at the moment. Is there any discount code available at all right now? :)

[@АльбусДамблодр]

bro we really need yoouuu(((

[@MP-ny3ep]

Thank you so much ! I don't think the DP problem is that intuitive.

[@sanooosai]

thank you

[@chickennoir691]

Thank you so much

[@heartout9757]

I am trying to understand the logic for dp[j]+i/j, I understood why we are considering dp[j], but when we are adding i/j this means we can paste i/j times to the original word. But what I am missing over here is we need to copy the word first so it would result in dp[j]+i/j+1. I dont know where am I missing since it works for dp[j]+i/j. Help me understand this

[@_night_spring_]

I wonder why you didn't give the simplest approach doing factorisation

[@zweitekonto9654]

Simplest in coding. Not simplest to come up with and prove why it works too.

[@mohammedfirasathussain2329]

congrats

[@mrvinyllad25]

I've managed to get close to the DP solution but i'm just not sure why we need to copy and paste as a single operation (and hence yielding +2 to the result when taking this path in the backtracking process. Is it to not allow double pasting? (at least following this path for me yielded 4 operations for when n = 5, like we start with 'A' and 'A': and 1 as the number of steps taken so far (first operation for n = 1 is copy): step 2: paste, now we have screen = 'AA' and copy_area = 'A' step 3: copy, now we have screen = 'AA' and copy_area = 'AAA' step 4: paste, now we have screen = 'AAAAA' and copy_area = 'AAA' - so, 5 AAAA in the screen. i think reading my explanation i misinterpreted the question. Copy gets overwritten with what is in the screen, not concatenating with what was there :p

[@firezdog]

it is to prevent going down useless paths where we copy and copy and copy again. If we apply copying as a single operation, we know it is never directly going to a node with a better answer. So we are just collapsing the sequence (current_node => copy_node => paste_node) into (current_node => copy_node). In essence, there's never a path that goes through a copy node that doesn't immediately visit a paste node afterwards (or not one that we're interested in).

[@CS_n00b]

do we really need i to iterate over all items, cant we just stop at n//2

[@faaeizkhan6134]

everywhere i go people are saying they were able to come up with the soln, and here i am struggling T_T.......................................

[@yang5843]

I feel like I've seen this problem before

[@chuyi-crack6290]

feel likes the min num coins DP

[@gowthamtg4884]

did he figure out the second explanation himself ?

[@alexandermelocco8140]

wth i was literally doin this problem for the first time

[@DeathSugar]

bruh. there's easy solution with pretty much log time and space 1. composite numbers takes count(n/d) + count(d) where d - is biggest divisor of n less then or equal to sqrt(n) 2. the rest take exactly n times class Solution: def minSteps(self, n: int) -> int: if n == 1: return 0 upper_bound = int(floor(sqrt(n))) for i in reversed(range(2, upper_bound+1)): # look from biggest to lowest if n % i == 0: return self.minSteps(n//i) + self.minSteps(i) return n

[@FlexGC]

Why would count be count * 2 and not count + 2 for copying abd pastkng? Oh the count represents the number of a's on the screen. Not the number of moves.

[@Nischal.shetty02]

while pasting the number of 'A' gets doubled for example - first well have 'A' then after copy and paste well have 'AA' which is 2 times the initial number of A's(ie count*2 => 1*2) then next time we copy and paste well have 'AAAA' which is 2 times the previous count(ie count*2 => 2*2) so youre basically doubling the previous count each time

[@069_Souvik]

Don't know why my memoized solution is taking more time than recursion

[@elisey4770]

probably because you used a hashmap and on lower n’s, hashmap is pretty inefficient. When i changed hashmap to an array, my runtime became significantly better

[@069_Souvik]

​@@elisey4770 I see

[@chaitanyasharma6270]

c# code public class Solution { int n; public int MinSteps(int n) { if(n==1)return 0; this.n=n; return 1+minSteps(1,1); } public int minSteps(int currA, int copied){ if(currA == n){ return 0; } if(currA > n){ return 10000; } //copy and paste int newCopy = currA; int copy = 2 + minSteps(currA + newCopy, newCopy); //no copy keep pasting int noCopy = 1 + minSteps(currA + copied, copied); return Math.Min(copy, noCopy); } }

[@adityabiswas3719]

ok

[@zedz4397]

Petition to change problem name to Copypasta