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 :)
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
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.
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.
@@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
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)
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 💚
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😵💫
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
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; }
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
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
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).
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.
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
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
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
I have always appreciated this guy for daily solutions of Leetcode. He may continue to do it
Where are you bro?
pls come back
Why are you not uploading the videos ?
waiting for LC.664 Strange Printer
waiting for LC.664 :D
NEETCODE CHAAN!!!! SAVE ME!!!
come back solving leetcode daily problems pllls
I'm not sure why you haven't updated in a while, but I hope everything is going well for you.
I got till using dp but started overthinking after that and fumbled. leetcode L streak strong
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 :)
always think of greedy before DP brother
@@greatfate Yeah I'll keep that in mind
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.
blows your mind when you realize this
I managed to derive the prime factor solution by myself, pretty proud of that. But the dp solution is also good to know.
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
always remember wherever we can use memoization there's mostly (if not always ) a dp solution that can be computed with O(N) space...
@@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
Todays (20th Augs) daily challenge so annoying even NeetCode skipped it
He has done it.
@@DNKF ah i see he has done it earlier 1 year ago
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.
Hey! Have you stopped this series where you solve the daily challenges?
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
We need your help
please make a video on math approach too, if possible
The second part was 🔥🔥🔥
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.
What? Wouldn't the largest factor of n just be n×1 which means it's n?
Interesting. Please share your code.
@@FlexGCSorry I meant largest factor
@@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
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)
wow really didnt expect you to skip the most optimal solution, especially one that involves math
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 💚
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😵💫
he doesn't always figure them out... he looks at the editorial
I have to admit i have a very spotty record solving DP problems I haven't already seen too haha
@@sarmohanty yeah maybe... I tried debugging the code... But didn't understand a little also🥲
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
lmao, worked for me without doing anything extra beats 5% too xD
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;
}
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
@@michaelroditis1952 true. I didn't care much after it got accepted.
@@ShinAkuma yeah and it would work the same so no need
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(((
Thank you so much ! I don't think the DP problem is that intuitive.
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
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).
Thank you so much
I wonder why you didn't give the simplest approach doing factorisation
Simplest in coding. Not simplest to come up with and prove why it works too.
congrats
I feel like I've seen this problem before
feel likes the min num coins DP
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.
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
wth i was literally doin this problem for the first time
everywhere i go people are saying they were able to come up with the soln, and here i am struggling T_T.......................................
did he figure out the second explanation himself ?
Don't know why my memoized solution is taking more time than recursion
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
@@elisey4770 I see
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
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);
}
}
ok
Petition to change problem name to Copypasta