2 Keys Keyboard | Detailed Explanations | Leetcode 650 | codestorywithMIK
Вставка
- Опубліковано 12 вер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 99th Video of our Playlist "Dynamic Programming : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good and famous problem : 2 Keys Keyboard | Multiple Approaches | Leetcode 650 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : 2 Keys Keyboard | Multiple Approaches | Leetcode 650 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Recursion + Memoization
Concept: This approach uses a recursive function to explore all possible ways to reach exactly n 'A's. It tries two main operations: copying the current string and pasting it, or just pasting the previously copied string.
Optimization: Memoization is used to store the results of subproblems to avoid redundant calculations.
Time Complexity: O(n^2) because there are n possible lengths, and for each length, up to n pastes might be considered.
Space Complexity: O(n^2) due to the 2D memoization table.
Approach 2: Bottom-Up + Mathematics
Concept: This dynamic programming approach builds up the solution from smaller subproblems. It relies on finding factors of n to minimize the number of steps. If i is divisible by a factor, we calculate the steps needed to reach that factor, then add the steps required to reach i by copying and pasting.
Optimization: By starting from the largest factors and working downward, we ensure the minimal steps are found early.
Time Complexity: O(n^2) due to checking each factor for all numbers up to n.
Space Complexity: O(n) as only a 1D array is used to store the minimum steps for each i.
Approach 3: Greedy
Concept: This approach greedily copies the current string when the remaining target is divisible by the current number of 'A's, and pastes until reaching n. It tries to maximize the number of 'A's added in each step.
Optimization: By always doubling the number of 'A's when possible, this approach minimizes the number of operations.
Time Complexity: O(n) because the loop iterates while counting up to n.
Space Complexity: O(1) as only a few variables are used to track progress.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
Hi everyone, my current streak at potd of leetcode is 103 days. Comment yours....I asked you for your current streak because i want a small group of coders who really want to improve and share their progress. It's like motivating each other😃.....
Now this is for mik........After 103 days of continuously watching mik's video, even though sometimes I solve it by myself but I watch his video just for another approach. Thanks you so much for making dsa very easy😇. You make problems look so easy that even a beginner can understand and it boost his confidence....Again thanks a lot and keep bringing up videos regularly.......(pin this comment if you want😃)
My streak - 198 😁
Streak - 125
68 Days
80
mine is 161..
Hello Bhaiya !! I have been following you since last 3 months. Superb explanation in each video. Your way of dry run made my intuition quite well. Thanks a lot. Also this question can be done in O(1) space, simply by taking sum of all prime factors of any input 'n'.
Below is my code:
class Solution {
public:
int getAllPrimeFactors(int num){
int ans=0;
while(num%2==0){
ans += 2;
num /= 2;
}
for(int i=3; i
Awesome and thank you for sharing. Indeed this is another very good approach and great observation ❤️
class Solution {
public:
bool isprime(int num){
for(int i=2; i
Hi! Loved all your videos. Can u please make a video on Cherry Pickup problem of dynamic programming. You've already made a video on cherry pickup 2
I ama really amazed by your approach 1 recursion + dp , Thank you
Easy to understand C++ beats 100% C++ approach
class Solution {
public:
int minSteps(int n) {
vector smallprimes = {2,3,5,7,11,13,17,19,23,29,31};
int ans = 0;
int k = smallprimes.size()-1;
for(int i = k; i>=0 ; i--){
if(n % smallprimes[i] == 0){
n/= smallprimes[i];
ans+= smallprimes[i];
i++;
}
if (n == 1) {
break;
}
}
if(n != 1 ) ans += n;
return ans;
}
};
Following you since you had 10k subs thank you for helping and being consistent bhaiya😇😇
Also my potd streak was max 169 then i got busy because of my mid sem exams now i m again continuing and my current streak is 56😄
Hello sir, just saw one approach on factorization in the leetcode comments, the code goes as follows :
class Solution {
public:
int minSteps(int n) {
if(n == 1) return 0;
int steps = 0, factor = 2;
while(n > 1){
while(n % factor == 0){
steps += factor;
n /= factor;
}
factor++;
}
return steps;
}
};
the complexity is much better here O(sqrt(n))
Bro what is the meaning of this:
Company Tags : LinkedIn, Amazon
Like ye question in companies k interview me most asked question tha ya this question was asked from a known person of yours?
Same intuition ban gya tha but code mein todha error aa rha tha thanks
I could come up with recursive approach.
2nd approach is really good and clever but it seems it was a basic observation
great bhaiya this is my approach
class Solution {
int ans=INT_MAX;
void solve(int n,int copy,int onScreen,char c,int op)
{
if(onScreen==n)
{
ans=min(ans,op);
return;
}
if(c!='c')
solve(n,onScreen,onScreen,'c',op+1);
if(copy and (onScreen+copy)
MIK bhai please make a video on the greedy approach, mereko ye samjh aaya ki prime factorization se ho jaayega
kaafi logo ka solution, lekin inituiation nahi aaye ki kyun aisa
your solution also I got it , so and so, it might not take much time I think,
kabhi fursat mile toh ...else fine
Easy Approach:- 🤷♂ Beats 100% with C++
class Solution {
public:
int minSteps(int n) {
int count = 0;
for(int i=2; i
Yep this is a good one ❤️
@@akshatyadav01 but can you explain intuition behind this?
Thanks a lot bhaiya ❤❤
//4 Lines only. Thank you MIK for giving me hints.
class Solution {
public:
int minSteps(int n) {
if (n == 1) return 0;
int x = n / 2;
while(n % x != 0) x-- ;
return minSteps(x) + 1 + (n / x - 1);
}
};
Awesome work 🙌
bhaiya i have a confusion please reply to this mai dsa c++ me kr rha tha apke videos dekh ke kyuki apka hi samjh ata and socha tha mern stack krunga react tak kiya tha but college me bola java full stack sikhne with react to ab jab java me spring boot sikhunga and mereko core java ata hai ab mereko main tension ho rha ye soch ke ki bhaiya interview me to java full stack bta rha pr dsa c++ me kr rha cuz aap itna acha samjhata ab kya c++ chor ke java me krna padega ? basic entry level service based companies ke liye ? pls pls reply to this cuz jitne spring boot devs dekhe sb dsa java me kr rhe to aur panic ho rha mai
Hey MIk I think there is another approach using prime factorization which is better than this. Can you make video on explaning that.
It solves the question in o(n) time complexity.
Is this approach is correct?
class Solution {
public int minSteps(int n) {
if(n == 1) return 0;
if(n == 2 || n== 3) return n;
int ans = 0;
for(int i = 2; i
Superb explanation. 2nd approach ❤
Bhaiya please aap ye question bata dijiye na LC. 174. Dungeon Game. It is my request 😇
we want greedy approach bhaiya and y DP , problem can solve using greedy aproach algo we want to seen
in this recursion plus memo, is this top down or bottom up....
I think this is bottom up right, as we are starting from low to high,
if so, is there any way to do in the normal top down way, like n=5 , toh "AAAAA" se "A" le jaana hoga, toh ulta operation lag jaana chayie,?? ( this will be more complex I think )
This is my Recursion + Memoization Approach
class Solution {
public:
int dp[1001][1001];
int solve(int prev,int curr,int n){
if(curr == n) return 0;
if(curr > n) return 1e9;
if(dp[prev][curr] != -1) return dp[prev][curr];
int choice1 = 1 + solve(prev,curr+prev,n);
int choice2 = 2 + solve(curr,curr*2,n);
return dp[prev][curr] = min(choice1,choice2);
}
int minSteps(int n) {
memset(dp,-1,sizeof(dp));
if(n == 1) return 0;
return 1 + solve(1,1,n);
}
1551.Minimum operations to make Array Equal
Can you make a video for this I have encountered many Question like this
But don't understand what to do
There are many other question like this but I don't understand from how to start what is the approach
Can you simply and also tell the general approach for solving this type of question please.
solved on my own. yayyyyy
Bro how can you able to solve DSA questions... Please help me 😭😭
@@ExternalUse-f5z bhai agar beginner ho to pehle concepts cover karlo. Then har concept par 5-10 qns banao. Har concept k lie aisa karo. Jab koi qn samajh nahi aata hai to mai isi channel par aata hu, isse acha explanation kahi nahi milpata. earlier i used to watch neetcode, but since I found this gem, I am addicted
@@gui-codes yes bro.. one thing when I go through solving array by momentum i solve the new question but if you give one dp question then I stuck at that moment......
Either half test passed or not able to identify pattern....
I am in the begging of third year...
sir
int f(int n,int sum,int clip_board){
if(sum>n)return 1e9;
if(sum==n)return 1;
int copy= 1+f(n,sum,sum);
int previous_paste= 1+f(n,sum+clip_board,clip_board);
return min(copy , previous_paste);
} what's wrong with this
Constructive criticism for you -> Your content is awesome and definitely deserves a million views but improve your thumbnails. Your thumbnail designs are very complex(Japanese type) which is not a good practice. Compare your thumbnails with other channels . Decrease the complexity of your thumbnails and make it more simple and easy readable 👍👍
Appreciate your kind words and feedback.
Would you kindly suggest what kind of improvements in thumbnail you believe will be a good move ??
❤️
@@codestorywithMIK
drive.google.com/file/d/1D0foPek4KfgqWJSoRhnWI95593ZFl-OZ/view?usp=sharing
In the image, the upper thumbnail is more effective due to its simplicity. The clear title for "Longest Common Subsequence" stands out immediately, while the lower one is harder to read.
Company names are secondary. A simple, well-colored title is more engaging. As a student, I think most traffic for DSA videos comes from students searching for specific problem on UA-cam after trying them out on LeetCode. Therefore, the problem title is most important, and you can include company names like Amazon or Google in the video title instead of the thumbnail. Prioritizing a clear title will attract more viewers. Thanks for taking my suggestion😊😊
@@codestorywithMIK
drive.google.com/file/d/1D0foPek4KfgqWJSoRhnWI95593ZFl-OZ/view?usp=sharing
In the image, the upper thumbnail is more effective due to its simplicity. The clear title for "Longest Common Subsequence" stands out immediately, while the lower one is harder to read.
Company names are secondary. A simple, well-colored title is more engaging. As a student, I think most traffic for DSA videos comes from students searching for specific problem on UA-cam after trying them out on LeetCode. Therefore, the problem title is most important, and you can include company names like Amazon or Google in the video title instead of the thumbnail. Prioritizing a clear title will attract more viewers. Thanks for taking my suggestion
@@codestorywithMIK
drive.google.com/file/d/1D0foPek4KfgqWJSoRhnWI95593ZFl-OZ/view?usp=sharing
In the image, the upper thumbnail is more effective due to its simplicity. The clear title for "Longest Common Subsequence" stands out immediately, while the lower one is harder to read.
Company names are secondary. A simple, well-colored title is more engaging. As a student, I think most traffic for DSA videos comes from students searching for specific problem on UA-cam after trying them out on LeetCode. Therefore, the problem title is most important, and you can include company names like Amazon or Google in the video title instead of the thumbnail. Prioritizing a clear title will attract more viewers. Thanks for taking my suggestion
@@codestorywithMIK emailed u
Thanks sir for your wonderful explaination...#include
using namespace std;
class Solution {
public:
int smallestprimefactor(int n){
if(n%2==0)
return 2;
for(int i=3;i*i
Well done ❤️
Sir Kindly make it white theme
we can run the loop from 2 also
class Solution {
public int minSteps(int n) {
if(n==1){
return 0;
}
int[] dp = new int[n+1];
for(int i=2; i= 1){
if(i % factor == 0){
int steps = dp[factor];
int copy = 1;
int paste = i/factor - 1;
dp[i] = steps + copy + paste;
break;
}
else{
factor--;
}
}
}
return dp[n];
}
}
But the answer of first test case can also be two because we can paste A two times and it will become AAA so the count is two why three??? plz explain i am stuck in this vey much
One operation needed to copy and another 2 operations to paste , so total 3 operations
bhai ek baat nai smj aayi jab aapne already copy wala operation consider kr liya tha phe hi step mai 1+ return solve() krke in the main function, then uske baad jab copy+paste wali call kr re ho solve function ke andr. wha pe bbhi dubara consider hogya. aaisa kyu? jabki humne copy tou phle hi consider kr liya tha main function mai.
First wala copy 1+ is a mandatory step.
But uske baad bhi to future me copy+paste operations karenge islie copPaste me bhi copy ka 1+ kara hai.
Although copy -> copy+paste will not give optimal answer but copy+paste can also come after some paste operation in future.
bro mujhe bhi same doubt tha but i dry run it and then i understand it. Do dry run once for n = 4 you will understand.
Can we do only copy and only paste ?
The path where you will do “only copy” will never end as your currA count will never increase because you are only copying. So copy+paste is required.
O(sqrt(n)) approach
class Solution {
public:
bool is_prime(int n){
for(int i = 2; i*i
Logic is :
To print any prime number n we will require n steps
take example n = 7
first we will copy(1) then paste for 6 times
So if number is prime , we will take n steps
Now , if number is not prime we will break down it into its prime factorization
eg] n = 105
prime factorization = 3 * 5 * 7
first we will print 3 in 3 steps (copy,paste,paste)
then we will do (copy, 4 times paste) so the number is 15 A's
at last we do (copy , 6 times paste) so we get 105 A's
Very nice ❤️
public int minSteps(int n){
int ans=0;
for(int i=2;i*i
very bad explanation of approach 2,sorry quality is so down now
Hi Aditya,
Apologies if you felt so.
Would you kindly share where exactly you lost me in the 2nd approach ?
I will try my best to share more information here that can help
Let me try to add more details here -
This code solves the problem of finding the minimal number of operations required to produce exactly `n` "A"s on a notepad, where you can only perform two operations: `copy all` and `paste`.
### Explanation of the Code
**1. Understanding the Approach:**
- The key idea is to break down the problem into finding the factors of `n` and then using those factors to minimize the number of operations.
- If we have `x` "A"s on the notepad, and `n` is divisible by `x`, then we can copy all `x` "A"s and paste them `(n/x - 1)` times to achieve exactly `n` "A"s.
**2. Base Cases:**
- If `n == 1`, it means we already have 1 "A" on the notepad, so no operations are needed. Hence, return `0`.
- If `n == 2`, we need two operations: copy the single "A" and paste it. Hence, return `2`.
**3. Dynamic Programming Setup:**
- We create a dynamic programming table `t` where `t[i]` stores the minimum number of operations required to get `i` "A"s on the notepad.
- We initialize `t[0] = 0`, `t[1] = 0`, and `t[2] = 2` based on the above base cases.
**4. Filling the DP Table:**
- For each `i` from 3 to `n`, we find the largest factor `factor` of `i` (starting from `i/2` and decrementing).
- If `factor` divides `i`, then:
- We already have `factor` "A"s on the notepad.
- We calculate the number of steps required to reach `factor` "A"s using `t[factor]`.
- We add `1` step for the `copy all` operation.
- We add `(i/factor - 1)` steps for the `paste` operations to reach exactly `i` "A"s.
- The total operations to reach `i` "A"s is then the sum of these values.
- We break out of the loop as we have found the optimal solution for `i`.
**5. Return the Result:**
- Finally, we return `t[n]`, which contains the minimum number of operations required to obtain `n` "A"s.
### Example Walkthrough:
Consider `n = 27`:
- The algorithm starts with `i = 3` and continues until `i = 27`.
- When `i = 27`, the largest factor found is `9`, and the table `t` will already have calculated the steps for `t[9]`.
- The code will add 1 step for copying and 2 steps for pasting (since `27/9 = 3`, and we paste 2 more times to reach `27`).
- Thus, the minimal steps for `27` is calculated efficiently by considering its largest factor.
This approach ensures that we find the minimum number of operations by leveraging the divisibility of `n` to minimize the total steps.
I think it was well explained and 2nd approach was something which someone can understand well if he/she has good grip in DP bottom up. No offence, but it was well explained
@@codestorywithMIK why we are taking the largest factor first? what if operations required to make that factor will result in more number of operations in the final result?
Secondly , in approach 1 , we are already considering 1 copy operation( 1+ solve(n,1,1)) , and then in copyPaste operation , we are taking 2 operations, wouldn't it take 2 copy operations for the first element i.e. we will get 1 extra operation?