CodeCamp Day 8 | Exploring the Magic of Recursion

Key Takeaways

foreign [Music] [Music] [Music] foreign [Music] [Music] foreign are you sure this course is just for 2499 yes and you know this is the only course with this expertise across the world no way yes way [Music] don't delay enroll now Geeks learning together hi and welcome to Geeks for this today so let me just change the layout yeah it is fine now today is the day 8 of code camp and we would be exploring the magic of recursion so in this stream people who are absolute beginners to recursion can skip this video can gain a little bit of basics of recursion and then come back to this video so if you are a very beginner so I just don't want you to feel cheated that yes this is not the very first one so yesterday we have already explored recursion this is the day two of it so we intend that we would be solving some standard problems over recursion so the basic absolute basic problems like printing the numbers from the front and from the back Fibonacci numbers won't be done here we would be doing the standard questions of recursion so this is a part of gfg code cam which is intended for you to build a coding Habit in just 21 days where for 21 days we will be solving problems in the live stream itself for the for the next 21 days we started off at first okay like the we started off at around ninth yep so we started off at around nine this is the day eight and we are continuing every day there are still some people who are continuing there have been many people who lost count and now they are following it in the recorded version and some people lost their motivation too so this is a hard process and you need to be well acquainted that this is not going to be easy because it's just that simple okay the very next thing is today is recursion of the very first problem they would be doing is this one let me just show you this prism the screen share screen your laptop many people are there how many people are there from the first day to utility for the very first problem we would be doing is this one okay we can just remove this thing and this is a very standard problems and this has been arched on Walmart and make my trip so basically it has been worked better one companies and it was a very famous problem like the idea that is the backbone of this problem comes handy to a lot of problems okay and you need to learn this idea and the very next one is this one this one is kind of the very famous problem asked when we talk about recursion if we talk about little bit hard problem of recursion then we talk about this this is not basically hard but I can say that this requires a little bit of analytical thing so as we can okay so thoda white background is a white background black okay let's take the black one only let's do it um and this is cool okay so let's start anyone has any queries so first read up this problem okay and then we would talk about how to solve this problem just take a minute or so I would be just waiting for the next one minute and then we would everyone okay like they are following but were replied okay yep this person also arushi Tomar okay fair enough I understood the problem statement I am from the second day oh yes I remember you also brother sugar let's see this problem so what is the first sample test case the first sample test case is 2 and 12 okay before this there are things to understand okay like this would include some Concepts foreign okay so here we are told maybe background this is looking a little bit elegant so here in this question we are told that number there okay we are given a number okay and then what we need to do is basically the very simple thing would be that we need to reverse the number and then we need to return the power of the universe okay but but there is a small constraint that needs to be respected we need to return it modulo 10 to the power 9 plus 7. okay so let us take some few examples and then we would say see we are given two two reverse that would still be 2 so 2 to the power 2 is equals to 4 and 4 modular 10 to the power 9 plus 7 is equals to 4 only what is this modulo the modulo operator Returns the remainder okay so what is modulo operator is done now let's take some more examples then we would learn everything like this is the Beast like we would start from the very basic and then we would go to solve the question okay now the very next thing is just the prerequisite is at least basic understanding oh how the recursion work what is recursion rate what is recursion and what is recursion trip recursion treatment the visualization of recursion in parent paper is known as the conscient tree not just pen and paper be it in anything the visualization of the question is known as in the form of trees is known as recursion tree just how recursion works in the back end is something a function calling itself with different okay so then we are told key let's take the value of 15 okay 15. so the reverse of it would be 51 so how many 15 to the power 51 then we need to do something module 10 to the power 9 plus 7. okay so let's just first talk about power so let's say we have 3 to the power 4 so 3 to the power 4 is nothing but 3 multiplied by four times this is what it is same way 5 to the power 3 is 5 multiplied by 5 multiplied by 5 6 multiplied by 7 is equals to 6 multiplied by itself seven times okay that is 6 multiplied by 7 this is what it basically means uh some extent we would talk about this modulo thing at the end okay yeah this is to be explained at the end is okay so let's say I ask you let's say the value given is X and the reverse value of x is equals to y so mechanical name we need to return x to the power y up for now just ignore this mod okay let's say the mod was not mentioned okay so now let's talk about the next thing x to the power y Cafe very simple again 5 multiplied by three foreign that just basically means lump power times so if we have something like x to the power y then we just can say that X multiplied by y times okay simple you say y times Saturday let's keep it simple we like I won't disturb you a lot more submit this easily so I multiplied by X multiplied by 10 so the time complexity would be nothing but Big O of Y okay the time complexity would be Big O of Y of socialism let's see the problem statement now okay problem statement okay without even submitting just by thinking problem statement 10 to the power nine okay on the expected value is also login if you are a beginner you can focus on this if you are not a beginner if you're an intermediate or an advanced person you need to focus on this okay so big off and many we need to do something in login why because for people who are beginner and advanced key in one and we know that we can perform 10 to the power 8 operation in one second so big O of n would be 10 to the power 9 which is more than 10 to the power 8 so we would be getting a time limit exceeded if we do this if you are a beginner Advanced if you know if you are a beginner who is who didn't understood my last thing can simply understand that I may login okay x to the power y seems simple okay how can we do it in login okay to be honest if you are for if you are first coming across this algorithm then it would seem absolutely okay this there is an algorithm to do x to the power y like in a fast way okay that is first exponentiation method first exponentiation okay or modular exponentiation okay to be honest first exponentiation and modular exponentiation is the word that we basically use anything you can use but first exponentiation I think it is very much relatable okay exponentiation what is this algorithm talking about let's say I have 5 raised to the power 25 so other if we solve this in the classical method then we would be multiplying five five times and the number of operation that would be performed is 25. if we perform the traditional operation okay like traditional way of solving it classical way of solving it and the number of operations will be 25 okay first tell me am I clear till this point or not coffee simple but as this is the weekend it might be a scenario that you are not in this zone of taking more okay so I would try to make it much more easier first tell me if this still this thing is clear or not up till now it is clear or not first tell me this thing and then we will move forward it is what about this 5 to the power 25 so 5 Core 25 by multiply karna if suppose we have 3 to the power 4 that just means three three three so multiply that now so in the same manner five times yes 25 times not five times okay now let's move forward so see this with care okay just understand this okay so what I can say is 5 can also be represented as how much 5 can also be represented as 5 multiplied by 5 to the power 24. okay fair enough now we have something like 5 multiplied by 5 to the power 24. what to do in this scenario what to do JavaScript and even give me a picture if you just turned on the previous stream yes now is [Music] what we can do what we can do is 3 to the power 4 can also be written as 9 to the power 2 because I can say that how it is 9 to the power 2 let me just show you that also it can be 3 to the power 2 multiplied by 2 which is nothing but 9 to the power 2 so I can do it in the same manner 5 multiplied by 5 to the power 2 and to the power 2X I can do this now let's come to the next point okay so now here I can say that 5 multiplied by 5 to the power 2 multiplied by 5 to the power 2 and hold multiplied by 6 B this is still 24 how 2 to the power 2 let me just show you 2 multiplied by 2 4 4 multiplied by 6 24 so still Avita K 24 value yeah 2 multiplied by 2 4 4 multiplied by 6 24. okay so now let's move forward okay so now again see 5 multiplied by 5 to the power 2 to the power 2 to the power 2 and this whole thing to the power 3. okay just see how am I doing it foreign so this is not a even number okay coming even banana yeah what we did was Here If You observe we had 25 what we did was to make it even we took out five because it can be clearly shown that suppose we have line 3 to the power 3 so it can also be 3 multiplied by 3 to the power 2 and that is same okay same base Powers would get added so in the same manner what we can do is we can kind of do this thing foreign we can do five like Joby value okay this value 5 to the power two two multiplication [Music] to the power 2 okay now oh no as you are guessing this is again an even number so I can say five multiplied by 5 to the power 2 to 2 multiplied by 5 to the power 2 2 2 . okay so now see this see this whole idea and give me a quick one okay and let's count the number of operation we did one two three four five six so we are able to find the power of 5 and 6 operation okay not writing the values because this would look a lot messy so six operations by using fast exponentiation first exp we were able to do it in six operations now tell me do I make sense to you or not [Music] um twenty four twenty four twenty six any mistake okay now let's see how did we do it in two steps and what is the logic of doing it in two-step let us understand that also update okay so when we were having see when we were having a even value um then we are multiplying the base see this is base and this is exponent okay okay so Hamlet is base cohere multiplier this basically multiply that there we are just multiplying the base okay if it is a odd value we are trying to make it even but taking one outside because if something is 5 so we can say 1 plus 4 so this 4 value would be even so we can multiply the base and the power would be divided by half okay simple side so we would multiply the base and the power would be written divided by half if it is odd term logic value to make it even so to remember this you can visualize okay fast exponentiation is nothing but foreign okay so I would just cook up a story so that you would be able to remember it for a longer period of time fast exponentiation go even first exponentiation foreign [Music] foreign he knows a method he knows the trick of mathematics that if something X2 if something is powered to an even number then he can simply multiply the base then he can then he can simply multiply the base and the power would get divided by two or and he knows just this so whenever he was getting he got 12 that is an even number so he multiplied the base he got 6 he multiplied by the base and power got divided by two but when he got a 3 he knew that I know it for even but this is odd so to make it even he took out one base and now it is even again he did the same thing and that become 2 divided by 2 that is equal to 1. will you be able to remember this and then we would talk about the time complexity of it we would see how to implement it we would see the modular part of it and then we would move forward to the implementation and this question would be done by the way this is trying this is not an easy algorithm as easy am I trying to show off the hard algorithms everything is interesting okay more harder it is more interesting it is that is why you can just see this so now just see this and tell me if I am clear to you or not will you be able to will you be able to remember this okay see how it is easy okay it is very easy why because instead of doing 25 the operation was just six direct fifty thousand fifty thousand to twenty five thousand one lakhs at fifty for twenty five twenty five seconds till it is even okay till it is even so to understand the time complexity of this you don't need to do so much you just need to analyze up Social suppose we got a value as 10 10 let's take a value like 100. so 100 would become 50 after the first step 50 would become 25 after the first step 25 would become 24 after the first step and this would get 12 and this would get 6 and this would get three three would become 2 after the first step and then it would be converted to just one so a big number like 100 what are the number of operation one two three four five six seven eight nine a big number like hundred can be just done in nine operation and you can see for it yourself so up if You observe if you like don't need to observe to be honest just make it a habit that if anything we are dividing at by 2 at each step just a binary stretch we learned about binary stretch at each point the search space was getting divided by two we learned that so the time complexity was log base 2 n we are dividing it by two so the time complexity would be nothing but but as you have guessed this is log base 2 m C it is a simple algorithm just care fact use if some number is multiple if some number is raised to the power of even then if we just multiply the base the power would get divided by two it's small mathematical factors and indeed it is very interesting not how it is considered as an advanced algorithm but it is indeed a mixed like it's interesting algorithm okay so multiplication in less time complexity so Joe intended this more thing okay what was left this just a sec my manager at gfg is calling me hello I actually uh but like the manager of minor Geeks for geeks is much more like a big brother to me like we know each other for a long period of time around more than two years now so we don't have that official thing I just call him we have a so he wants to come home to just collect his his documents Okay so okay so by the way if you want like if you want now we are understanding some difficult Concepts and if we are following this stream religiously it might be a scenario that you want some notes and you are not able to take it so what you can do is you can simply ask me that Siddharth can you just send me the uh scribbles that you have used in the class and I can just give you that so that you can just whenever you would come across the same thing you can just refer this the video won't be required to see the whole damn two hours no and the very next thing was we have we had something like x to the power Y and that was modulo mod okay that was modulo mode so there are four like you need to understand a plus now you need to know first a plus b um modular mode you need to know the formula of this a negative modulo mod and then a divided by B modular mod and this is very important because it it involves you extended equilibrium algorithm it this is very important it involves the usage of extended equilibrium algorithm and it also involves the usage of ferment Circle theorem and these two are very easy these all are not required what is required is we require this I would just teach I would be teaching you everything that is required okay so we require a multiplied by B in modular model you need to learn all this remember it okay this is a homework for you so a mod a multiplied by B modular mod is nothing but a modular mod multiplied by B modulo mod and hold down thing module mode here this is the formula so let's take the scenario so if we have something like 5 multiplied by 3 modulo 10 let's say so that would be five modular 10 multiplied by three modular 10 and whole modulo 10 itself so 5 modulo 10 is 5 3 modulo 10 is 3 and hold down modulo 10 is equals to 5. so this is how this formula would be used okay so am I clear with this thing just ask me it might be a scenario and that is fine just tell me if this small thing is clear or not and then we could move forward problem is similar to trailing zeros or you can ask others also okay this is pretty simple to understand so we would be understanding thanks a lot for understanding thank you thank you thank you so much Ebola okay so um so this thing implements see implementing this thing is very easy because the formula okay but implementing this thing what would be basically the idea what would be the pseudo code of this so let's understand the pseudo code of this yeah this is just by using loops and all so let's just directly implement this so we would multiply the base of it if it is odd we would take out the base outside and this is enough yeah let me charge this is Apple products apart from Mac and iPad the battery is very pathetic with more or lesser all other Apple products power of numbers um [Music] [Music] I would just make this lowercase n and lowercase R so that I don't need to hit the shift again Okay so okay we would write the base case okay first as we need to return this in long long so we would make this as we would make this long long so what we basically need to do is we require so we are given what you don't need to do that for denoting the input and its reverse and Returns the power of n so we are already given the n and the reverse so we don't need to reverse anything okay so now calculus it says we can write long long y and then we can see if x to the power y okay let's make this x to the power y a is this would be more relatable okay now if x to the power if Y is even Y modulo 2 is equals to equals to even so do something like 9 to the power 3 to the power 4 can also be written as 3 multiplied by 3 whole power 2 so that is nothing but answer is equals to answer is equals to mod like power powers hmm [Music] let's make a little bit about the front of this let's make this array let's make this a rapid function it's called explicitlyn okay so we can just pass on this values okay fast exponentiation so F EXP speech okay and this would be x to the power y and here we would have the same thing long long answer okay 3 to the power 4 right so it can be also written as 3 to the power 4 can also be written as 3 multiplied by 3 to the power to the power 2 4 divided by 2 so in the same manner what we can do is if Y modulo 2 is equals to equals to 0 that is if Y is equals to an even value then we can say answer is equals to f e x p f e x p is long wrong okay let's not operate over X and Y so we can simply write X y divided by 2. okay you can simply say this okay and you'll be answer we can just multiply it answer is equal to answer multiplied by answer simple Okay click 3 into 3 multiplied by 2 is nothing but 3 to the power 2 3 to the power 2 3 to the power 2 multiplied by 3 to the power yeah okay so that this number is not growing up to reduce the number value okay and it might be as soon as it is more than 10 to the power 9 and we are not able to handle it here okay just remember this is now click on product Foundation it is odd okay Y is odd so if something is X to the power x to the power y then if it is nothing but X multiplied by x to the power y minus 1 okay X multiplied by y minus 1 because x x bar again okay so we can say something like answer is equal to answer is equals to first X modulus X naught this is as of now we want practice and 3 is equals to answer is equal to answer answer is equal to X X multiplied by X multiplied by f e x p to the power x to the power y minus 1 okay and the same is correct okay answer is equals to just this and then we put it on something like whatever the answer was okay and create an answer this is the thing so I'm okay with this approach just tell me that and here we can just create around the value of return at EXP to the power n comma r Justice now tell me do I make sense or not um just tell me this if I'm clear can I get can I get friends here for coding collaboration absolutely so your way of explaining is amazing thank you so much it was explaining an amazing it may be amazing okay I'm late will I I will see the recording version of this question sure all the best absolutely so I'm here till this part um okay I was just kidding that's absolutely nice okay so now there are some base cases one one one divided by 2 is equals to zero last one so one divided so one we stopped we stopped like when we see this thing when you see this thing okay this is no this won't be visible sorry Okay so if we see this thing okay if we see this then okay yep let's see when did we stop we stopped when the power became one okay so now power became one so away I must stop so once you come here zero after we would say if x is equal to 0 then we would return 0. simple both cases if Y is equal to 0 to return one why why because anything to the power 0 is equal to 1 5 to the power 0 is equals to 1 10 to the power 0 is equals to anything to the power 0 is equals to one so if power is 0 then we would return one if the number is only zero foreign if you want more thing go applicable how we would make thing more thing see here the value of mod is already defined so we can just use mod in place of 10 to the power 9 plus 7 so make sure you see this so wherever we are multiplying anything we would apply mod at that point so you have a answer multiplied by answer so X multiplied by Y is what a multiplied by B modulo is nothing but answer modular mod answer modular mod and then whole modular model simple together so you have a b we are multiplying anything okay yeah maybe we are multiplying so this modular mod this modular mod and whole thing modular mode oh yeah and then we are returning the answer so answer with what we can do is answer plus mod and modular board if you're not understanding this small segment here just learn about modular arithmetical feedback and then you would understand if I explain you you won't be able to understand this is a very small concept if you do the things that I have said this would make sense so your last name is nothing but model answer this is so now let me just see and we have the correct answer I you should do it on yourself concept you should do it on yourself so I would be providing you with the function okay copy power of numbers tell me the line number tell me the line number at which you are not able to understand tell me the point at which you are not able to understand quickly again if you are able to understand give me a quick one is I don't want to rush don't worry [Music] okay I think I'm clear because I didn't receive any chat for the last one minute so I think I'm clear just quickly like the video what is permutation unique permutation of the given strength permutation is nothing but the reordering of the alphabets lexicographically sorted automatic dictionary order there are the two things that you need to understand just see the problem statement and then we can move forward just quickly tell me if I'm clear to you or not thank you okay here sure let's understand this [Music] okay yeah charge [Music] yourself [Music] here we are told that we need to find all the permutations of a string so what is basically permutation permutation is nothing but the output that is generated by rearrangement of the alphabets in the string itself so what do I meant by this so let's say we have something like ABC if we just modify the arrangement of A and C let's just swap the values positions of A and C that would be c b a so basically CBA is nothing but a permutation of ABC so in the same manner if we just swap the position of B and C it would be a a c b so this is also a permutation of ABC if we swap the values of a b this would be b a c so now let us understand so this is basically a re permutation so that is permutation and what are the different permutations ABC has so let me just show you those also so we have a b c itself first we can come across ABC ABC I am a permutation of myself first then b a c a permutation and then c b a a permutation okay then a c b permutation okay so a for permutation only still we have many permutation what is something like C if okay c a b b permutation so we have got five permutation what is that is nothing but Bachelor of Computer application BCA okay so these are basically all the permutations of the string of the string itself okay yeah yeah no how to solve up this ABC again specifically so the very first approach you can use to solve of this problem is by using the inbuilt function of C plus plus that is nothing but just search it make a Google search of it and let me just do it for you that is nothing but next foreign so you can simply write this because you can directly use up that Yep this is mentioned a very important thing that is mentioned a very important thing that is the number of permutation is three factors ABC so we have the number of permutation as three three factorial three multiplied by 2 multiplied by 1 is equals to 6 that is why we have six permutation Okay so very first way was directly to use next permutation as the number of C plus plus is not the very majority and all of you just don't use C plus plus multiple use different languages too so I am not explaining that approach and to be honest that approach is not acceptable by an interviewer because whenever you use an inbuilt function the interviewer will definitely ask you can you do this without using the envelope function most common question okay so how to solve this without using any animal function it can be solved basically so we have a b c okay so if we swap a with a if we swap a with it it would be ABC if you swap a with B it would be b a c if you swap a with c that would be nothing but c b a so how many we are first we are swapping a with a then we are swapping a with B then we are swapping a with c so here I can say that in the first step so it's have this so I can say in the first step we did something like this so this is the outcome of the first character first character this was the outcome of the first character now we would do the same thing with the second character we would sub B with B that would be nothing but a b c and then we would say B with C that would be nothing but a c b then we would sub a with a that would make it b a c then we would stop if it's c that is nothing but b c a and we would do the same thing B with B that is making us BCA B with e which is nothing but c a b okay now we come to the very last characters a third that is we would say C with C that would make it a b c we would sub B with B that is the last character with the last character last character with the last character last character with the last character b c a last character the last character C B A last character the last that is c a b so this was the result of the second character this was the result of the third character okay so this is how we can get all the permutation of ABC at this point okay first character circuits episode okay and this is how we can build up all the permutation by doing this simple thing do I make sense give me a quick one just give me a quick one if this makes sense to you throw the quality just give me a quick one if I'm clearly anyone who is not able to understand give me a zero I would be more than happy to draw the equation three for one more problem one more sample test case okay for everyone this is clear then we won't repeat the same thing so yeah okay let's understand this what we can basically do okay or something let's understand this problem okay problem the problem is that let's say this Israel okay he is in the first year okay now let's say siddharthur is a very spoiled brat his father has a lot of money or let's say his father is has a lot he has a constructed his father has a construction company so he doesn't he thinks that he doesn't need the job of his own so he went on with his college life he did all the wrong things he can do and now Siddharth hazrat is a spoiled brat okay spoiled by on the end of the fourth year like by the end of fourth year he is he is basically a failure in life okay he is basically a failure in life now Siddharth azra realized this in the fourth year so can he jump on like now he wants a placement in the end of the fourth year it is already the end of fourth year and he is a spoiled child so at the end of fourth year he can't get a placement the only thing that he can think of doing is the only thing that we can think of doing is to reverse the time like like when we made a wrong mistake and the time is gone there is the max thing we can think of is Rael do a lot of hard work and evolve as a person who is satisfied with himself okay so he needs to go back to his previous form of first year so that his reward at the fourth year and this transition this transition if you understand he spoiled to goodness this is what our parents say and this is true indeed when we grow up we realize this thing that once the time is gone it is no more and I am a spoiled brat then by no means I can get a good placement because even though I work a lot hard still I would be questioned that why do I have a year Gap also my grades would be lot bad I won't be able to set for Max of the interviews and I would face a lot of difficulty so yeah so the only transition we can have is sorry the only transition we can think of is that we need to go back to time and then we can become a good person so much for how many of you this example is clear for how many of you this example makes sense how did you come to this approach like recursion okay so basically if You observe that when I wrote down the ABC thing I found out that I need to explore all possibilities okay so whenever you come to the conclusion that you need to explore all possibilities in a string or in a particular question then you need to use something like recursion explore all possibilities by the way Poonam chori that's indeed a commendable job that you followed my suggestion and make sure you keep doing this to everyone out there teaching so that this teaching would get better so for how many of you this example you are able to understand we have an example that first year thing okay so many of you are able to understand I think so because I got no zero and this is the indeed uh a relatable example so if You observe this in the same manner I will teach you so much things let's draw this ABC thing we have a B and C the first what we did was we replaced a with a that is making it as a b c then we want to replace the first character with the second character so a with B so that would make it v a c then we want to replace the first character with the last character so X is notice here that we are replacing that in the original part first is foreign okay this is what we need to do if I try to do this I would draw that with a different color if I want to swap the first character with the last character in this one originally answered originally the answer should be a with C that should be C what will be half we would have something like first character the last chapter if we just swap that it would be how this got turned on it would be c a b so you're wrong here yeah right not this so if You observe that form fourth year [Music] so we can't really use the modified string but we need to use the original ABC is known as a sister node this is known as the parent node like sibling this is our sibling and this is known as parent in a tree okay so basically we can't Transit from siblings to siblings but we need to swap the values in the parent s post modified strings do I make sense yep yeah like this thing out there like this thing is all rotated in my home okay that Diwali rights okay so they are enough it's okay we are not making a transition we are going back to the string making a transition and then we are coming back this is not working we are making a transition from the parent to the next sibling okay parent to the next sibling that is why this is POS this this parent thing is possible so let's come back to this instance foreign there are many hypotheses around the world that we still have a time machine or something but practically we don't have it but we have that in programming and that time machine thing is nothing but backtracking so whenever you come to the conclusion that you need to preserve the original form and then move from the preserved form that is the point at which you need to use back structure backtracking is nothing but a small bit of understanding over recursion this is the most simple definition in Lehman's language of what backtracking is backtracking is nothing but a small modification or a better understanding of recursion is known as that trick for me it is backtracking the book is definition of backtracking is different but for me let this understanding Okay so yeah backtracking so we need to trace back foreign okay okay so if we are at the first index then we are swapping it with the ith index only Italian then we are swapping I with I plus 1 then I plus 2 and we kept doing this until the last index we kept doing this foreign this tells me that when I'm at the last element when I'm done with the last element I have the values we need the original foreign we had ABC then we swapped the values of a with synthia sorry sorry the value of a and C so we had c b and a okay so if we want a time machine suppose modified string is now this we don't have this thing we don't have this string so we can have the original strip from this string let's say me and my girlfriend went out for a dinner okay and let's say this is towards the door side okay this is me and this is my girlfriend okay now let's see let's say my girlfriend told me that that let me sit on your place so now this is my girlfriend so my we me and my girlfriend swapped position so now the position would be this would be my girlfriend position and this would be my position okay now after swapping that she is telling me Siddharth I it didn't turn out unexpected I want to sit where I was sitting so I just told that yes kindly swap the back swap again if I swap again she would be at her original position so here again this here I would be sitting here and again I would be sitting here so if we swap two times this just gives us a conclusion that if we swap something two times then we are having at the origin we are having the original thing foreign if we swap it back again it would be ABC again and then we can process again and then we can have the output string so from The Sibling also we can generate this okay here we talked about that siblings but we have a way what we just need to swap back again okay so that would be the original position just remember that how SWAT Back original position this is the visual representation okay just okay this is if I just told you in the forms of replacement or swapping it back you won't understand it yeah funny thing you would be able to understand okay but these are all the things that you need to understand let's just sum up everything we found out that first character first I to I plus one I say I Plus and then we found the way also we would just swap back it when we are at the last index we have the value okay these are all the considerations that you need to understand you don't need to understand much okay now let's move to the coding part and you would how did you know that that tracking was used here I gave a very I started with an example first I started off with an example and then I just showed you what is happening in this recursion tree so where you present earlier where you present earlier like everyone else who was already present just can you quickly reference that you know how the backtracking came to the came to the reference just tell me quickly that backtracking the chapter were you able to understand and Mama please okay yeah you just joined because we are now moving on to the implementation okay so let me while we before we start let me just read okay I'm quite impressed with young men I'm a retired I am a retired theoretical scientist and I travel that's an honor sir I loved your taking reference so you can still keep loving it because that my teaching reference is still not passed by the way thanks a lot I was just kidding okay you can explain multiple approaches of the problem um multiple approaches the first approach can be using an inbuilt Library the very next word can be a very simple like recursion with backtracking and that would solve the purpose foreign [Music] again and again so to make the function simpler and easy to understand I would declare I would kindly copy like I would copy the value of s in the Global space Global space so that we don't need to pass it from look we can just take it from them okay fair enough now I would just take this this we would start from the very first okay so let's start doing this okay so we would have lack of recursion of n type okay if we are at the last so if we are at the last Index this is my value okay so we would say if I is equal last index matala what array is 0. so last index would be n minus one already know this this I is equals to equals to x dot size minus 1 if we are at the last MX then we would as of now just write here print it would print here the value of x as of now let's just keep it okay well last one is then let's understand else condition if this is not the last index then what we need to do we start from that index and we keep doing I with i i with I plus 1 I with I plus 2 till the end of I minus n minus 1. so it would start a formula so we would initialize and I and D is equal to I S Plus you can just keep it J also you can instead of I you can just keep on that as let's keep it okay this is done so first I would swap okay I would swap the values of s of I with s of IMD if you don't know if you don't know about swap then we learn about how to swap the numbers okay first we are circle then we are calling it for the rest of the index now the next note the next node can be drawn up now we need the original version also we need the original version so we came out from first year let's say this is a spoiled child okay this is a spoiled brat okay this person is a spoiled brat he went forward to the fourth year and now he is a spoiled brat now I want I want to go back to the time machine and I want to sit at the first year so what I would do is swap back s of I with s of IND again short practice my girlfriend is like my position so now she's telling Siddharth this is not feeling what I was expecting so kindly just switch back so that I am at the original position this is time machine okay time machine to the original version okay and this is done okay now we would start from the very first index Red Cross okay and then we would have something like no If You observe this would work if the values are used so if the values are unique you would get a correct answer but here we might have duplicate values also okay what I want to convey is this is the file but um okay so now instead of ABC okay let's just have AAC so you would understand you would see a different scenario a with a would make it AAC e with 60 would is also AAC is what c a a and now we need to have the next thing the first character with the first character and the first character of the next character first character with the first character would make it AAC and first character the next character is a c a this with this is AAC and this with this is nothing but a c a this with this is c a a and this with this is just CAA again so now if You observe okay these are duplicates AAC AAC or duplicates okay and then then aca aca is a duplicate and then CAA and CAA is also a duplicate okay so how to combat this thing the most simplest way would be okay this can all be handled by recursion but as of now don't expect you to do the most simplest way would be to just have unique so I want uniqueness so if I have multiple duplicates and I want to get out the unique value so if I have 2 2 1 and my interviewer tells me that I want only a unique values so what I can do is I can simply hash out the values okay by simply okay so this is just like like you went out to the market okay you went on a market you brought five kg of potato 5 kg it's like 3.5 kg 3 Kg of brinjal okay so how do you really find out the all the mother asked me what all vegetables you brought so I just said her like I brought potatoes and I got Ginger can say we are just hashing out the frequencies in the same manner if I want to count out the unique values in proto 1 so they can hash 2 multiplied by 2 and 1 multiplied by 1 and we can just have these all values and that would tell me the unique values so here what I would be doing is we already have something like set in plus plus if we insert something in the set then duplicates values are not inserted so set automatically does the task of making it unique all the duplicate values and what you get is an unique value so we would just insert everything that we are receiving in this set that's the most simplest explanation um one day you were talking about a video lecture one day you were talking about a video lecture as well where can I find your teaching reference as of now my teaching reference in a public platform lies only at Geeks for geeks YouTube channel I'm planning to build a YouTube channel of my own but I'm not really getting the idea of how to making it how to make it unique because I don't want to be in their address many people are better than me that better than me in that but but but the very next thing is yep sort it first and Skip all the positions and handle duplicates without set yep you can do this this is an homework but I don't expect you to do this at this point if you are learning backtracking for the very first time so I'm taking things into consideration I'm not making it super hard or something but the the correct approach would be what I think go away okay so here what I can do is foreign done now we need to return here vector and we have a set so take out all the values from the set insert it in the vector so that uh okay so we have something like answer again sorry and then we put return on the value of sorry now you can see it will help getting correct output or not we are indeed getting a correct output do we need to have sorting or something should we sorted no set stores the value all the winning values in the sorted form so sorting is not limited it would be automatically sorted but if you are handling this without set then you need to sort before returning the answer the question talking about the implementation of mine I would just give you this thank you so now I would be waiting for the next one or two minutes if you have anything to ask other than this question you are most welcome to ask if you are not able to understand at any any line number just tell me the line number I will explain you that part else if you're well understood give me a one at this let's send this on a good note line number 12 okay what is the line number 12 if we have reached the last node okay so again suppose ABC V swap t with a then B if first to the second third character and when did we saw when did we stop we stopped when the last character was worked with itself we stopped at that point if you just recall the reversion tree so that is why if we are at the last index then swapping the last index with last index will make a difference like if you have something like APC the last character is C so if we swap c will see that would still be the same agar hamare pass ABC here or last character come last character says so in the same manner instead of swapping the last character with last you can just confirm that yes this is the answer and we can insert that in the set do I make sense to you do I make sense to you and if you are done with this you can give me a quick one if you want it want to ask anything other than this then you can just move forward by the just a small bit of observation okay so why simply not starting won't work privately whereas if time permits why sampling not working same characters won't work to about duplication uh swapping the same character might work it can work okay it can work I'm not definitely sure because I didn't submitted can work and you can think of it as well just try it for yourself I'm not that greatly confident because I didn't have this simple approach but but I can like okay so what is the making condition what that's the baking condition as well yes conditions just observe the leaf nodes where we are stopping and that is that is the base condition foreign that swapping the same with same okay like a with a it might be a scenario that we have a duplicate at this side of the recursion Leaf node and this side of the recursion of the D flow I am not confident that they would be different foreign [Music] explanation okay foreign so I don't feel like thinking again to this problem okay most welcome okay by the way just a small bit of realization because this is d8 and kind of your mid like if you are able to surpass this so I will just give you one thing so so many people like if You observe like this is the thing that should be a realization like everyone wants to know how to how to code okay everyone wants to know how to code but no one really goes when the code thing has happened that is why if You observe that road maps have more views than tutorials or the editorial of the problem and I see no harm in this but the problem is with the mindset let's see everyone is doing for its own good I am teaching at this point of the hour because I think that I'm good at teaching and I might do something good at it even though I have a full-time job which pays me well okay so everyone has their own terms and conditions some people do charity but majority of the people out there are not here for charity okay so thing is they want to raise a YouTube channel even though they are doing a charity and if you are giving more views to the roadmap rather than real problem solving they would bring more road maps okay the problem is with the mindset so what you want is what you get out there on the internet if you are liking reels so people would the content creators would start making reels and shifting to reads so so next time try to promote more the original teaching part rather than the roadmap part so that the beginners who are readily seeing five road maps in a day are not deflected okay because the roadmaps are getting more views much more views like I can say exponential views than tutorials so if a newbie is coming into this YouTube era you would see so he would move back to that so try to like I'm not trying to say just promote my video I'm just trying to say everyone out there try to promote more problem solving rather than just roadmap because when I started off with the day one of this code camp the number of live viewers went above around 400. and now it is just 22. okay so this is how people gradually drop off okay and say that programming is hard but you need to work out okay so I think that's it for the day can you please see how many promises I saw for a single topic approx five to ten problems are enough do more random solver okay so that's it for today good night everyone happy weekend tomorrow devashish Curry will be the person responsible for taking this string thanks a lot for the great response over gaurav he indeed teaches well but thanks a lot so that's it for today good night so if you're watching this stream in the recorded version kindly like and share this video so that the reach of this video could be increased and this hard work could be justified that's it for today thank you and have a nice day