CodeChef Starters 240 | Video Solutions - A to D | by Vikas Soni | TLE Eliminators

Added: 2026-05-28

[00:00:00]So, hello everyone. My name is because only and I welcome you all in this post contest discussion of code chef starters 240.

[00:00:11]So, let's start our discussion by solving the first question which is comfortable sitting.

[00:00:18]So, in this question there are n people standing in a line and the i-th person has a friendliness value of AI.

[00:00:27]And you want to fit n people around a circular table and a sitting arrangement is called comfortable if every person has at least one neighbor whose friendliness value is less than or equal to that.

[00:00:41]And we have to determine whether a comfortable sitting arrangement exists or not.

[00:00:48]And the constraint for this question are like test case number of test cases are 100.

[00:00:54]The size of the array is 100 and the value of L uh the elements are 100.

[00:01:01]So, yeah, there is nothing much about time complexity.

[00:01:06]Okay, so yeah, let's analyze this.

[00:01:12]So, the name is uh name of the question is comfort table sitting.

[00:01:24]So, in this question we are given an array. So, assume that the array is something like this.

[00:01:32]The values are like A1, A2, A3, A4, A5.

[00:01:37]So, you just have to place them in a circular arrangement. Let's say arrangement is like this.

[00:01:49]Such that for each person there should be a neighbor which have a friendliness value less than or equal to its one. So, like for this A3 either either the value of A1 should be less than equal to A3 or this A5 should the value of friendliness of A5 like should be less than or equal to A3. So, at least one condition should be satisfied for this.

[00:02:19]Like for this A5 uh it should be either greater than or equal to this one or either greater than or equal to this one.

[00:02:28]So, and we have to find the if if some some arrangement exist or not.

[00:02:36]So, let's analyze some test cases for this and uh the first uh Okay, so let's analyze some test case.

[00:02:45]So, let's assume that the our array is like this 1 3 5 5 6.

[00:02:55]So, now like if you try to have a sitting arrangement, you will find that this one is the smallest value.

[00:03:05]So, your whatever the arrangement is the neighbors of one are going to be bigger than one, right?

[00:03:13]This one because each value is bigger than this each value is bigger than one.

[00:03:18]So, like if you have arrangement like this still you can see that uh both of its neighbor are greater than this one, right?

[00:03:27]So, you can see here that the sitting arrangement is not possible because every value is bigger than this one.

[00:03:41]Okay, so this is our first observation, right? If uh So, our observation one which is if the minimum value has a frequency is equal to one then solution is not possible.

[00:04:18]Because in that case, each value is going to be greater than the that mean value.

[00:04:26]Solution is not possible.

[00:04:31]Okay, so yeah, we Now we know that uh uh the array is something going to be like this. Let's say two two four five six six and something like this.

[00:04:45]So, yeah, we know that the minimum value has frequency greater than one.

[00:04:51]So, now how you are going to have an arrangement?

[00:04:54]So, yeah uh the easiest way you can see here is just uh put them in the sorted way.

[00:05:03]So, like you put it something like this.

[00:05:06]Because if you put them in a sorted way, you can see that like for seven the lesser value is six here, which is its neighbor. For this six its left value is less than or equal to six and this value is also less than equal to uh this four is also less than equal to five.

[00:05:25]This uh uh for this four, the two is also less than equal to four.

[00:05:31]For this two, this is also less than equal to two.

[00:05:35]But only for this two, in the left one, this seven will be there.

[00:05:40]But yeah, we know that for this, the condition will be satisfied from the the neighbor.

[00:05:46]So, if you just put them in the sorted order like this, always we are uh we are going to get our solution.

[00:05:55]Because, yeah, as we saw here that for each person, its left value, like for this five, that four is less.

[00:06:05]For this four, on its uh right, this two is less uh two is smaller.

[00:06:10]So, the solution will will always exist.

[00:06:14]So, yeah, that was it in the question, like and so, this our observation one was a sufficient condition for getting the solution.

[00:06:25]So, yeah, only this is our logic.

[00:06:28]So, we have to see that the frequency of the minimum element and if this is uh if the minimum value has frequency is equal to one, then answer is not possible.

[00:06:41]Else, the answer is possible.

[00:06:43]Else, answer is possible.

[00:06:45]So, that's it.

[00:06:49]So, for this, what logic I used is I just sorted all the elements and check if these two values are equal, right?

[00:06:57]If these two are equal, then I know that this minimum value has frequency greater than one.

[00:07:02]And if the these two values are not equal, which means that this minimum value is alone, right? If the array is something like this, let's say it is two and four, so, these two are not equal, then this minimum value has frequency equal to one, that's it.

[00:07:19]Let's see the code and uh yeah, this was a pretty easy uh question.

[00:07:25]So, we took the number of test case.

[00:07:29]This is the input of n. Then, we take the input of the array.

[00:07:34]Then, I sorted the array and we check if the smallest value and the second smallest value, which is a r of one, If they both are equal, then the answer is possible.

[00:07:46]So, we print yes, else we print no.

[00:07:50]So, that was it in the in this question.

[00:07:54]So, let's move to the second question of our discussion, which way binary smile.

[00:08:00]So, in this question, uh we are given two binary strings A and B.

[00:08:05]The binary strings are the strings which have only two values, either zero or one.

[00:08:11]So, each element of the string is either zero or either one.

[00:08:15]And the length is N.

[00:08:17]So, in one operation, Chef can choose any substring A of A that contains at most one frequency of one.

[00:08:28]And then we just reverse it.

[00:08:31]And we have to determine the minimum number of operation required to convert A into B.

[00:08:36]And if this is impossible, we have to output minus one.

[00:08:41]Okay.

[00:08:42]And yeah, substring is a continuous characters within A, so we will discuss this.

[00:08:49]The constraints are so, the number of test cases are till 25.

[00:08:54]And also the length of the string is till 25.

[00:08:59]So, we have to think something in O of N or O of N log N.

[00:09:03]So, yeah, let's discuss this. Uh So, name of the question is binary string.

[00:09:16]I I I I I I Binary smile, sorry. Name binary smile.

[00:09:27]So, let's first analyze that when the solution is not possible.

[00:09:36]Okay.

[00:09:38]Okay, when the uh when we have to print is a minus one.

[00:09:42]And even before that, let's analyze about the operation we can do, right?

[00:09:46]So, let's assume that we have some string.

[00:09:50]So, let's say our STR1, which is like this.

[00:09:57]Now, what operation we can do? So, like we can take some sub any substring which have at most one one at least sorry, at most one occurrence of the one, okay? So, I mean, we can take the substring like this.

[00:10:15]Uh you can see that in this substring, there is only one occurrence of one.

[00:10:20]Or you can take the substring like this.

[00:10:24]In this substring, there is zero occurrence of one. But you cannot take the substring which is like this because for this, there are two ones.

[00:10:34]Yeah, and you take the substring and just reverse it.

[00:10:38]So, let's take let's say we take the substring which is this one.

[00:10:44]So, then this substring will be reversed.

[00:10:47]So, after this operation, the our STR1 will be 100 one then zero zero one zero and one.

[00:10:57]So, this is reversed mean this value is now this one, this value is this, right?

[00:11:02]This substring is reversed.

[00:11:05]Okay, so now you can see that the only change is like the one which was at this position is now at this position.

[00:11:13]So, now you have to think that is why this operation can you just transport the one to anywhere in the string or is there any constraint on traversing right like Okay, so one thing is clear, right? The only thing that changes is the position of one, right? Because the the one was here, the one is now here.

[00:11:42]Okay, so we have to analyze this operation.

[00:11:49]So, let's say Okay, so now let's just take uh see something.

[00:11:56]Let's say this is our one.

[00:11:58]You want this one to be here.

[00:12:00]You want this one to be here. Can you do that?

[00:12:03]Uh the answer is yes, you can do that.

[00:12:05]So, you you will just take this substring and then this thing will be reversed.

[00:12:09]So, zero will come here and one will come here. So, substring will be like this.

[00:12:15]And yes, so this one is now at this position.

[00:12:18]Now let's say you want this one at this position. Can you do that?

[00:12:29]Uh and the answer is yes, you can do that. So, what you will do is you will take this substring and then this one will come at this end.

[00:12:39]So, this is also correct.

[00:12:41]So, we can see that in one operation we can change the position of only one one and it can be anywhere, like uh like you can uh transport this one to this position or you can have this one at this position by taking this substring or you can move this one to this position or this position.

[00:13:05]Right?

[00:13:06]But, you can move only one occurrence of one, right? In one operation.

[00:13:10]So, this is our observation. Okay.

[00:13:13]So, now how uh we will uh get our logic. So, first thing we have to think uh is uh when the answer is not possible.

[00:13:25]So, yeah, the only case for that is uh when the number of ones are different. Okay. So, let's say in the substring A, uh the string A is like this and the string B is like this.

[00:13:38]Which is the test case.

[00:13:40]So, in this uh case, no matter what operation you do, these two can never be equal, right?

[00:13:48]Because this has two ones and two ones and this B has only one ones, right?

[00:13:58]So, this was our observation one.

[00:14:02]This is our observation one is which is if frequency of one is different, then the solution is not possible.

[00:14:20]Then solution is not possible.

[00:14:26]Or we can say solution not exist.

[00:14:29]Okay. But now let's assume that the frequency of ones are equal. Then how you are going to do that?

[00:14:39]So, let's say the strings are like this. So, string A is like uh this.

[00:14:50]And the string B is like this.

[00:15:00]Okay.

[00:15:02]So, now you know that for this one, you can move it here. You can move this one from anywhere from this position to this position, right?

[00:15:11]Also, the one thing is uh the ones cannot jump each other. So, you cannot move this one to this one. Because for this, you have to take uh this substring. But you cannot take this substring because there are more than one occurrence of one.

[00:15:27]So, you can just move So, yeah, the observation is that for this one, which is like the first one in the sub B string B, uh for this at at this position, this first one will come only.

[00:15:46]Uh for this This is the second one.

[00:15:49]So, at this position, only the second second occurrence of one will come here.

[00:15:56]Right? Because like for this one, this one cannot come here, or this one cannot come here.

[00:16:03]Because no one can jump this thing, right?

[00:16:06]So, that's why uh at this position, this one will come.

[00:16:11]Then for the second occurrence of one in the string B, the second occurrence of this uh string A will come.

[00:16:20]One uh in string A will come, right?

[00:16:23]So, yeah, you can just uh use this approach. So, what we'll do is uh we will traverse from left to right.

[00:16:32]Okay? We will find the first occurrence of one.

[00:16:37]So, the first occurrence of one is here, and for this it is here.

[00:16:42]So, both are not same, right? So, I mean, both are not matched. Okay?

[00:16:47]So, you have to move this one.

[00:16:50]So, you have to move this one to here, and this thing you can do in one operation only by taking this thing.

[00:16:57]So, you take this substring, and now the array is uh string is reversed, and we will get 100.

[00:17:05]And everything else is same. So, let's remove this thing, and we get uh 100.

[00:17:12]So, now you can see that these both are matched.

[00:17:16]Now, you will see the second occurrence of one in the string B.

[00:17:21]And this should be matched with a second occurrence of one in the string A, right?

[00:17:28]So, now this one have to come this at this position.

[00:17:32]This will be also done in a one operation. You take this string and you move it here.

[00:17:40]So, yeah.

[00:17:42]Then after one operation, it will be like this.

[00:17:45]Now, let's let's test.

[00:17:48]Assume that the string was like this, okay?

[00:17:50]So, we matched the first occurrence in one move. We matched the second occurrence in one move. Then we find the third occurrence of one, okay?

[00:18:00]So, this is our third occurrence of one in the string B.

[00:18:05]And this is our third occurrence of one in the string A. And you can see that both are at same position initially. So, there is no need to change them.

[00:18:15]So, yeah.

[00:18:16]You just move ahead and find another ones if there is any.

[00:18:21]So, that was it in the code. So, for this, we will use a two-pointer approach. What we will do is we will have a pointer uh at the starting of the string A. And we will have a Let's call this P1.

[00:18:35]And we will have a pointer, let's call this P2, at the starting of B.

[00:18:40]So, they will move uh so, they will point at some occurrence of one.

[00:18:46]If they both are at same position, then we don't have to do any operation.

[00:18:52]Okay, let's write it.

[00:18:55]Uh so, what we will do is let's assume that this is our string.

[00:19:03]Okay?

[00:19:04]So, this There will be our pointer P1 and initially and there will be our pointer P2.

[00:19:12]So, this P1 and P2 will move until we get any occurrence of one. Okay, so the P1 will point here.

[00:19:20]And the P2 will iterate until it points to any one. Okay, so like this is zero, so P2 will move ahead.

[00:19:29]Then this is zero, so P2 will So, P2 will also point here.

[00:19:33]So, P2 will point here.

[00:19:36]Now, we will check if the both ones are at same position.

[00:19:40]So, yeah, the P1 is two, so this is index two.

[00:19:44]And for the index of P2 is also two.

[00:19:47]Both are same.

[00:19:49]So, we will not do answer plus plus. So, let's say initially answer is equal to zero.

[00:19:53]There is no need to do the operation.

[00:19:56]That's okay.

[00:19:57]So, then we will move again.

[00:19:59]So, now our P2 will come here. Sorry, P1 will move here. It is zero, so it will move again. And P1 will point at this position now.

[00:20:09]And then P2 will point at this position.

[00:20:13]Okay. Now, we will check if they both are equal, but they both are not same.

[00:20:19]So, we will do answer plus plus. So, my answer will be one now.

[00:20:25]And then P2 will come here, but yeah, the while loop will end.

[00:20:30]So, that's it in our logic.

[00:20:33]So, let's see the code.

[00:20:36]And just note the point that instead of like moving from this and moving the pointer this way, you can also do like have the pointer here.

[00:20:49]Find the first occurrence of ones and then go this way.

[00:20:54]So, that was That is the approach I used. So, let's see the code.

[00:20:59]So, yeah, this is test case and input.

[00:21:02]Uh I found that P1 is the number of ones in the string one.

[00:21:07]And this P2 is the number of ones in the string two.

[00:21:11]So, I iterate in the string one and count the number of ones and this is count the number of twos.

[00:21:18]If they both are not same, then I know that the answer is not possible, so I print minus one and I continue.

[00:21:25]So, yeah, the next test case will run.

[00:21:28]This code will not run if I write the continue.

[00:21:31]Then, initially for my two pointers, the pointers are pointing at the end of the string, which is n minus one index, right?

[00:21:41]And the answer is equal to zero.

[00:21:43]Until P1 is greater than zero or P2 is greater than zero, I have my this loop.

[00:21:52]So, they what this loop is, so like until my P1 is in the range, okay? P1 is greater than equal to zero.

[00:22:01]And if the uh if P1 is pointing at the zero currently, I will move left.

[00:22:08]Uh and I will stop and I will stop at the position where the element is one.

[00:22:14]So, until the position is zero, I will move to left.

[00:22:17]Right? Uh I do the same in the string two.

[00:22:21]Until P2 is greater than equal to zero, which means I am not out of the string.

[00:22:26]If the current element is zero, I move to the left, okay?

[00:22:30]So, after this, I know that my P P1 and P2 both are pointing to the index where element is equal to one.

[00:22:38]Right?

[00:22:39]And so, if anyone is out of the range, I just break.

[00:22:43]So, now if P1 and P2 are not equal, index are not equal, I know that I have to do operation.

[00:22:50]Uh I have to do exactly one operation.

[00:22:52]So, I do answer plus plus and P1 and P2 minus minus after that.

[00:22:56]So, this run will uh this loop will run again.

[00:22:59]And after that, I uh this is my answer, so I print the answer.

[00:23:04]So, that's it in this code in this question.

[00:23:07]Uh if you have any doubt, you can uh comment it.

[00:23:12]So, now we will move to the third question.

[00:23:17]Which is partition.

[00:23:19]So, in this question uh we are given an array of an integer and a partition of A is a sequence of X continuous sub-array.

[00:23:30]Such that the concatenation equals A.

[00:23:34]Okay, so this partition is nothing. We are just dividing our array A into some uh more than one array.

[00:23:45]Okay? And for each sub-array DI So see here, we have this array A. Uh we break it into let's say X parts.

[00:23:56]So, this B1 is the first part. This B2 is the second part.

[00:24:00]And for each part this G of BI denotes the maximum frequency of any element in BI.

[00:24:08]So, for this B1 uh the G of BI will be the maximum frequency of any element in this B1 array.

[00:24:15]This G of B2 will maximum frequency in this B2 array, and that's it.

[00:24:20]And the score of the partition is nothing but the summation of this G of BI for all of the this sub-array.

[00:24:31]And we have to find the number of distinct values of F over all partitions of A.

[00:24:37]And the number of test case and the N are till 25.

[00:24:42]So, again, we have to think something in O of N or O of N log N.

[00:24:48]So, let's analyze this question.

[00:24:52]The name is uh partition.

[00:25:04]>> Okay, so remember that whenever you have to count the distinct count the distinct possible values that's a distinct value.

[00:25:16]You have to first of all think that what is the minimum value you can make or let's say here minimum score you can make.

[00:25:26]And also you have to find what is the maximum score you can make.

[00:25:31]Right?

[00:25:33]You have to find this and like after you find this there can be like many possible ways. I mean that that can be possible that uh the whole score is continuous. I mean right? Let's say the score values can be like 2 3 4 5 6 7 8 something like this.

[00:25:55]So like if you find this minimum value you if you find this maximum value of score possible then you know that everything in middle is possible.

[00:26:04]So the answer will be 8 minus 2 plus 1 here.

[00:26:08]Or another case can be possible is that uh the max minus min value is uh so small so you can just brute force there.

[00:26:16]Or maybe you can find some pattern or formula there. So yeah this is a important thing that you find the minimum score and the maximum score possible.

[00:26:30]Okay.

[00:26:31]So let's first analyze like what is the partition mean.

[00:26:36]So let's say initially the array is like this A1 A2 A3 A4 and A5.

[00:26:44]So I mean you can just partition in how much continuous sub arrays as you want. So So uh you can partition this A1 [clears throat] A2, then this A3, and this A4 A5 alone.

[00:26:59]So this will be my one array B1.

[00:27:03]This will be my another array B2, and this will be my another array B3.

[00:27:07]And then for this, the score will be G of B1 plus G of B2 plus G of B3.

[00:27:18]Okay, so let's analyze this by some test case.

[00:27:23]So let's say the array is like this, 1 3 2 2 1 1.

[00:27:32]So this is our uh array.

[00:27:37]Okay, so now maybe you can partition this like uh this thing.

[00:27:48]And for this Okay, so for here the maximum frequency is uh one.

[00:27:56]For this, the maximum frequency of any element is two, right? Because there are two occurrence of this value two.

[00:28:04]For this, the maximum frequency is just one.

[00:28:07]Uh sorry.

[00:28:11]This is also one, and this is also one.

[00:28:14]So the score for this partition is uh five.

[00:28:20]Right?

[00:28:22]So now think that how we will get the maximum score and the minimum score.

[00:28:27]So let's say we want the maximum score.

[00:28:35]So for that like we want that each element contributes like I mean what I'm saying is that like this one is contributing one value, right? This one also is contributing one value.

[00:28:48]Here like there are two values, but the score is only one.

[00:28:53]So, we want each value to contribute.

[00:28:56]So, let's say you can partition it like this.

[00:29:00]Let's say 1 3 Uh it was 2 2 1 1 2 2 1 1. Okay. So, yeah, the simple observation is you can partition it like this.

[00:29:11]And now see, for each thing they are contributing one.

[00:29:17]Right? Because like for this array the score is a G of this array is one, right? Because maximum frequency is one.

[00:29:25]This also one, for this also one.

[00:29:27]For this element is also one. This for also this one and this one. So, yeah, the score will be just the size of the array, size of the array.

[00:29:39]Yeah, that's one observation we found.

[00:29:41]Okay, but what about the minimum array?

[00:29:44]Uh sorry, minimum score possible.

[00:29:49]So, yeah, for that you can just do the reverse of what we did here, right? For here, we just partition each element.

[00:29:57]But here you can think that I I I just don't partition any element.

[00:30:01]So it can be like 1 3 2 2 1 1.

[00:30:06]And you don't even partition. So, this is my one partition only.

[00:30:12]And for this the score will be three.

[00:30:15]Because the maximum frequency is three, which is of the value one, right?

[00:30:22]So, yeah, this is three.

[00:30:25]So, from this you can also get the observation that the minimum score you can get Let me change the color.

[00:30:35]The minimum score that you can get is just the maximum frequency of any element, right? The maximum frequency of any element.

[00:30:52]And that's it.

[00:30:54]So now we have found the minimum score and the maximum score.

[00:30:59]Right? So like for this the like for this array the minimum score is three.

[00:31:05]And the maximum score is uh maximum score is six, which is the size of this array.

[00:31:12]Okay. Now what?

[00:31:16]And so you can think of uh like finding that like you have the score three.

[00:31:22]Now can you make the score equal to four? Can you make the score equal to five?

[00:31:27]Like can you make the score like which is between this three and this six every score possible?

[00:31:34]And yeah, in this case you will find that it is true. So I mean like if you can make the score equal to three and if you can make the score equal to five so every value in between you can also make it. So that's it.

[00:31:51]Okay, so and you can prove this by just like taking the several test case and just by into intuition.

[00:32:00]I did that I did by that way only like in the contest.

[00:32:06]And also this method is really important because I remember in the ICPC Codefest Prelims the fifth question was based on this method. Where you have to find the minimum and the maximum.

[00:32:20]And all of the score which is in between them is also possible.

[00:32:27]So yeah, that's this is it. Okay.

[00:32:29]Now let's prove this thing.

[00:32:32]So for proving let's take uh test case.

[00:32:36]So let's say my array is like uh this.

[00:32:42]Okay.

[00:32:43]So, for this we count the maximum value.

[00:32:46]So, the maximum value is uh what the size of the array, which is seven here.

[00:32:52]And the minimum score is uh the maximum frequency, which is two here.

[00:32:59]Okay, so what you can think is let's say we start by the minimum score.

[00:33:08]Uh let let's start by the maximum score, okay. So, let's say like initially the score is seven.

[00:33:16]So, so let's write here the score.

[00:33:21]So, initially the score is seven.

[00:33:23]Right?

[00:33:24]Now, you have to make the score equal is equal to six.

[00:33:28]So, what you can see here is that these are the previous two values, you just combine them.

[00:33:33]And now like the score of this array is one only.

[00:33:37]So, the total score will be six now.

[00:33:41]Okay, now you have to make it five.

[00:33:43]So, you can just again uh make this sub-array bigger.

[00:33:49]So, now again the score is one.

[00:33:52]So, 1 1 1 1, so the score is now five.

[00:33:57]Okay, now you want to make it four.

[00:34:01]So, yeah, you know the thing, we extend this last sub-array.

[00:34:06]So, this one is removed and uh the score is one now. So, the summation is four. So, my score is four now.

[00:34:15]Okay, what if we want to make uh the score equal to three?

[00:34:21]Again, you will just extend this thing.

[00:34:24]So, we extend this thing.

[00:34:26]So, now the score is one for this.

[00:34:30]And the score is three now, right?

[00:34:33]Now, let's say you want to make the sum is equal to two.

[00:34:36]Again, you extend this thing.

[00:34:40]And now comes the tricky part, okay?

[00:34:43]Sorry.

[00:34:44]Okay, we want to make it as two, and now comes the tricky part because for this the score is two now, and the score is one, so total score is still three now.

[00:34:53]But what we can do is we can keep extending it, right? So, now the score is two.

[00:35:00]So, yeah, we you can see that uh if you can you just keep extending this sub array, okay? You keep extending this sub array.

[00:35:10]The score is reducing uh and the score can reduce by at most one only, right?

[00:35:17]So, yeah, by this proof uh you can say that the score is reducing by at most one for each step you uh add. So, I mean if initially the sub array was one, and now you make it one.

[00:35:30]So, the score can be changed by at most one only.

[00:35:34]You make it this, and now the score is changed by at most one only.

[00:35:38]So, yeah, this is continuous, so you can say that you can find any value. Uh you can make any score possible.

[00:35:45]So, that was it. Uh so, yeah, the logic is simple.

[00:35:51]What was the logic?

[00:35:53]We found that the maximum answer is uh size of array.

[00:35:59]And the minimum answer is the max frequency.

[00:36:04]So, and the answer will be max minus min plus one.

[00:36:11]Right? Because like you can see if the maximum is seven and minimum is two.

[00:36:17]Uh then there are seven minus two plus one, six values possible, right?

[00:36:22]So, yeah, that's what you have to do.

[00:36:26]So, let's see the code.

[00:36:30]So, this is our input and we take the input of the array.

[00:36:37]Now, we have to find the maximum frequency of any element, right? So, for that I made a map.

[00:36:46]So, map of something will just store give me the frequency of that element, okay?

[00:36:53]And also this is the max fr which will give me the maximum frequency.

[00:36:57]I iterate on each element. I do the map of array plus plus and I do the max frequency is maximum of max frequency or mp of arr of i. So, after this the max frequency will store me the maximum frequency of any element.

[00:37:15]And my answer is the maximum answer possible which is the size and the size is n minus the minimum answer possible. So, minimum is max of fr plus one and I just print this thing.

[00:37:31]So, I hope that you understood this thing.

[00:37:37]Okay, so let's move to the fourth question of our discussion and this was the best question among like this uh four question because like the logic is really amazing. And even if you don't know any hard concepts like the Mobius inversion of the in the number theory, you can easily solve this question.

[00:38:06]Okay.

[00:38:07]So, in this question we are given that we have a number z and we have to count the number of pairs x y such that that x is less than or equal to Z.

[00:38:23]This Y is less than or equal to Z and uh the LCM of these two values must be greater than Z.

[00:38:30]And this is strictly greater greater than Z, okay?

[00:38:34]And yeah, that's it.

[00:38:36]And the range of this Z can be till 10^6.

[00:38:40]But also another constraint is that the sum of Z uh don't exceed exceed 10^6.

[00:38:47]So yeah, you can see that uh uh you have to solve this in O of Z or O of Z log Z or something like this.

[00:38:59]So Okay, just give me a minute uh for Okay, so uh let's discuss this question.

[00:40:01]So the name of the question is uh counting LCM.

[00:40:10]Uh just a moment.

[00:40:26]>> Okay, so like the first thing in this was like if you try to find the number of LCM which are greater than that.

[00:40:36]So you will find that this LCM can be any value, okay, so let's discuss here.

[00:40:44]So the name is the counting LCM.

[00:40:52]And yeah, we have given some value Z.

[00:41:01]And uh we have to find the number of pairs, number of pairs XY such that this X and Y both are less than equal to Z.

[00:41:14]And their LCM is uh greater than Z, okay.

[00:41:23]So >> [clears throat] >> the first thing I analyzed here is uh that this value of LCM of X and Y Let me write more clearly.

[00:41:39]This LCM value of X and Y So this value can be very bigger, like I mean, let's say if they are both some prime number near Z, so like they can be till Z square.

[00:41:53]So which means they can be till 100 12, which is a very big value.

[00:41:58]So it's better So it is better to Okay, this is our observation one.

[00:42:10]It's better to count the count the number of pairs which have the LCM less than equal to Z.

[00:42:22]Right?

[00:42:23]And then we will just do that answer is equal to possible pairs.

[00:42:29]Like all possible pairs minus this bad pairs, right?

[00:42:38]Uh these are the bad pairs which have the LCM less than equal to Z. Why?

[00:42:43]Because now you can see that uh this thing is kind of easy because there are now only Z possible values for LCM, right? I mean the LCM can be from till one to Z.

[00:42:55]So there are less options for LCM.

[00:42:57]Okay, so now if you know this and like if you have solved the CS CS problem set this is a kind of a fundamental question.

[00:43:07]Okay, so now what we will do?

[00:43:10]So we know that we have to solve this in O of Z or some complexity like this.

[00:43:18]So now we will uh try to think that uh can can we find something like uh Okay, so there are so in the question uh while solving in the contest I tried many approaches, many different approaches. Like what I did was let's say I took some number A and some number B, okay?

[00:43:41]Uh let's say this number is like G times A and this number is G times uh sorry, G time X and this is G times Y.

[00:43:49]And then I thought uh that uh like the LCM is equal to the multiplication divided by GCD.

[00:43:57]So it let's say it is G time X into G time Y and the GCD is equal to G.

[00:44:03]So this is G of XY.

[00:44:05]And I I just thought like g of xy should be less than equal to z. Then I tried to uh fix some pairs like I tried to fix the GCD.

[00:44:17]Let's say GCD is equal to one. So, how many pairs there are? So, then xy should be like this and uh this all uh doesn't work.

[00:44:27]So, I just forgot this thing and now let's try to fix something another thing, okay?

[00:44:34]So, because like this is we have to solve this in O of z. You can like try something like you try to fix some value and then try to find the number of pairs fixing that value.

[00:44:46]Then you just iterate and you get the answer, right? So, let's fix LCM.

[00:44:52]So, let's say you have to find the number of pairs such that the LCM is equal to what?

[00:45:03]LCM of two numbers is equal to some particular value x, okay? And this x is given to you.

[00:45:14]LCM.

[00:45:16]Okay, you want to find this. The number of pairs such that LCM of these two numbers is x. And of course, the a and b both should be less than equal to z.

[00:45:29]Okay, so for this thing and if you let's say if you don't know any algorithm and if you have not solved any question, like how you will approach this?

[00:45:38]So, let's find uh some observation or something, okay?

[00:45:42]So, first of all, from this uh you can uh say that this both a and b will be a divisor of x. Will be a divisor of x.

[00:46:01]This is uh for sure true.

[00:46:05]Uh Okay, and why like let's say Uh why because uh you can take some example. So, let's say uh LCM of uh 4 and 3 is uh 12.

[00:46:26]And you can see that 3 is a divisor of 12 and 4 is also a divisor of 12.

[00:46:31]Or let's say 4 and 8, the LCM is uh 8.

[00:46:35]And both are divisor of 8, you can see.

[00:46:38]So, this is our first observation.

[00:46:41]And you can see that the number of divisor are not mm that much a big value, right? So, even for a number like 109, the number of divisor are only till 400.

[00:46:55]So, you can think in some that way.

[00:46:58]Okay. So, now you know And now comes the main part, okay?

[00:47:05]So, now you know, okay, let's say the uh value is 12.

[00:47:10]Right?

[00:47:12]So, now you know that if uh if there are two values AB and their LCM is equal to 12, so this A and B must be from one of these values, right? 1 or 2 or uh they should be 3 or 4 or 6 or 12, right?

[00:47:33]This A and B must be one of these values.

[00:47:38]A and B must be one of these values, okay?

[00:47:43]Uh but you can see that like not every value will give you LCM is equal to 12, right?

[00:47:52]So, like what? Uh like let's say you you take uh this two in pair, okay? You take A is equal to two and B is equal to six.

[00:48:02]So then LCM of two and six, yeah, you get 12, which is nice.

[00:48:08]But let's say you take LCM of uh two and three.

[00:48:13]If you take you you get uh only six.

[00:48:17]Right? Which is not equal to 12.

[00:48:22]So now, how we are going to solve this thing?

[00:48:27]Okay, so uh let's take uh one more example properly.

[00:48:31]Like let's say our let's say we want our LCM to be 10.

[00:48:35]So for that we know that our value A and B must be one of the one, two, five, and 10, right?

[00:48:41]This must be true.

[00:48:43]Okay, so now let's try to make every pair and uh see what's their LCM is.

[00:48:51]So for this one, two, let's write all the pair, one, five, one, 10, two, one, uh two, two, okay, two, there is one, one also.

[00:49:01]Uh two, five, and uh two, 10.

[00:49:06]Then there will be five, one, this is one pair, five, two, five, five, and five, 10.

[00:49:22]And then the 10, one, 10 and two, 10 and five, 10 and 10. Okay, so now, like for all pairs, let's count the LCM. So for this LCM is one.

[00:49:36]For this LCM is two, LCM is five, LCM is 10, LCM is two, LCM is two, 10, 10, five, 10, five, 10, 10, 10, 10.

[00:49:53]And so you can see now let's take try to take some observation.

[00:50:00]Uh so you can see here that either the LCM is equal to 10 or the LCM is some divisor of 10, right?

[00:50:09]So the LCMs are some divisor of 10, right? You can see that 2, 1, 5, everything is a divisor of this.

[00:50:18]So now to find to find the number of pairs uh such that the LCM is equal to 10, okay.

[00:50:33]You have to do the You have to see all possible pairs.

[00:50:37]So how many pairs are possible here? So there are 4 cross 4 16 different pairs, right? Because because like for LCM to be 10, only one of these values should possible.

[00:50:52]So for A there are four possible values, 1 2 5 or 10. And for B also there are four possible values, so which are 16.

[00:51:03]Let's write down.

[00:51:07]So which is like total pairs minus you have to uh cancel the pair which have GCD equal to some divisor of it, equal to some divisor.

[00:51:31]Okay, so now point is how we are going to find this thing. Right? Because let's say we want the GCD is equal to sorry, LCM is equal to 10.

[00:51:42]I'm sorry if I if I was saying GCD if LCM. Yeah.

[00:51:51]So now like we will see first of all all possible pairs which are 16. Then I will cancel the pairs which have the LCM is equal to one.

[00:52:00]Then also minus the pair which has LCM is equal to two.

[00:52:04]And yeah, then I will get the exact pair which have the LCM is equal to 10, right?

[00:52:11]Okay, but now the yeah, the point is how you are going to find it.

[00:52:16]And here comes the main part.

[00:52:19]That we will uh find iteratively like for all of it.

[00:52:25]So we will run iteratively for I from one to 10. Uh sorry, let's say from I from one to let's say X.

[00:52:35]We will do uh the our work iteratively.

[00:52:37]So What does it mean? So let's say I make my array This is my answer array.

[00:52:50]1 2 3 4 5 6 7 right?

[00:52:55]So like uh so the each value will give me so the value here will give me the number of pairs which have the LCM is equal to three.

[00:53:03]So I will work iteratively. What I will do?

[00:53:07]So I will count the number of pairs which have LCM is equal to one. Okay.

[00:53:11]Uh let's I count this.

[00:53:13]Then I will come at this two.

[00:53:15]Right?

[00:53:16]So for this two, the divisors are one or two, right?

[00:53:21]So all of the possible pairs are like 1 1 1 2 2 1 and 2 2.

[00:53:28]This has LCM one. All of the other has LCM is equal to two.

[00:53:32]So I will do the total pairs.

[00:53:35]Okay, let me write here.

[00:53:37]So for this answer is one here.

[00:53:39]Because there is only one pair which is this 1 1 which have the LCM is equal to one.

[00:53:45]Now, when I come at this two, I have already calculated the number of pair that have the LCM is equal to one.

[00:53:53]So, I just have to remove that thing.

[00:53:54]That's it.

[00:53:56]So, the total possible pairs are two cross two four, minus this value, minus this value.

[00:54:06]So, here the answer will be three.

[00:54:09]Now, I come at this, let's say this three.

[00:54:13]So, for this three, uh its divisors are one and three.

[00:54:18]Right?

[00:54:20]So, total total pairs are four.

[00:54:26]And you will go to its divisor, all of its divisor, and minus that value.

[00:54:32]So, here the answer will be three.

[00:54:35]Here comes the nice part, okay?

[00:54:37]Now, you come at this four.

[00:54:41]Uh you come at the four.

[00:54:43]So, the you want the LCM is equal to four.

[00:54:47]So, its divisors are one, two, and four.

[00:54:53]Right?

[00:54:54]So, total possible pairs can be what? So, like for A, any value from this three can possible.

[00:55:04]So, it will be three, and for B, there are three values possible, so three cross three nine.

[00:55:09]Then, you will go at each divisor. You will go at one. You will go at two.

[00:55:13]And ask that how many pairs are there such that LCM is equal to one.

[00:55:18]You will go at this divisor. You will count that how many uh pairs are there such that the LCM is equal to two.

[00:55:26]And you minus all of that stuff. So, you minus one, and you do minus three.

[00:55:31]Right? And we get the answer is equal to five.

[00:55:36]Yeah, that's it.

[00:55:37]So, this is like a iterative version of Mobius and like we have derived this thing, okay?

[00:55:46]So, that's it.

[00:55:47]Uh So, uh This is our logic.

[00:55:55]What we will do for like we will first uh find the what? Find the divisor for each number.

[00:56:06]Let's say find the list of divisors for each number.

[00:56:13]Then we will work iteratively, okay?

[00:56:15]We will work like I from 1 to Z because Z is the maximum uh LCM that we want, right? Like and we will just count total pairs.

[00:56:37]And then we will run a loop and we will like cancel the pairs which have less LCM, right? Which have less LCM.

[00:56:49]Lesser LCM, that's it.

[00:56:51]And then the sum of all of these things are our answer.

[00:56:55]So, let's see the code and uh you will understand this thing.

[00:57:00]Okay, so let's see the solution.

[00:57:04]Like I hope you understand like what I was saying here. I mean, how we uh run out iteratively and find the answer and uh let's say uh in case you have some doubt, you can comment me or you can see the CSES uh question. Like exactly I don't know which one it I will write that in comment.

[00:57:29]Okay, so let's see the code.

[00:57:32]So, first of all, I am calculating the divisors for each uh uh each number, okay? So, the maximum value is 26 only.

[00:57:43]Right?

[00:57:44]And now, what I do is uh I'm just counting the divisors. So, in case you don't know what I'm doing here is uh Look at this comment.

[00:57:55]What I'm doing here is like I know for this one. So, one is divisor of 1 cross 1, then 1 cross 2, or sorry.

[00:58:04]1 cross uh 1 into 2. Then, it is divisor of 1 into 3, it is divisor of 1 into 4, right?

[00:58:11]If If we talk about four, the four is the divisor of 4 cross 1, 4 cross 2, 4 cross 3, 4 cross 4, and so on.

[00:58:21]So, that's what uh we do.

[00:58:26]So, this is the vector of uh vector of div.

[00:58:30]So, like div of I will give me the list of all of the divisor. I run from uh 1 to till the maximum.

[00:58:38]Uh the current value is I.

[00:58:40]So, I know that this current is the divisor of current, and I keep adding the cur.

[00:58:45]And I in this value J, in this value J, I push back the cur, which means that current is the divisor of this value J. That's it.

[00:58:56]Uh then, I run the loop. Uh I take the N.

[00:59:01]Then, this is bad, so I'm counting the number of bad pairs, which means that they have LCM less than equal to Z.

[00:59:08]Uh sorry, because I have taken the Z is equal to N here.

[00:59:13]Okay, so this is my vector.

[00:59:16]So, this is just the array we are talking here, like it will So, area of I will give me the number of pairs which have LCM is equal to I.

[00:59:27]So, I run from one till N.

[00:59:31]So, the number of total possible pairs are like the number of divisor into number of divisor, okay?

[00:59:37]So, like uh in the pair like for A, there are this much option and for B, there are this much option.

[00:59:46]Then, I go into the uh I I trade on its divisor and minus if their value, okay? So, let just see here.

[00:59:59]Uh let's say the list of the divisor is something like this. So, let's say for the five, the divisor list will be like this.

[01:00:11]Uh sorry.

[01:00:12]For uh let's say for 10.

[01:00:16]So, for 10, our divisor list will be one, two, five, and 10.

[01:00:22]So, we have to uh run the loop till here only, okay? We don't have to uh see the 10 here, right?

[01:00:31]We just have to go till here. So, I iterate on this thing and I just do the I just cancel the number of pairs which have LCM is equal to one, which is answer of one. Then, I do uh minus of answer of two and that's it.

[01:00:48]So, you see here, I'm iterating on this divisors list.

[01:00:54]The divis divisor is like div of I {comma} J and in that total pair, in the total pair, I'm subtracting the answer of divisors.

[01:01:05]That's it.

[01:01:07]So, now the number of pairs which have LCM is equal to I is this pair's term.

[01:01:14]So, answer of I is equal to pair and also the pair like this is the initial thing. This I'm adding this into pair.

[01:01:22]So, my total answer is going to be the number of possible bad which are the Z cross Z or you can say N cross N minus this bad bad and I'm just printing the answer here. So that's it in the code.

[01:01:39]And yeah, the time complexity is going to be over first of all here.

[01:01:47]186 log 186 and for here it is going to be N log N because I'm traversing over N and the number of divisor are kind of over log N.

[01:02:03]Oh yeah, that's it.

[01:02:05]So that was it in this code and in case you have any doubt, you can comment me comment in this video and uh So yeah, that was it till now.

[01:02:19]So let's uh over this discussion.