Transcript for:
Contest Video Solutions by Smart Interviews

hello guys welcome Contest video solutions by smart interviews today we are going to discuss the solutions of starters 142 so yeah let's get started in a football match a penalty shootout is used to determine the winner if the score is tied after regulation and extra team each team takes turns attempting five penalty kcks team a has scored X goals in three turns and Team B has scored y goals in four turn so there are two teams A and B each team will have five penal tiets out of which a has used three turns and scored X goals and B has used four turns and scored y goals next determine if it's possible for the penalty sh out to end with equal score after both teams have taken all five of them and so a can take two more kicks and B can take one more kick we have to figure out if let's say Z1 and Z2 are the final scores we have to figure out if Z1 equals to Z2 or not if there's a possibility for that or not input format the first line of input contains single integer T denoting the number of test cases each test case contains two space separated integers X and Y where X is number of goals scored by team A in their three terms and Y is number of goals scored by team B in the four terms next output format for each fish case we simply have to print yes if Z1 can be equal to Z2 and no if there's no possibility of that and it's clearly given the output must be separated by a new line and the standard thing yes can be printed in any way and no can also be printed in any way that is each alphabet can be in any case lower case or upper case next there are T Test cases X will be less than or equal to three of course because there are only three turns used by team A and Y will be less than or equals to four because Team B has only used four turns next sample is given so first Inver is one and two team a is one and Team B is two that's course now there are two more chances for team a and just one more chance for Team B teamate if it is scoring in the second chance so the score will become two and if it's scoring in third chance as I mean in the remaining two chances this score will be Become Three so already three chances were used and score was only one in the fourth chance if the score the score will become two and in the fifth chance if the score the score would become three coming to Team B two is the current score after three after four T now if they're scoring the last go the score would become perfect three so we simply have to check if there is a possibility of one number from here to be equal to one number from here if you say there are two such cases so the output is yes coming to the next samp player team a has SC three gos and team we has for Zer gos so two more chances and just one more chance this four possibilities are four and five and here it could go to one do you see any number from from here to be equal to any number from here no so there's no possibility of them being equal so it's a no they ask us one and one they're already T so if the next two chances are not scoring anything it would be a drw so that's a possibility draw I hope the amp is clear now coming to the approach team a has for x goals and Team B has scored y goals so in their fourth turn if they are scoring a goal team a score would become X+ one and in the fifth turn as well if they are scoring a goal the score would become x+2 correct similarly for Team B they only have one more chance so if this score the score will become y this one for the possibility of draw any number from here should be any one number from here that is X should be equal to y or X should be equal to y + 1 so we got two cases if x = to y or X = to y + 1 in both these cases there is possibility of draw similarly X+1 can be equals to y or x + 1 can be equals to y + 1 so that brings us to the x + 1 = y or x + 1 = y + 1 so if you're taking x + 1 = y + 1 this is nothing but X = Y which is already considered so I'll skip that case next x + 2 = y or x + 2 = y + 1 that x + 2 = y and x + 2 = to y + 1 if we subtract one on both sides we get x + 1 = to Y which is already taken so checking this four cases would be sufficient so if X and Y are the given inputs if one of these cases is true then we can simply return return Yes or print yes and else we will be printing no shall we code it okay let's put it first let us take the input in CT and uh loop T times each time to space separated integers are given we read them as well and if there is a function which will say if the result can be draw or not simply call it and output should be separated by a new line so what should result of function return directly yes or no so return type would be stram now if one of those four cases is true we return Yes what are the four cases if x = to y or X = to y + 1 or x + 1 = 2 Y and the last Cas is x + 2 = to Y if one of these cases is true we simply return Yes else we simply no that's it shall we test it the Ed output is yes no yes perfect let us submit and check that's it let us Gove to the next question second question Chef loves P Chef loves h l byf so the chef has a unique way of cutting round pces he starts by cutting the pizza in half then then in eights and so on always cutting through the center below is an example of cuts made by Chef in sequential order so one cut is dividing the P into two halves then the next what four quarters then one more cut we got six then one more CIT we got eight sectors then one more cut how many C we get here it will be 10 then so from this what do you understand for each C the number of slices is increasing by two what else is given Chef wants to cut P to X slices where X is always even so here it's given slices so in this case the cut will be made like this then one slice will be added but if the whole cut is made then two slices will be added but it's clearly said X slices where X is always even so a small in the question here this whole thing is not considered as one cut but two cuts that's only thing different next your task is to determine the number of pieces that will be smaller than the rest so input format the first line will contain three number of test cases and each test case will simply contain X that is the number of slices T fs and X will be an even integer output the number of slices which are smaller than the other T will be 10 x will be 10 and X will be even as well so [Music] two if you are making one and then two CS how many slices are smaller than the other zero because all are equal then 14 so here it's clearly given 14 Cuts is displayed in picture 7 where is picture 7 over here so we get 1 2 3 4 5 6 7 8 9 10 11 and 12 slices which are smaller compared to the other slices which are bigger now how can we get the answer we know one will give us two slices so every time if I'm making one cut I get two slices and if I'm getting one more cut I get four slices that's one observation what's the other observation in which cases or when X is what value we will get equal size slices so first when I make one cut I got two slices how many Cuts should I make such that we get equal SES two more guts then we get equal slices I'm further cutting the slies how many Cuts should I make four more Cuts then after that we got eight slices and if I'm making one slice into two then we get two smaller slices but if I want to make them equal each of this must be cut in the same way so into two again if I'm moving further number of SES will be into two of this and then into two so what did you observe from this if the number of cuts made is a power of two then we get equal sizes and after that for each cut what will happen we will get smaller slices so so if x is given how can we get the answer we want the nearest power of 2 of X let us call that as y then for each cut made from y to X that is x - y Cuts we get a new s every time how many slices we get for each cut two new slices so can I simply say x - Y into 2 will be the number of slices which are smaller that's it right so what's the Mind ask in this finding this way if a number X is given let us take 9 we want the nearest power of 2 to 9 which is lesser than or equals to 9 it will be8 but how can I get this should I start iterating of course that will take a lot of time if iterate let us say you are given some random number and you have to start iterating so until you get the Power of Two keep on iterating which is not at all suggestable our complexity will be very higher if we do this so what else can we do perfect guys those who said we can simply get the last set bit from the given number you're right perfect those could it from this if we want the power of two which is lesser than or equals to the given number nearest one I'll simply make all the bits to zero except the MS the bit then that will give me the power of two so I hope the approach is clear let us the first line of input contains the number of test cases and for each test case an integer X is given and what are I supposed to do find the nearest power of two for X once we get this what we supposed to do we print the answer as x - Y into 2 separated by so I F fill this function it's done now how to get the nearest power of X Which is less than or equal to X simple if we get the number of bits in X we can simply return 2 power number of bits minus 1 how to get the number of bits let's count them and CSN Z so when X is greater than Z it will have some bits in it so how can we move bit by bit until the number become zero simply do right shift x asss x right shift one and I WR increase the count and what I supposed to is nothing but 2 power in this case the count of set bits we want so count as C and 2^ cus 1 should return so we simply return one LIF shift C minus one let us run it and check we got 02 and 68 928 and the expected output is also that as well let is submit and check perfect now let us move to the next question AR you are given an array a of size 10 your task is should determine the minimum number of elements that need to be removed from the array a such that bitwise or of the remaining elements is 2^ xus one so what's the information we got from this we are given an array of Siz and we are supposed to check the count of minimum elements to be removed such that the bitwise or of remaining elements will be 2^ xus one note that the bitwise or of an empty array is considered to be zero if no element is there the output will be considered as zero that means if there is no way to get 2^ xus 1 we can simply remove all the elements which will result in zero and we know 0 can be expressed as 2^ xus one so 2x = 2 0 when 1 isal 2 0 so X is equal to Z so if there are no elements then we can simply take zero elements and it's clearly given X can be greater than or equals to zero now moving to the next part of the question input format the first line of input contains T that is a number of test cases the next line contains n and then n number of integers that are integers of the array so first T and for each dist case n and the array elements are given then next the output format we simply have to print the minimum number of elements that need to be removed from the array constraints T up to 10 power 5 n is up to 10^ 5 and our elements can be n anything from 0 to 10 9 the sum of N overall test cases won't Exit 3 into 10 5 so the significance of this is T is = 10^ 5 n is = 10^ 5 and T into n is 10 part 10 but we know at most we can do 10 Power 8 iterations but here itself 10 PN so that is why it's clearly mentioned the overall test cases won't exceed 3 into 10 5 so which is less than 10 8 clear let us take the sample input on output two test cases are given the first test case is containing two integers which is six and the other integer is 16 six can be represented as perfect 0 0 1 0 16 can be represented as 1 0 0 0 0 so this is 2^ 0 this is 2^ 1 2 S 2 q and 2^ 4 6 is 2^ 4 and 6 is 4 + 2 so 2 s + 2 1 if we do all of these both what do we get 1 0 1 1 0 and if it just take six that is not 2 X - 1 if it take 16 even that is not 2^ x - one and how I'm able to directly say if it's 2^ X - 1 if this can be expressed as 2 x - one or not and if this can be expressed as 2^ x - one or not how am I directly saying it okay look at this 2x minus 1 the significance of this is if you are taking 2 power x what are the possible things you can take one you can take two which can be represented as one Z then the X power would be four which is 1 0 0 then the X power would be 8 which is 1 tri0 and so on yes this is 2x what is 2x minus one in this case it is simply zero in this case it is 1 in this case it is 3 4 - 1 which is 1 1 in this case 8 - 1 is 7 which is triple 1 and in this case 16 - 1 is 15 which is four vales so I now we understood what's the significance of 2 xus one it will contain all ones only in the binary representation so hum if you take any number consisting only one one then all Zer and if you subtract a one from it you'll get all ones and this one would turn to zero so that is why we simply get all ones so that's a significance of 2x - one and that is how I directly said this cannot be expressed as 2x - 1 and this cannot be expressed as 2x - one so the first thing we figured out is 2 x - one contains only once in the binary representation now 66 we have already checked coming to 11 17 18 5 and six 1 is simply 0 0 0 0 1 17 is simply 16 + 1 18 is simply 16 + 2 5 is simply 4 + 1 and finally six is simply 4 + 2 these are the minary representation if you do R of everything we are getting 1 Z 1 1 1 so we have to figure out if there is a way to only get 2x - 1 and we cck clear know this is not 2x - one because it contains a zero not only on now moving to the next part the output given is two that means by removing two elements we are able to get 2 xus one if you clearly observe there is no way of getting one in this position because any number you take it does not have one so R would never result in one so consider these two is of no use so we'll take one five and six so considering only five and six only five and six which is 10 1 and 110 and if we do R we are getting triple1 which is equals to 7 so we can remove all these three 17 17 and 18 but the question clearly said minimum number of elements that needs to be removed if we put one with this the r would still be seven so one can still be included it need not be removed so we only remove 170 and 18 that's how we got the output as two everything's clear so far so the second point is remove minimum number of elements now if all this is clear we have to figure out how to solve this if you have any approaches before I reveal it comment your approach in the comment section and uh yeah here we go so first thing one mination is simply one two it's 1 Z 3 it's 1 1 1 sorry 1 0 0 5 it's 1 1 6 it's 1 1 0 7 would be 111 then for eight what would happen now we got only three bits right we'll be getting one more bit one Tri 0 so the possible 2x - one values are one of course z is also there but for now let us not consider it then three then 7 then 15 then 31 and so on so for us to get one can we consider this of course not because this V is set in two and three so if you consider those you can never get one and for three can you consider four 5 6 and 7 no because this bit will be said when we do R so we can only consider anything in the so for seven we can consider anything from this and similarly for 15 from which value to which value can you consider perfect any value below 16 so we understood to check first if one is possible then three is possible seven is possible our elements cannot be greater than those so it cannot be from four for three it cannot be from eight for seven and so on so that's one more point to observe next thing let us say we have 01 and uh we have 1 0 0 and then we have 1 0 0 if we do R how do we get 1 0 1 why did you get this because two and three are not present which contribute for this bit so we cannot directly do R for one and four and directly say seven is not possible yes so while doing or we need to follow the other so one must be hard with two or three before doing with four five 6 or 7 so once the we are sure three is not at all possible then we can set for seven so 0 1 1 0 1 2 3 is not there so we are directly saying three is not possible of course now if we have a six in this case seven is possible now so our next observation is while doing r we have to go in an order we cannot skip the order because if you are skipping the order we will never know if these numbers are possible or not so in this example we took 1 48 let us after this we have a two considering only this we are saying three is not possible but if we considered 1 and two getting three is possible which is 2^ x - 1 so first we need to sort our data 1 2 4 and 8 and only then continue in correct perfect so that is another observation that is we need to sort the data only then we can check integer by integer are you able to think of an approach before I reveal the final St if yes just comment on yes fine those who couldn't figure it out so for this case 1 17 18 5 6 it's simply 0 0 0 0 and 1 this is simply 1 0 0 0 and 1 this is 1 0 0 1 0 this is 0 0 1 0 1 and for is 0 0 1 1 0 in this case s was the answer so if we did 1 or 17 we'll get the answer as 1 0 0 0 1 correct that is 7 from this is there a possibility of getting seven after doing r no because this bit became set we cannot unset it by doing R so that was observation we just made our data should be sorted now the data is started now let us start doing R here we got one so now we know that 1 is x - 1 is it correct so for xal one we know that we can get 2x - 1 and one more way as we discussed it has only one one we know if the bit representation is containing only once then yes so yes now when we do r with five what do we get one1 itself one or with one1 we get one one itself correct is 1 1 2^ X - 1 no because it has a zero now we do r with 6 what do we get 1 1 1 that is for this if we do r with six we simply get one one and one now seven it contains all ones so this can be the answer so in this case how many elements must be removed if we can this as answer two elements must be removed correct and if we consider one as the answer how many elements must be removed four elements must be removed which is the best answer only two elements so what are we doing simply we are first sorting the array then we are doing R element by element and after doing R whatever result we get we check if that is equals to 2^x - one or not that is if it contains only once or not if yes then we can simply our update our answer to removing the remaining elements in the future if we get a better answer we update our answer so in this case four was the answer in this case nothing because R is not equal to 2x - one in this case Ral 2x - 1 so we remove the remaining elements two will be the answer in future if we get better answer we'll update the answer with that now how to directly get the answer so if you at 0o you got the answer is 4 n = to 5 I value equal Z that is index equal to Z can I simp simply say this is nus I + 1 you can check for this case as well 5 - 2 + 1 which is 3 which is equal to 2 we got two so we can directly update the answer to nus I + 1 once we get the of 2^ x - one so suming it up first thing we know 2 xus one will contain only once second thing we have to remove the minimum elements third thing we have to sort the array so what was the approach first we sort the array then do R and whatever r value we get we check if that is equal to 2x - 1 how do we check it should and if it is 2 xus one we update the answer to number of remaining elements that is we assume we'll remove all the elements in the future if we get better answer then we'll update the answer with that better answer done shall we C it up first three testes are given and c and we look for three times and then thing first n is given which is size of the array we have read that and we need to create an array of that size after that perfect simply read the input into the array now we have the input with us watch an extra print the output so see how let us say AR removal or we are passing AR on the size of the and of course output should be separated by new L just [Music] and the size of the now what are we supposed to do we have to iterate on the and simp have to do R so n or answer initially I'm keeping it as zero so we need to start itating for i z i than I ++ what we have to do we have to do R and check if the R value equal to 2 xus or not if yes we need to update the answer so forther I will take the answer as well initially what should be the answer we'll assume all the elements must be removed so that will be the answer if you get a better answer it will be updated yes our answer or equals to short annotation AR of now what do we have to check we got the R value we simply have to check if r value = 2x - one or not so check or answer if this is the case what do we do answer assigns nus I + and the answer what's left up check function check what we have to do now perfect have to check if it contains Z or not so why n greater than zero if n and one equals to Z we can simply return false and I return right and false was not return Then true so this is how we check if the given integer in its binary representation contains zero or not so as long as it is not zero we write shift and every time the last bit we'll be checking how to check the last bit simply do n and one if it is one we'll get as one if it is zero we'll get as zero that's it let us run and check two and two are the expected outputs okay we got two and four any guess us why yes if you have guessed it we did not s the without sorting one that's our discussion now we'll be getting to and perfect submit correct answer so that was approach and the solution for the second question now let us solve the next question number given a positive integer X find the smallest positive integer y satisfying all the conditions what the conditions first condition y should not be a prime second condition y should not be a perfect square and third condition no factor of Y should be less than x other than one so factors of y should be greater than or equals to X it should not be less than x and if there's any factor it's only one we have to find such number X mentioned why might not fit in the 3 bit integer range we'll come back to that later and you are given key test cases for each test case you are given an integer X you simply have to print that y output format for each T Cas we simply have to print the separated by new Lan and again it's mentioned y might not fit in the 30 bit integer range we'll come back to that coming to the sample AO we have 1 2 and three for one the possible number set we can take starting from one one 2 3 and so on so let us check can one be taken first thing is one no are factors of Y that is factors of one greater than or equals to X that is one yes one factors are one and one so they're greater than or equals to one but why can consider one because one is squ what about two it is a prime what about three prime again four per square 5 Prime again six let us Che six we have one 2 3 and six itself do you see any factor of six less than one no and is 6 per square no 6 a prime no because it has more than two factors six is the answer I got six as the answer com to do any number from Two Can Taken 2 is a prime excluded 3 is a prime excluded four per squ excluded five Prime again and six let us check so for six these are the factors other than one do you see any Factor lesser than two no so for it will be six coming to three can 6 B Tak 1 2 3 4 5 have rolled out already we know why and six cannot be taken because it has a factor which is lesser than three what about seven it's a prime so cannot be taken what about eight one of the factors of8 is two so it cannot be taken what about n perfect square so cannot be taken what about 10 one of the factors is two which is lesser than three so cannot be taken what about 11 Prim so cannot be taken what about 12 again factor is two so cannot be taken what about 13 prime so cannot be taken 14 factor is two so cannot be taken 15 15 is not a prime not a perfect square we simp have to factors 1 into 15 and 3 into 5 other than one do you see any factors lesser than three no so for is the answer so what would be a brute for solution we simply start itating from the given number and first if it is prime if yes continue if it is perfect square then also continue if factors of it at least one factor of it is lesser than the given number then also continue else we simply return or print that number but what will happen if you do exactly that here it's clearly saying that for 10^ 9 the numbers you'll start from 10^ 9 and we go number by number verse case it will take care it it will be taking huge time and to get the factors also will will be requiring so much time and again storing those factors so lot of time of course you can do it without storing the factors as well you can simply check one by one factors if it is lesser than the given number you'll simply neglect it so Brute Force you might get a t any other way I mean can we optimize it somehow let us look first for any given number how can we directly get the answer is there any way it is a math question think in terms of that so if you given any number X and you have to find a number y such that factors of it are greater than x or equal as well which numbers can we pick so we understood after it we need to take such number which is not a prime not a perfect square and factors of it must be greater than or equals to X now if you taking any number which is greater than x and not a prime don't you think it will have a factor lesser than x of course it will have right if x is a prime what is the first number you'll be getting such that the factor of it will not be lesser than x it will be x² I mean there are multiple numbers but the first number that comes to Over N mind is X squ we can take this but what's the issue it's a perfect square so that is R out what else can we do so first thing we have to find the number a such that factors of a should be greater than R equals tox what kind of number is a according to this so it should have a factor only greater than x so can I take a as Prime then the factors of a will be 1 and a but what's the isue it's clearly said we cannot take a prime now let us take another number B which is also a prime factors of B will be 1 and B this two numbers individually cannnot be the answer but what about the product of this it can be the answer right a into B will be a number which is not having a factor lesser than x and a into B is not a prime and it's not a perfect square as because a and are different numbers but what are A and B simply two primes which are nearest to X now can a be X as well yes factors of a are one and a factors of X are one and X so if x itself is prime then we can take X as well as a but keep it keep it in mind if it's only a prime so how to get a and b simple from X we will start iterating until we get a prime let's say we get a and from a we start iterating or to be more precise from a + 1 we start iterating until we get a prime and we get B and we simply have to return return the product of this first so in C and then while T minus minus we are given integer and what should we do as we discussed we have to find out a number more specific a prime number which is greater than or equals to X so from X we should start iterating and get a prime once we get that a we should also get B what should we do for that perfect from a + one we should start iterating and then get the once we get a and what should we do simply print a into B sub the new line do you see an issue with this the given constraints X can be any value up to 109 so after reading x you'll get a value which can Beal as well so get Prime for 10^ 9 will be some number which is greater than 10^ 9 and get Prime when we are calling it for B will be even more greater number and the product of those will definitely not fit in the integer range so that is why it's clearly given y might not fit in the 32 integer range so what do we have to do we can type cast or simply change these two [Music] long get function so long get point of index if you see here we're taking integer and we start adding if the value goes to long then what to do of course it will not go it won't go but if it goes so you have to be careful for this case it will not go so simply iterating from X would work but if it goes it will not work so we will be taking long long end in that case for this even without taking a good work now what do we have have to do we have to start iterating from X till we don't know we find the prime so is it correct of course not we using so while the given number is not prime what should we do simply in is a value of x until we get a prime that's it are I missing something nothing as of now of course done now the final thing if we complete this is Prim Prim we simply have to check if it is having any factor from two to square square root of its number so from to to square root of its number if there is a fact that is if X Mod I equals to0 then we return return false and we simply return true that's it are we missing something here long long index has been taken and we are checking square root I into I so this should also be long long that's it let us test our code okay so B was not declared in the score it's declared what else long long be okay semicolon over here so we got 2 six and 15 but for one what should we get six so what's my here one is not a prime so if x equals to 1 what should return FS 66 and 15 it worked perfect yeah guys that's it for this video for more such videos follow this Channel and let me know which solution was more interesting in the comment section