# GFG Weekly Coding Contest - 150 Post Analysis | GeeksforGeeks Practice

GeeksforGeeks Practice2024-04-15

geeksforgeeks courses#data structures#programming#geeksforgeeks#gfg#GFG#GeeksforGeeks#geeksforgeeks practice#gfg practice#GeeksforGeeks Practice#practice#gfg problem of the day#gfg practice problem#problem of the day gfg#coding problem#data structures problem#data structures and algorithm#weekly coding contest gfg#weekly coding contest#gfg weekly coding contest#weekly contest 150 live#gfg live#weekly coding contest 150 analysis#gfg weekly coding contest 150

1K views|3 months ago

ðŸ’« Short Summary

The video discusses the Geeks for Geeks weekly coding contest 150, focusing on problem-solving strategies, dynamic programming, and bit manipulation. It covers various coding challenges, emphasizing efficient problem-solving techniques and the importance of understanding problem statements. The speaker also highlights the significance of binary representations, optimizing bit operations, and utilizing a two-pointer approach for solving complex problems. Overall, the video aims to enhance viewers' coding skills, critical thinking abilities, and problem-solving proficiency in handling different programming challenges effectively.

âœ¨ Highlights

ðŸ“Š Transcript

âœ¦

Geeks for Geeks weekly coding contest 150 overview.

01:54Difficulty of the four problems leaned towards constructive algorithms.

First problem focused on finding common ground between two people.

Second problem involved substring and permutation and was relatively easier.

Last problem required understanding of bit manipulation and was a modification of classic frog jump problem.

âœ¦

Improving problem-solving and critical thinking skills.

08:10Emphasis on understanding the thinking process and deriving valuable insights.

Key topics include string board problems, substring and permutation, maximum points, and array operations.

Equipping viewers with skills to tackle different problems effectively.

Encouraging critical thinking in problem-solving scenarios.

âœ¦

Understanding the problem statement is crucial for converting substrings of 0s and 1s into all 0s or all 1s.

15:06The explanation intentionally lacks examples to encourage problem-solving without relying on them.

Equal substrings on both sides are necessary for successful conversion.

Problem-solving strategies and understanding the problem statement are key focuses of the video segment.

âœ¦

Characters in a string cannot be modified to match specific patterns.

21:55Invalid condition arises when certain characters in the string have fixed values.

Converting all characters to predefined values based on the condition is discussed.

Solution involves converting all characters to either 0 or 1 based on the condition.

Importance of maintaining the specified pattern is emphasized.

âœ¦

Explanation of a code problem involving finding common substrings in two strings.

25:14The solution requires iterating through the strings and checking for common substrings.

If a common substring is found, the function should return true, otherwise false.

The speaker seeks confirmation on the clarity of the solution before moving on.

The discussion transitions to a hypothetical scenario involving retrieving specific plants based on their indices in a row.

âœ¦

Efficient plant collection strategy and problem-solving techniques.

32:16Determining the farthest index to collect required plants based on a given sequence.

Rearranging the order of plant collection for optimal efficiency.

Solution involves finding the farthest index and adding one to it.

Emphasizing the importance of understanding and testing the problem, especially when certain plants are missing.

âœ¦

Highlights from the segment on storing indexes and retrieval system.

36:15The segment focuses on storing indexes based on character appearances and building a map for quick access.

It emphasizes the importance of handling cases where the index exceeds the size array by reporting -1.

The speaker provides a detailed explanation of how to efficiently retrieve specific characters based on their indexes.

The implementation of a retrieval system based on index positions ensures a seamless process for data retrieval and storage.

âœ¦

The segment focuses on a coding problem related to finding the minimum distance to reach specific indices.

43:02The speaker explains the concept using an example of planting crops.

Lower bound for character frequency is used, and indices are iterated through to solve the problem.

The solution includes counting crops and returning -1 if the required amount is not available.

The speaker highlights the importance of understanding the solution and engages the audience for confirmation.

âœ¦

Maximizing value through strategic skipping.

47:39The process involves analyzing the value of points and deciding which items to skip.

By taking strategic jumps, it is possible to maximize the overall value obtained.

Evaluating different scenarios is crucial to making optimal choices and achieving the desired outcome.

âœ¦

Approaching decision-making in the face of confusion or indecision, using the example of choosing between medical and engineering fields.

52:11Trying out all possible options is crucial in reaching a conclusion.

Recursion is discussed, noting its high time complexity and ways to optimize it through memorization and dynamic programming.

Emphasis is placed on building recursive solutions, with an explanation of base cases and recursive cases in problem-solving.

âœ¦

Memorizing dynamic programming solutions and understanding dynamic parameters.

59:25The importance of declaring arrays or maps of the appropriate dimensions.

Debunking the myth of 2D and 3D dynamic programming, stating that the number of dynamic parameters determines the solution's dimension.

Recommending starting with basic problems like Fibonacci series and 0/1 knapsack to build expertise in dynamic programming.

Emphasizing personal choice in learning and suggesting focusing on iterative building rather than recursive functions.

âœ¦

The segment discusses a complex level problem involving finding pairs of I and J where I is less than J and certain conditions hold true.

01:04:50The problem requires considering all indexes and performing operations on them to find the answer.

The video assumes a certain level of coding knowledge and familiarity with modular arithmetic.

It emphasizes the importance of understanding these concepts before attempting to solve the problem to maintain motivation and avoid frustration.

âœ¦

Importance of Bit Manipulation in Understanding Binary Representations.

01:08:24The segment explains the calculation process for different binary values and how to determine the contribution of each bit to the final answer.

Examples are provided to demonstrate how specific binary combinations result in zero or other values.

The segment serves as a tutorial on basic bit manipulation techniques.

Viewers are encouraged to think in terms of bits when solving problems.

âœ¦

Importance of Computing Contribution of Each Bit

01:16:19Emphasizes optimizing operations per bit to avoid redundant n square operations.

Setting the value of each bit correctly is crucial for efficient computation.

Example provided using binary representations of numbers like five and four.

Focus on understanding the contribution of individual bits in the process for efficient computation.

âœ¦

Understanding binary representation and conversion.

01:20:34The segment explains converting binary to decimal and vice versa using examples like 7 and 14.

Importance of recognizing when a value contributes to the overall result or remains zero.

Discussion on bit-by-bit contribution and finding the contribution of individual bits in a binary number.

âœ¦

Importance of processing in terms of bits and challenges of N Square operations.

01:29:55Need to consider all I and J elements and find the result efficiently without exceeding time limits.

Significance of observing the sum of bits to determine their contribution to the answer, with the sum needing to be one.

Focus on optimizing operations and efficiently processing elements to achieve the desired outcome.

âœ¦

Conditions for contribution to the sum.

01:35:57A bit contributes if both A and B are turned on and meet specific value-related criteria.

Bits are kept in a 2D format and a two-pointer approach is utilized.

Emphasis on specific values and conditions for bits to contribute to the final answer.

âœ¦

Two-pointer approach for increasing the sum of Ln R.

01:39:13The sum is less than 2 to the power i-1, Ln R value should be included in the answer and R should be moved forward.

Conditions where certain bits contribute to the answer based on their values.

Involves sorting values and using two pointers to find values greater than 2 to the power i.

Focuses on finding all l+R values greater than 2 to the power i.

âœ¦

Discussion on contribution of each bit in a complex problem involving bit masking and fusion of two pointers.

01:47:11Understanding transition points is crucial to solving the problem effectively.

Analyzing values of A, B, and E in relation to 2 to the power of I helps determine contribution to the answer.

Adjusting the pointers can lead to a better sum and ensure certain combinations meet required criteria for inclusion in final solution.

Importance of grasping underlying concepts to navigate through the problem effectively is emphasized.

âœ¦

Finding pairs in a sorted array with a sum greater than or equal to a given target.

01:50:30The solution utilizes two pointers and bit manipulation for efficient computation.

The speaker seeks feedback on the explanation's clarity and expresses a willingness to enhance it.

The video ends with a message of gratitude and a call for viewers to like and comment for encouragement.

00:02[Music]

00:19[Music]

00:34[Music]

00:51[Music]

01:06[Music]

01:17[Music]

01:24[Music]

01:42hey hi and welcome to geks for gigs I am

01:46zadat hazra and today we will be

01:48discussing the Geeks for geeks weekly

01:50coding contest 150 and this is the post

01:54contest analysis so before we start

01:58talking about what what is the solution

02:01and what are the intuition behind them

02:03let us first talk about the problems

02:06overall what was the feedback from my

02:09side so this time the problems looked a

02:14bit on the difficult side there were

02:16four problems and they were good there

02:20was a good balanced among all of them

02:23but what I think of is that if you're

02:27not very good very good with

02:30constructive algorithms I would take the

02:33second problem as the first one if

02:35you're not good with constructive

02:37algorithms but if you are coming from a

02:41background where you are very good with

02:42constructive algorithms then this

02:45context is well balanced but the people

02:48like who are

02:50just okay solution always like comes but

02:53after the contest okay we would talk

02:55about those all so let's talk about the

02:57very first problem the very first

03:00problem if I talk about the intuition

03:03overall for all the problems okay so

03:06let's talk about the string reboot

03:08problem in the string reboot problem the

03:11very small intuition that needs to be

03:15understood is a very small observation

03:18is that instead of trying to make a as b

03:23or B as a we can

03:26both okay we can both come to a common

03:29ground what I meant to say is that if

03:33you are given two people and this person

03:37should change and this person should

03:39change some qualities to become him or

03:41some qualities to become him then it is

03:43tiresome but if you look that we can

03:46both come to a common ground and then

03:48see if both we both can become this

03:51person or not

04:14equ this is the intuition of the first

04:18okay this is the intuition let's talk

04:20about the very next one that is

04:22substring and the

04:25permutation this is comparatively on the

04:29easier side

04:30or

04:31paper you would understand what needs to

04:34be done and this is a pen paper solution

04:38okay the last one is the maximum point

04:41so what I say is this is just a small

04:46modification of frog jump one or frog

04:49jump two the very classical problem of

04:53atcoder DP Contex so is what needs to be

04:58done is

05:00these kind of problems these kind of

05:02problems are just a variation of the

05:04standard problems so if you are not able

05:06to solve this problem you need to be

05:08good with the standard problems of

05:10dynamic programming the very last

05:12problem the very last problem I would

05:16say that you need to be very good with

05:20bit manipulation to solve up the last

05:23problem but but

05:25but it becomes easy if you have seen a

05:30problem like this before like this

05:32problem is broken down into two pieces

05:36okay and is solution I can't give you

05:40the intution but this is just narrowing

05:43down from n Square to n okay narrowing

05:47down from nÂ² to n and whenever you don't

05:52care about

05:53indexes

05:57okay we just need to find the number of

06:00pair and here the in original index does

06:03not matter when the original index does

06:06not matter and when the index does not

06:10matter then we can sort it or

06:14sort so this question is of two

06:18pointers these are all the different

06:21intuitions or these are all the

06:23different

06:26Pathways okay fair enough now let's move

06:29forward to the editorials of these all

06:32problems okay am I clear

06:36with am I am I clear with these all

06:38things just give me a quick zero or

06:41one yeah am I clear my voice is clear do

06:45I need to turn off this fan or my voice

06:48is like glittering a little bit or

06:49something okay let me just turn off the

06:51fan

07:01[Music]

07:02okay now I think the room is very well

07:06quiet and the audio quality would be

07:08fabulous so if you're able to comprehend

07:11till this point just give me a

07:14one it's fine the quality

07:18like the if one person is suffering for

07:22these many people it's fine okay

07:26so and to be honest not just suffering

07:29this is is just a matter of one 1.5

07:31hours so sub mil see sub mil let's do

07:36this kind of

07:38discussion kind of I am not going to

07:41give the editorials and move forward see

07:44the whole objective of this stream would

07:48be not just Ed tutorial but next time

07:51when you see a problem around this you

07:54would be able to solve this the thinking

07:56process okay here you are just here for

07:59the thinking process and the it to all

08:02the ideas which you can take here from

08:04these are the two objective of this this

08:07is the whole objective of absolving okay

08:10so let's start with the very first

08:13problem okay in the first problem what

08:17you are

08:18given let me

08:22first copy these two

08:32and here you

08:38go Al B after a long period of time I'm

08:42taking the weekly after a very long

08:45period of time there was once a point of

08:48time where every weekly was taken by me

08:52then I got busy with some other

08:53commitments and now again I'm back and

08:56I'm planning to do this on regular basis

09:00okay no I would go with the flow if

09:03you're here for the fourth qu just for

09:05the fourth question and you don't care

09:07about all the other three you can just

09:09wait a bit but I would

09:12say

09:15perspec okay I would go with the flow

09:18very first problem would be string board

09:20next Str substring and permutation

09:22maximum points and array operations good

09:25enough so let's move forward CH let me

09:30just share my whole screen

09:46and there here you given two binary

09:50string okay it is told that it would

09:53start with zero and end with one now

09:57what you can really do okay choose an

10:00index 0 to 0 okay fair enough so what

10:06are the small observation we have let us

10:09discuss those see here you are given two

10:14strings and both of them would start

10:18with zero and end with

10:21one okay these things would change but

10:26zero and one in the start and the end is

10:29fixed enough okay what is the operation

10:33that you can do you need to take you

10:37need to take let's say 0 1 0 1 and then

10:42this is zero so you need to

10:45take

10:47lnr then convert all the values in

10:52between lnr with the value of n so if

10:56there is zero and zero and you want to

10:58convert the substring all this substring

11:00would be converted to zero and remember

11:03you can take up this value okay what how

11:08the first one is coming up the very

11:10first one is coming up

11:12because let

11:19me see the very first one how the very

11:22first one is coming up see you what we

11:25can really do

11:27is we can

11:30take up this we can take up this okay we

11:34can take up this and this and

11:37then so it is told no let me just see it

11:42just a sec see what we can really do let

11:45me just take a green pen

11:47y so see what we can really do is if you

11:52ask me I would take this 0 to 0 I would

11:56take this 0 to 0 and then then I would

11:59convert every one of them to zero yes s

12:04values all the values would be converted

12:06to zero all the values would be

12:08converted to zero and I would have 0 0 0

12:110 0 1 0 0 0 0 1 and that is why the

12:15output is here as one okay now the very

12:21next thing what I would do here in this

12:23case see I would

12:26convert 0

12:31to Zer till this point but here the next

12:35point is not here so here I can cater

12:39these all as equal but see 0 1 and 1 1

12:44can never be converted can never be

12:47converted okay now this is why the

12:50output to this is zero now a small

12:53observation is If You observe this

12:56explanation like again this

13:07the sample explanation was this you

13:09could have solved this problem but the

13:12explanation of the sample test case is

13:14given in such a way that you won't get

13:16to the solution this is done

13:19intentionally so that the solution is

13:23not evident enough okay so the first

13:27learning what I like

13:31learner

13:34explanation in adoc problems you don't

13:37need to see this explanation you try to

13:39solve it on your own and then see

13:43explanation for you this explanation

13:45should not exist this explanation should

13:48only be used to understand the problem

13:50statement not to understand the example

13:53test

13:55case now what is the solution for this

13:59okay

14:03basally so that you don't get near to

14:05the solutions okay now what you can

14:08really do

14:10is if somewhere here it

14:15is0 let's say we know that the string

14:19would be contributed of zero and one in

14:21the start and the end so if what you can

14:25do is if let's say there are many

14:27characters like this so let's say at any

14:30point you just take this as zero and

14:34here it is one so what you can do is you

14:38can select up this substring and convert

14:41all of them and make it zero using this

14:46then you can select all this substring

14:49take consider this character make all of

14:51this as

14:53one makes sense

15:00okay just

15:02say see again doing the sample test case

15:06from the scratch so that you have a

15:09better idea what I am talking about see

15:131 0 0 1 0

15:170 0

15:201 okay and this is 0 1

15:251 1 and then 0 1 0 0 1 so what I can

15:31really do

15:33is I can take up this and convert it to

15:370 0 0 I can take up this convert it to

15:4111111 I can do this okay here also I can

15:46take

15:47[Music]

15:49up here also I can take up till this

15:54point yep till this point

16:03yep we can take up the substring of both

16:06of them make them as one okay 2 2 4 and

16:11this s okay so now what is the condition

16:15where we won't be able to do

16:19this intu what is the condition when we

16:23won't be able to do

16:26it okay if this is the condition

16:29we can do it but if let's say it is

16:34something like this

16:36problem let's see what is the problem

16:40they 0 0 1 0 0 1 okay here we have 0 1 1

16:51and then 0 1

16:531 and here we have 0 1 1 we have some

16:59like

17:00this

17:05okay why can't we convert see if we take

17:11up this this is equal this is equal

17:14because s of L and S of R should be

17:18equal be equal be equal we can make the

17:23whole string as zero we can do this but

17:28here

17:29we can't have S and L equal condition we

17:35need to select lnr and S of L should be

17:39equal to S of R they should be equal so

17:44we can't select a substring over

17:46here this is causing the

17:50issue

17:51okay so now this is the invalid

17:55condition that would tell us

17:57so am I clear till this point the

18:00invalid condition we can't select a one

18:04I would tell you more first tell me if

18:06I'm clear till this point or

18:08not if there is a condition like this we

18:10can make like this yeah we can do the

18:14same thing

18:15but this can become 0 0 this can sorry

18:19this can become one one but this

18:2201 can't be modified into anything 01

18:25can't be modified into 1 1 or 0 0

18:29am I clear that this can't be modified

18:32am I clear just give me a quick one 0

18:36and 01 can't be modified just give me a

18:38quick

18:39[Music]

18:42one just give me a quick

18:46one okay we

18:51have problem

19:03please explain no we

19:07need okay I'm clear that this can't

19:11happen Okay so what is basically the

19:15invalid

19:18condition just let me check the

19:24comments

19:27okay h

19:29let me present the whole

19:44screen

19:46okay we have

19:55this okay now

20:0001 can't be converted so whenever we

20:05have this condition that this is

20:09zero okay and this is

20:141 okay and this is also zero okay this

20:18is also

20:21zero and this is

20:24one whenever we have this condition in

20:28any of them let's say this would be zero

20:31I know here it would be one here it

20:33would be zero here it would be

20:35one

20:40okay fixed last here we have any of the

20:46characters how beautifully we can

20:49convert

20:51be we have this

20:55condition that this current part is zero

20:58and that part is one then we can convert

21:02all of this then we can convert all of

21:06this to zero and all of this to one for

21:10both of them now let's try this out

21:14let's try this out for the first string

21:18now let's try this out as

21:26a now see

21:29okay 0 0 1 1 1

21:351 okay

21:45see here we can take of this and we can

21:52take up

21:55this and we can convert all of them

21:59to here this part would be converted to

22:01zero this part would be converted to one

22:04how again showing you in a better view 0

22:090 both are 0 0 so we can convert that

22:12side and this is also equal equal this

22:15is L again this is R again this is L and

22:17R so we can convert this to one and this

22:22to zero so this would become something

22:25like 0 0 and 1 1 1 one one one one so

22:27both become equal and we come to the

22:30conclusion condition 0 0 so this should

22:35become 0 0 and this should become one

22:37one and you we have one one standing

22:40here we have 0 0 standing here we know

22:43this these two are here to these this

22:47zero is to support here this one is to

22:50support here we know that so as a

22:53condition I would convert these all to

22:56zero I would convert these all to one

22:58now the solution here

23:10is so let me just show you the

23:19solution okay so what I did is first I

23:24took that this is not valid now we tried

23:26started searching okay so let's say the

23:30current here is zero as explained was

23:33zero one this is zero and this is B + 1

23:38means one this is zero and one

23:42okay so I would take a snapshot and then

23:47explain

23:48you today explanation of like I won't

23:52write the code from scratch rather I

23:54would explain this

24:10just AIT to

24:21look

24:26yep so see what are we basically doing

24:30see we started

24:32counting from zero and then this let's

24:37say this is the string a and this is the

24:40string B if at any point this is equal

24:44to

24:45zero okay and the very next character

24:48this is equal to 1 then we go to the

24:52next Ste statement you can just nest out

24:54all the four condition together also

24:57okay then if this is equal to this that

25:00means 0 is equals to 0 and this is

25:03equals to this that means this is one

25:06whenever we have a substring like

25:11this common substring like this in any

25:14of A and B we mark it as true that yes

25:18this can be converted and we return it

25:20if we don't find this condition it would

25:25preserve as false and we would return

25:26return am I clear with the Sol am I

25:29clear with the solution of the first

25:30problem give me a quick one so that I

25:32can move forward to the next

25:35problem give me a quick zero or one this

25:38is me SRA

25:43J so it ask us to return a true or false

25:48driver code after the prints 0 or

25:53one sound minus minus what is this

25:56thing any problem

25:59here

26:00so what is this driver code

26:04issue output one and zero okay one and

26:08Zer is fine enough so what is the driver

26:11code

26:13doing yep no

26:16issues I hear you fine

26:20okay CH clear let's move to the next

26:23problem yeah comparatively on the easier

26:26side

26:30I would again take a

26:42screenshot okay

26:46so this was a long weekend for working

26:50professional working professional and

26:52how many of you went for Long

26:55Weekend people who would I think the

26:58people who would watch this post contest

27:01analysis

27:03later okay are the people who are

27:05enjoying their long weekend

27:10and okay

27:31okay so you are given a string of length

27:34and character of strings okay this is

27:38the string that is

27:42given to make

27:45088 how far you need to go okay this is

27:50just like what I would say is this is

27:53just like this compare this that this is

27:57what yeah make

28:00example okay compare this as a strip of

28:05land

28:07okay let's say this is a strip of land

28:11where farming is made and these these

28:16this is the plant of type zero this is

28:18the plant of type six this is the plant

28:21of type four this is the plant of type

28:23eight this is the plant of type one

28:25let's say Z to n they are the types of

28:29plant in a strip okay let's hear a story

28:34okay as like story so strip strip of

28:37land and these are the different types

28:40of plants planted in a

28:46row let's enumerate them let's give some

28:50indices to

28:52them okay so type so this is the index0

28:581 2 3 4 5 6 7 8 9 10 and 11 okay fair

29:07enough now it is told that what I want

29:11is I want the plants

29:15088 I want the plants 088 so I would go

29:20and plug this zero now the next Plant I

29:25want is eight so I would go and cross

29:28this

29:30eight next I would go and cross this

29:34eight how far I went I went till the

29:38index six that means I went till the

29:447eventh plant to collect the values this

29:48is just like like these are the

29:50different types of plants and these are

29:52the different crops they want and they

29:54they are asking how far you need to go

29:57okay

29:59this is just like let's say my father is

30:02farming and he has all this plants in a

30:04strip he asks me I want you to collect

30:08088 the type of plant

30:11088 how far you need to go from the

30:14house because he's very concerned about

30:26me or

30:35okay so I

30:37told

30:41last the maximum I need to go is seven

30:44this is what is asked in the question

30:46now there is one small observation

30:50ke these can be rearranged that just

30:54means Z if my father is asking 088 I

30:59need to collect 088 in the order I can

31:03collect 8 then 0 and then 8 why because

31:07after that I can

31:09[Music]

31:14rearrange okay denotes the minimum to

31:16construct any possible permutation

31:19possible

31:22permutation 88 88 collect

31:26808 collect

31:29peration

31:338 this is what is the depiction of the

31:37problem am I yes I'm good

31:40enough no issues

31:44okay

31:46so if you're able to comprehend this

31:48problem and draw out the test cases like

31:50this then this problem becomes easy now

31:53if I want 364 I would go and strike out

31:56first three I would

31:59I would go and find three this is three

32:02then I would go and find six and then I

32:06would go and find four I would I would

32:08try to find the characters from the

32:13front come I can collect the plants this

32:16is what is asked so the maximum far I

32:21need to go is till the ninth character

32:23that means till the ninth index means

32:2510th character to collect three I would

32:28say father to have the have the plants

32:31364 I need to go till the position 10 so

32:35he said okay this is the maximum farest

32:37position you need to go now I what my

32:40father wants me to do my father wants me

32:43to build to find crops which does not

32:47exist that is Zer and seven so I found

32:49out zero but I can't really find seven

32:52father one crop is missing what you are

32:55asking so he would say one crop is

32:58missing that means you you don't need to

33:00go out so whenever you need don't need

33:03to go out just return minus one here

33:06okay this is what is asked in the

33:11question now what is the solution of

33:14this problem like what see end of the

33:19day you just need to find the farthest

33:22index and that would be and that index

33:25plus one would be your answer

33:29farthest index plus one would be my

33:31answer by doing this first tell me if

33:34I'm clear with the test cases or not

33:36test Cas then there is no point in

33:38telling you first tell me if this test

33:41case is clear or not with this story

33:44give me a quick Z

33:45One Z

33:49one give me a quick Z or

33:52one okay what if both and there is no

33:55instance where where

33:58what if both strings are equal and there

34:02is no instance where the condition is

34:09met that would I think so so given a

34:15string string robot okay given both the

34:17characters you can perform any number of

34:20s choose two character and then turn all

34:22the characters formally you can choose

34:25so let's say this is 0 1 1

34:331 okay let's say everything is

34:38zero let's say everything is zero and

34:41this is

34:48one still this condition would be met

34:51there is there won't be any

34:54string 0 1 1

35:02okay so 0 and 1 and let's say here it

35:08is

35:10one there won't be any

35:12string

35:15yep am I clear with the clear

35:20one we are guar it is not possible to

35:23have Z one yep CH there are only two

35:26three people there won't be stream

35:30conf and this happens while you are just

35:34streaming okay so let's move

35:37[Music]

35:38forward we just zero or one and on that

35:41makes the

35:44difference up

35:47they I didn't get any zero so I would

35:50just assume that everyone is clear with

35:52this okay so now what I really need to

35:55do

36:00see I would start storing the index see

36:04for Zer what are the different index I

36:07have this is for index 0 1 2 3 4 5

36:136

36:157 8 and 9 okay let's say this is so I

36:22found out zero so I gave here zero this

36:25what is these are the character

36:28and these are the index that they appear

36:32so zero I find out zero

36:36six appeared in the index one four

36:41appeared in the index

36:4428 appeared in the index 3 count why

36:51because the farthest index matter index

36:53matters okay then we can go to one and

36:56then we can write

36:58for one the answer

37:02is four for one the answer is four then

37:06for nine the answer is five for eight

37:12the answer is six we will just go and

37:16has them for four the answer is seven

37:21for eight for8 the answer is

37:25eight okay for for three the answer is

37:32nine for next three the answer for three

37:37the answer is nine for nine the answer

37:40is 10 and for 8 the answer is

37:4611

37:47up what is

37:49asked 0 is asked once and eight is asked

37:54twice for the now first we would

37:58store for each index for each of the

38:01characters 0 to one we would store the

38:03indexes in they Walker first we would

38:06this would we would build a map like

38:08this

38:10just then this is the kind of

38:13implementation at the end of the day

38:17Z one so I would go and hit we know that

38:22as we progress further the indexes would

38:24increase so for getting one Zer I would

38:29directly hit for the first index and if

38:32I want two zeros I would hit the second

38:36index two if I want 38 I would go and

38:40hit I would go and

38:43hit if I want 48 I would go and hit the

38:47fourth index if I want 38 I would go and

38:51hit the third index if I want 28 I would

38:54go and hit this Index this is the idea a

38:56kind of a imp impementation

38:59way you would have this all tricks and

39:02tips and

39:03tricks directly I can know that if let's

39:08say 48 is asked 48 is asked how far I

39:12need to go if let's say 48 is asked how

39:16far I need to go I can directly go and

39:18jump on the fourth index of where it is

39:20kept on eight but let's say if five8 are

39:25asked five8 are asked

39:28that is greater than the size of the

39:30eight so if that is greater than the

39:33size of the eight if five8 are asked and

39:36five indexes does

39:39not uh exist so we would report minus

39:42one

39:44so now we would build out the answer the

39:47very if we start processing the very

39:49first index we are told that zero so we

39:51would go and hit the first index of zero

39:54we would say that the value is z 0

39:59okay Zer is our answer then we want 28s

40:03so I would go and hit the second index

40:05so I want six so

40:08Maxim six index so the answer would be

40:13maximum the maximum index plus one that

40:15would make it seven that is why the

40:16answer is seven now let's process the

40:19next TR we want 3

40:231es 3 1es that is

40:26n 3 ones 6 ones six that is value is one

40:324 1es that value is two so out of 912

40:37which is the maximum that is 9 so 9 + 1

40:40is equal to 10 that is why the answer is

40:4210 ofus one

40:47see okay so we want one zero one0 the

40:51value of 1 Z is zero then we want 17 we

40:56go to 7

41:00okay we want

41:0217 but we don't have any elements here

41:0717 but we don't have any elements so if

41:11the number of plant asked is more than

41:14what we have if less than is more than

41:17what we have we would report minus one

41:20that is why we would report

41:23here how would we do it let me explain

41:26am I clear with this

41:31solution index and I know that the

41:34number of different characters would be

41:37just 0 to 9 that is 10 characters and

41:39this is also written in the

41:42question how to process

41:4728 how to process

41:5428 how to process 28

42:02if I want

42:032 I know that the second 8 is located in

42:07the second index so if I want 28 I would

42:11just go and directly pick up go to the

42:15second index of this

42:18one if I want 38 I would directly hit

42:21this how far I need to go eight

42:30element IND

42:33lar

42:35see this is just

42:37like the baj okay baj so my name is so

42:44just a little bit of story I would

42:45explain this so my name is ha so in my

42:50school days people used to like the baj

42:53crop is taught in the geography so in my

42:55school back on those School old days

42:57people used to make fun of me by calling

42:59me Bajaj okay so let's go back to this

43:02problem let's say I I have grown bajra

43:06and my father has grown bajra and he has

43:11he has like there is a strip of land so

43:16he has planted bazra on index zero on

43:20index 3 and index four and index five

43:23okay and index 9 so if I I want if my

43:29father wants if my father wants three

43:33bajas how far I need to

43:35go

43:37minimum I would directly go and see four

43:41and I would return this if my father has

43:44asked four five badas I would directly

43:47go and hit this so same kind of this is

43:50done if I

43:53want 6 28 I will directly go and hit the

44:00index location in the sorted manner so

44:04that

44:06minimum okay this is it do I make sense

44:09give me quick zero

44:14[Music]

44:16one we can just check the frequencies of

44:19characters using lower bound absolutely

44:22absolutely this is a very intuitive

44:25thing what we can do

44:27very

44:29intuitive but I think so people who

44:32don't know lower bound that would be an

44:50Overkill yeah huh I also thought of this

44:54am I clear with the solution give a

44:56quick one or zero at least there are 32

44:59people live here one or

45:08[Music]

45:12zero now let me show you the solution

45:15then I didn't receive any

45:18zero so I would move forward

45:27so what I did was I started

45:30iterating and I just inserted all the

45:33index I drew out a map like that okay

45:38then I

45:42counted this is just like counting

45:46crops then if the number of crops needed

45:50is more than what we have we would

45:53return minus one and we would break for

45:56this current Str else we would just go

46:00to that we would find that index add one

46:04to it because this is one index and that

46:06is zero index add one to it and the

46:08maximum of that would be my answer

46:11simple

46:13enough

46:15okay makes

46:17sense okay I did already read the

46:21Dy okay now let's move forward to the

46:24last problem sorry third last last

46:27problem so the second last

46:30problem okay

46:35so

46:42[Music]

46:48here now let us paste this

47:03okay now let me share

47:18this

47:21see it is

47:23told that at each point

47:27okay at each point we have a and

47:33b okay

47:36now

47:39if I jump on this I would get a points

47:44but I need to skip the next B

47:53indexes okay now

47:57see kind of this is not kind of this is

48:01that if I jump on

48:05this I would get

48:08three and I need to exclude the next two

48:13so next two

48:15exclude then I can make a jump to this

48:18again so if I jump here I would get two

48:21again and I need to exclude them so the

48:25value is equal to five this is how the

48:27value five is here I need to exclude

48:32okay first index would be my price and

48:34the next index would be the point where

48:36I need to the point where I need to

48:39exclude

48:41it okay fair enough now the point like

48:46what is basically asked in this

48:51like

48:54see the objective here is

49:01if I select

49:07a if I have a and

49:10b if I have a and b then if I get if I

49:15select this a I need to skip next B next

49:19B

49:25items if this value is good enough let's

49:28say this value is one lakh or something

49:32one lakh if this value is 1 L and it is

49:36telling me to ski all the items seems

49:39lucrative like let's say what I meant

49:44is let's say this value is 100 and it is

49:48telling me to skip five items and here

49:51we have one one one one one one like

49:55this

49:57so in this state like from

50:01here

50:03like from here it is very

50:07good to take a jump here and get this

50:10100 and Skip all the next

50:14five which we can focus

50:17is

50:19points if we can focus on points if the

50:22points are more then we can focus on

50:25them but

50:30why because let's say this value is

50:35three not three let's say this value is

50:39two if this value is two and we are

50:42focusing on points then I would take

50:45this two and Skip all the five

50:48items I would take this two and Skip all

50:51the five items because two point I would

50:55take this two but if you see this

50:57closely taking a jump of this this this

51:01is

51:03three okay taking a jump of this and

51:07this is more

51:09beneficial is more

51:11beneficial what I meant

51:14is taking this path that

51:17is selecting this going

51:21out the total point is two but instead

51:26of that what we we can do is we can take

51:27a jump here we can take a jump here then

51:29we can take a jump

51:31here so now you can see that you can't

51:34really decide where we need to

51:38focus okay

51:40kab sometimes less

51:44points would sum up together and give

51:47you more value or sometimes more points

51:51would give you more

51:53value than sum of all the rest of the

52:11whenever you are in the middle of this

52:14confusion or kashmakash whenever you

52:16can't really decide what to do then like

52:22when I when I can't decide like let's

52:24say I can't decide

52:27if let's say I want to do like what what

52:29is the general agenda of human mankind

52:32IND when a person who is very good in

52:35studies and he can't really decide to go

52:39between medical or engineering and he

52:41likes both of them equally like some he

52:45he's not he's confused then for the time

52:48being he would take PCM and PCB there

52:51were some students in my bch so math

52:55like biology or maths don't

52:58so they are trying out all possible

53:03ways and you are trying you need to try

53:06out both the ways this just boils down

53:08to the conclusion that try

53:14all possible

53:16ways or be you come to the conclusion

53:20that you need to try all possible ways

53:23try all possible ways just Narrows down

53:25to recursion

53:28recursion has a very high time

53:30complexity how to lower it down that is

53:33just memorize it and that then do

53:35dynamic programming add add two lines to

53:38it it would become optimized and you

53:40would be able to fly with

53:42these now you would ask me that how to

53:45build up a requested Solution that's

53:48true so now let us talk about how to

53:52build up this recursive solution yes I'm

53:55good enough

53:58okay how to see this what how to build

54:00up this recursive

54:04solution top down bottom

54:07up

54:10okay

54:14see first in the recursion what are the

54:17two things that we have we have base

54:20case and then we have the recursive case

54:25let's talk about the B base case the

54:27base case is the smallest case that you

54:31can solve by yourself so sub smallest

54:36case when we don't have any

54:39elements when we don't have any elements

54:42we would just return

54:44zero but if you have some

54:47elements but if you have some elements

54:51what are the two things I

54:53can the two things I can do is is the

54:57two things I can do is what I can

55:03do what I can do I can consider that

55:10index I can consider that point and Skip

55:13next five next consecutive points I can

55:16consider a points and Skip B

55:19positions and I can just move forward I

55:23can just move

55:27so if I consider if I consider let's

55:31talk about first consider if I consider

55:34it okay if I consider it then I would

55:39add EI points to my answer and I would

55:44go to the next B index and my next index

55:48would start from I + B of

55:52I I would skip B indexes if I don't

55:56consider it I would simply move forward

55:59that is my

56:02like my score would remain the same my

56:06score won't increase here the score

56:07would

56:08increase score plus a ofi here the score

56:11would increase here the score would

56:13remain the same and only I would move to

56:16I + one that is I won't consider this

56:19one let go

56:23skip my score would remain the same

56:27consider so the score would increase and

56:30I would skip B

56:33index fair enough it let's implement

56:37this and then we will talk about how to

56:39memorize it in the most easiest way but

56:42it

56:46cont am I clear with the solution just

56:49give me a quick one or

56:51zero up the idea is very simple if we

56:55don't have anything we would return

56:59zero okay now you can ignore this at

57:02this point just ignore that now

57:05answer maximum the very first one is we

57:09can directly just move forward and the

57:12score would remain the same just move

57:14forward the next option

57:18is I need to add a of I to my answer and

57:25I need need to skip the next few

57:29indexes so I would skip few indexes and

57:33I would score a ofi to my answer and

57:37this is a simple recursive code this is

57:40the given solution and simple

57:47recursion this is the

57:50solution this is the solution just add

57:53three lines this is the solution just

57:56four liner

58:00solution this is recursion you would get

58:03a time limit exceeded if you do this

58:06okay just add three lines and that would

58:10be done now you would ask me sidhar how

58:13to memorize it in the best possible

58:15manner memorize don't need to think more

58:19what are the

58:22parameters what are the dynamic

58:25parameters

58:28technical what are the dynamic

58:30parameters If You observe I is changing

58:33here I is I + 1 here is I is I plus

58:37something else the given array Remains

58:39the Same the size of the array Remains

58:42the Same and the DPR is just to store

58:44the answer so we can see only I is

58:47changing so what is the lowest value of

58:49I so I would start from zero and if I is

58:54greater than n we would hit the base

58:56case so I need to memorize 0 to n minus1

59:00so I can declare an array of size n and

59:03initialize it with minus1 so just look

59:06there is nothing so I would say that

59:10whosoever is saying 2D 3D DP and 2D DP

59:14in different scenarios this is a myth

59:17the number of dynamic parameters would

59:19tell you the dimension of the dynamic

59:22dynamic problem solution number of

59:25dynamic the way to memorize in the best

59:27possible manner is find out the number

59:30of dynamic parameters then declare an

59:33array or a map of that Dimension and

59:36then just memorize it simple

59:39enough 2D DP

59:423dp comp DP is just a

59:48icing just a decoration over recursion

59:52okay I am clear with this give me a

59:54quick one or zero

01:00:01take not take this is just I can say

01:00:04napsack one now we would move forward to

01:00:06the last

01:00:08problem give me a quick zero or

01:00:24one e

01:01:13okay uh I Amo usually starting from the

01:01:16base case and building on it easier than

01:01:18finding recursive function

01:01:22memorizing finding reive function

01:01:24memorizing

01:01:26personal

01:01:28choice on who learned what earlier and

01:01:31better um I think if you know dynamic

01:01:34programming the very first problem you

01:01:36would solve are some Fibonacci series

01:01:38and then 01 napse if you have solved 01

01:01:40napse this is just a take on on Take so

01:01:43t let just

01:01:49see let's just F comp

01:01:59working

01:02:02successfully no issues let's go to the

01:02:05very last

01:02:07problem

01:02:09Ma trust me this is

01:02:12amazing okay this is just

01:02:17amazing okay can you explain the last

01:02:21condition added con the last

01:02:24condition just mention the line number

01:02:27and if I just tell you

01:02:29explicitly I would deserve a comment

01:02:32from your side Kumar just tell me the

01:02:36line number at which you are asking we

01:02:38would

01:02:39wait 30 seconds for

01:02:45you just see it and then tell

01:02:51me S if just check it on your side that

01:02:56is more

01:02:58feasible Anil Kumar just tell me the

01:03:00line number quickly

01:03:05bat there's nothing as last I can't

01:03:08really

01:03:11move I think he is gone or

01:03:16something okay I think he is gone so

01:03:19let's move forward okay so now see

01:03:26this is a good enough

01:03:50problem line number

01:03:5345 yeah line number 45

01:03:56if DP is not equal to minus one yeah

01:03:59okay so see initially I just this is a

01:04:02part of the

01:04:03memorization so I will just give you a

01:04:06brief and then you can talk about

01:04:09see I'm saving the answer of recursion

01:04:12with minus

01:04:14oneus

01:04:15oneus that means the answer is not

01:04:17calculated and we are moving forward but

01:04:20if there is no minus one that means the

01:04:23answer is calculated and kept there so I

01:04:25return that so you can these this this

01:04:29line this line and this line learn about

01:04:33memorization a bit and you would

01:04:35understand this tell me a problem in

01:04:39these lines because this is main work

01:04:44around

01:04:47okay now

01:04:49see

01:04:50so this is a complex level problem I

01:04:55must

01:04:56say okay this is a complex problem that

01:05:01we need to handle today okay Maz trust

01:05:06me it's

01:05:07amazing okay now

01:05:16see here the problem statement won't

01:05:20really be of much use because they are

01:05:22very small and they can't like they

01:05:26can't contribute to the

01:05:31explanation so so I would assume

01:05:34that you understood the problems they're

01:05:37like sample test case because they way

01:05:40too

01:05:41easy okay so let us understand what is

01:05:45asked in

01:05:48this up there am I sharing the screen

01:06:01I

01:06:02deserve a comment from you Anil Kumar so

01:06:07see let's talk about this problem by the

01:06:10way I have already seen up this problem

01:06:13somewhere okay that's why this was very

01:06:15evident to me so what this problem tells

01:06:18us this is telling

01:06:21us to find all the pair of I and J all

01:06:27the pair of I and J where I is less than

01:06:31J on which this condition is true that

01:06:36is a of

01:06:39I and with a of

01:06:44J and with a of

01:06:48I plus a of

01:06:54J that is okay Special Operation and we

01:06:59need to just consider all the indexes

01:07:02and add their value okay like need to do

01:07:05this on all in and contribute them to

01:07:09the

01:07:10answer

01:07:12okay of the thinking process of this see

01:07:16what we can the basic Brute Force

01:07:18application is that we would consider

01:07:20all I and J we would sit on all I and

01:07:24iterate over all J by the way for the

01:07:27people who are coming to the fourth

01:07:29problem I'm assuming that there are

01:07:31coders of like a little bit above

01:07:35beginner level okay

01:07:38because I won't really explain I would

01:07:42assume that you already know the

01:07:44properties of and you already know

01:07:47simple simple things okay you already

01:07:50know what do you mean by modul 10^ 9 +

01:07:537 like modular arithmetic that is A + B

01:07:57whole modu M isal to a module m b modu m

01:08:00plus whole module M you know all this I

01:08:02would assume okay now if you don't know

01:08:05you can just learn about this and then

01:08:08come back to this video here I would

01:08:10assume that you know modu arithmetic you

01:08:12know the properties of and then you are

01:08:14trying to solve up this problem okay now

01:08:18if you don't know I would suggest not to

01:08:19solve this problem else your motivation

01:08:21would go a little bit on the lowest side

01:08:24if you know

01:08:26of let's say level 10 and you're trying

01:08:27to solve level 100 then you realize that

01:08:29you have you don't know anything and

01:08:31then you get

01:08:32demotivated this is a personal choice

01:08:34you can do it whatever you want let's

01:08:36move forward to this

01:08:39up the very first simple solution is I

01:08:41can consider all I and J's give up the

01:08:44sum and return it but that won't really

01:08:46serve the purpose why because there are

01:08:4810 the^ 5 elements and that would be an

01:08:51N Square operation so 10 the^ 5

01:08:53multiplied by 10 the^ 5 is greater than

01:08:5610 The Power 8 so you would get a t that

01:08:58is time limit

01:09:05exceeded I would assume I would assume

01:09:08that you already know this narrative

01:09:12okay now let's move

01:09:14forward now let's see see the point

01:09:17is that

01:09:20if if you want to do a n Square

01:09:24operation that is you need to take hold

01:09:27of a and you need to find all the

01:09:30respective B's for it you need to take

01:09:33hold of I and you need to iterate over

01:09:36all the GS for

01:09:37it okay and you need to facilitate that

01:09:41if you want this if you want

01:09:45this then I would say in any bit

01:09:48manipulation

01:09:50question in any bit manipulation where

01:09:53for I you need to process

01:09:56the next whole array like it is told

01:09:58that for give the value of I I and with

01:10:03all the values of the next if this kind

01:10:07of thing

01:10:10is next element

01:10:14element if this thing is asked the most

01:10:17simplest thing you can do

01:10:19is you need to

01:10:22think in

01:10:26terms of

01:10:29bit you need to think in terms of

01:10:38bit what s wants to say here let's see

01:10:43this let's say the very first sample

01:10:46test case here is

01:10:4917 and

01:10:51seven

01:10:53okay the value here is

01:11:00six okay so see so the binary

01:11:04representation of one here would be just

01:11:07one okay let's change the color the

01:11:10binary representation of one here is

01:11:12just

01:11:14one the binary representation of 8 is

01:11:17that is 8 - 1 is equal to s that

01:11:23one11 okay right the is 4 + 2 + 1 same

01:11:30goes for

01:11:32this and this would be 0 0 0

01:11:36comparatively the calculation is

01:11:38becoming easy how let's

01:11:43see

01:11:45for one I would just see the

01:11:47contribution of this bet first so I

01:11:52would say this one when clubbed with

01:11:54this one one and

01:11:57one so one and one

01:12:02and with

01:12:07what one and with one and one with 1 + 1

01:12:14that is 2 okay so 1

01:12:19Z that would make it what that would

01:12:22make it zero

01:12:26okay if one one is

01:12:28done if next one and one is

01:12:32done again we would have zero so this

01:12:36would

01:12:37contribute zero to our

01:12:40answer

01:12:42okay how because 1 + 1 this is what this

01:12:46is the summation of these two so 1 + 1

01:12:50would make it the this would make it two

01:12:54that is zero

01:12:56okay fair enough this would contribute

01:12:58zero to the answer the very next one

01:13:01let's talk about the very 011 so

01:13:05zero okay

01:13:08zero this is one 0 and 0 and0 is

01:13:15something okay so 0 and one is not

01:13:19really matching

01:13:22okay so now

01:13:26so just take that take out that bit so

01:13:29see this is if we take out the middle

01:13:33bit that is 0 0 0 if we just keep the

01:13:37middle bit

01:13:39in Middle bit intact that

01:13:43is if I just take out the middle

01:13:47bit okay this one would be

01:13:51one like I'm just taking out the middle

01:13:54bit

01:13:55so now I need to do and between all of

01:13:58this to get the contribution of the

01:14:01second bit so I can just remove the

01:14:04upper

01:14:05bits okay now

01:14:09see one and withth okay let's do this

01:14:14thing 0 0 0

01:14:180 and with 1 Z and with 0 0 like we are

01:14:26Computing this one so 0

01:14:300

01:14:32okay 1 0 and 0 0 this would be Zer and

01:14:37this would be

01:14:391 okay so this would again

01:14:43become 1 Z so that's why the value would

01:14:47be zero again then again with this the

01:14:51value would be zero again now let us

01:14:53consider

01:14:591

01:15:00Z and with 1 Z and

01:15:07with 1

01:15:110 and 1 0 is zero and this would be two

01:15:16that would make it 1 0 0 1 0

01:15:210 so as a ky what we can really do is we

01:15:24can

01:15:26compute the and with like sorry

01:15:30and okay like we would find the

01:15:35contribution of the last bit find the

01:15:38contribution of each of the bits

01:15:40separately find the contribution of each

01:15:44of the bets

01:15:46separately is

01:15:49contribution

01:15:50contribution

01:15:53contribution we have this

01:15:56okay the idea is to find the

01:15:58contribution of the bits in different

01:16:02different

01:16:03ARS

01:16:06okay first just tell me if this idea is

01:16:09clear or

01:16:12not find the contribution of each bit to

01:16:15make up the

01:16:19answer I can't really check your code y

01:16:21hack V hack because if you send the code

01:16:25here I won't it won't get displayed like

01:16:27if You observe like uh YouTube algorithm

01:16:31doesn't really allows sending codes in

01:16:33the chat okay it won't really

01:16:38detect okay just a little bit quick

01:16:58now that we need to compute each of this

01:17:01bit

01:17:03separately okay each of the bits go

01:17:06separately

01:17:08manage okay like we would come to the

01:17:10very first bit but

01:17:14still

01:17:16combin like

01:17:18see we are talking about the last bit

01:17:22okay so first we need to see the this

01:17:25with this again this with this then we

01:17:27need to see this with this so we are

01:17:30again doing n Square operation for each

01:17:33of the bits okay this is just

01:17:36like like let's say number of the values

01:17:39are 10 the^ 5 so around 30 bits would be

01:17:42there so 30 times you would be doing the

01:17:46same n Square

01:17:49operation we would need to do the same

01:17:52thing now so now we need to to optimize

01:17:56this per bit one per bit operation one

01:18:00okay a per bit operation thing

01:18:08optim if we have something like the

01:18:12second bit is

01:18:13set the second bit is set so for anyone

01:18:19whose value is one second bit is set

01:18:23that value would be

01:18:25second bit is

01:18:28set like

01:18:31five

01:18:334 and 9 5 4 five and four so the binary

01:18:39representation of five would be 1 0 1

01:18:44and four for four the B

01:18:47representation would

01:18:50be the four the binary representation

01:18:52would be 1 0 0

01:18:56okay and if I add both of them and then

01:19:00do the binary

01:19:01representation for 9 the value would be

01:19:05what the value would

01:19:10be the value would be 8 + 1 that is

01:19:14something like this that is 1 0 0

01:19:191 so the answer to this would be zero If

01:19:22You observe

01:19:25okay 5 + 5 and with four and then and

01:19:30with 9 let us prove this let I just

01:19:34check

01:19:35this five and

01:19:38with five five and with five and with

01:19:439 it is equal to

01:19:471 5 that is

01:19:52five okay 5 + 4

01:20:05sorry okay I just took this this is

01:20:08eight this is just nothing other than 8

01:20:11+ 1 okay so this value would be 5 + 4 +

01:20:181 five and withd so this value would be

01:20:22one

01:20:25so 2^ 0 let's take some different

01:20:31example okay

01:20:33[Music]

01:20:34so we would have let's take the example

01:20:37one only 7 and seven 7 and

01:20:43seven

01:20:45take 7 7 so the binary representation of

01:20:51seven is how much

01:20:562 ^ 0 + 2 The Power 1 + 2 ^ 2 this is

01:21:01the binary representation of 7 this is

01:21:04again the binary representation of 7 of

01:21:087 + 7 because a and with b and then and

01:21:14with A+ B so and with A+ B that is the

01:21:19binary representation of 14 the binary

01:21:22representation of 14 would be

01:21:258 then then 8 + 4 + 2 so 8 + 4 + 2 so

01:21:368 +

01:21:394 + 2 so this would be the binary

01:21:44present 1 1 1 0 I would just check this

01:21:46please I'm sorry but I would just check

01:21:49this binary representation

01:21:54binary representation online I would

01:21:57just check this

01:22:05please convert binary to decimal decimal

01:22:08to

01:22:09Binary

01:22:1914

01:22:21110 say but

01:22:25doake over I'm doing this every

01:22:32day up

01:22:35see up the magic

01:22:38here so I can observe that this would

01:22:43make it as one this would make it as one

01:22:46that is why the value is 4 + 2 that is

01:22:49Zer that is six the answer is

01:22:52six but why is this value

01:22:55one okay why is this when a value would

01:22:58be contri when a value would contribute

01:23:00when a value won't

01:23:02contribute okay so see small

01:23:09observation or

01:23:11one okay so

01:23:16one if this is

01:23:18[Music]

01:23:21one these two are one

01:23:24one is getting contributed these two are

01:23:27also one but here zero is getting

01:23:29contributed be one one so how do we know

01:23:33when it would be a zero when it would be

01:23:35a

01:23:36one when it would be a zero when it

01:23:39would be a

01:23:45Oney suppose I want to know without

01:23:48adding I want to know if that would be

01:23:51zero or one so they here the trick Lies

01:23:55over here let's talk about this one if I

01:23:58talk about this one this would be

01:24:00something like this 1 0 here this would

01:24:03also be 1 0

01:24:070 okay if this value is 1 0

01:24:120 okay if this value is 1 0 0 this is 1

01:24:190

01:24:200 okay this value is z this value is

01:24:23zero this value would become two so that

01:24:25would be that would that is

01:24:28this this is

01:24:32what this value is

01:24:35[Music]

01:24:371 1 okay one and one because your last

01:24:43bet okay this is also

01:24:48zero same but still add Z add one

01:24:56okay bit by bit

01:25:00contribution how would you find the bit

01:25:02bybit contribution of

01:25:04them how would you find

01:25:08it the bit by bit contribution the bit

01:25:12by bit contribution can be found out by

01:25:17doing

01:25:18this

01:25:21whenever like am I clear to this point

01:25:24what is is the

01:25:27[Music]

01:25:37objective two are one and the last one

01:25:39would also become

01:25:40one so last one one this if everyone is

01:25:45one then only we would get a one

01:25:48according to bit manipulation if

01:25:50everyone is not one we would get a zero

01:25:52according to bit manipulation

01:25:55by how would I know it without them

01:25:59adding and

01:26:09thenen I don't really know that first

01:26:12tell me if I know what is the objective

01:26:14or not

01:26:25okay screen was

01:26:30not

01:26:38damn

01:26:42okay okay let give me a

01:26:48man I'm doing it again all over again

01:26:50like I would have the fresh just give me

01:26:52a minute

01:27:07[Music]

01:27:22tough day at work

01:27:43give me a few seconds just let me read

01:27:45the chats

01:28:08just let me see the

01:28:15chat have to start again as screen was

01:28:18not visible take I would start again

01:28:21just give me 2 minutes I'll just read

01:28:23out the chats previous

01:28:27chats damn I'm still seeing

01:28:31this I'm still seeing

01:28:34ads I think I should

01:28:36buy premium or something

01:29:16chill

01:29:27yes my screen is visible

01:29:34now okay now see

01:29:40this the very first idea

01:29:55so I would just go through it so now the

01:29:58idea is that you need to do this you

01:30:03need to what you need basically need to

01:30:05do

01:30:07is you need to have I and J you need to

01:30:10find all like you need to consider all I

01:30:12and J and then give out the

01:30:14result but you would need n Square

01:30:17operation and N Square won't really help

01:30:20because 10 ^ 5 * 10 the^ 5 is equal to

01:30:2410 the^ 10 which is greater than 10 the^

01:30:278 so this would get a time limit

01:30:29exceeded so this is a bit problem and

01:30:34for one element you need to process all

01:30:37the rest of the

01:30:39elements then what I say is process in

01:30:41terms of bits process in terms of

01:30:45bits but

01:30:52bit then for each of the bit like let's

01:30:55say this is a b c d e let's say these

01:30:59are all the bits then I need to again

01:31:02see if this is working with this this is

01:31:04working with this this is working with

01:31:06this this is working with this the very

01:31:08next one is this is working with this

01:31:09this is working with this basically I

01:31:12need to again process

01:31:14nc2

01:31:16pairs I need to again process nc2

01:31:21pairs so this is again big off n square

01:31:25but wait there is a small catch in

01:31:30this okay the small the small catch is

01:31:35the small catch

01:31:38is the very small catch here is If You

01:31:43observe

01:31:45M

01:31:48yes

01:31:50okay I think yes D was the person who

01:31:53was knocking the

01:31:55door okay very small catch here

01:32:07is okay the very small catch here

01:32:12is that if you have something

01:32:15like 1 0 1 and if you have 1 0

01:32:220 okay okay so if I want to know that if

01:32:27this bit would contribute in the answer

01:32:29or not why

01:32:32because these two and the sum of them

01:32:35should also be

01:32:40one

01:32:41one okay may answer

01:32:44one so now see this is equal to 1 this

01:32:49is equal to

01:32:51Z and if this value is just just one one

01:32:55this would become one Z so see this is

01:32:59not we are not able to contribute to the

01:33:01answer this is not able to contribute to

01:33:04the answer

01:33:05zero okay contribute see one one if

01:33:11something like here

01:33:14as

01:33:17this contribute see for this bit if I

01:33:21want to know if this would contribute

01:33:23for this bit or not

01:33:24then see I would just add the bits one

01:33:26one this would become I would just carry

01:33:28it this would become zero I would again

01:33:32this is becoming three so I would become

01:33:34this so see

01:33:36now this bit if I want to know if this

01:33:39bit is contributing or

01:33:42not this bit would only

01:33:44contribute If the previous values give a

01:33:48carry to

01:33:51itry see to make to make one and one and

01:33:57the sum of them is also one one one or

01:34:00sum be

01:34:08one let say this is a and this is

01:34:11B set B set or some may this should be

01:34:16set then only it would contribute to the

01:34:18answer I know that so now if You observe

01:34:22even though these two bit are set you

01:34:24can see the sum of them is now

01:34:26contributing but here these two bit are

01:34:29set but in the sum in after the sum this

01:34:32is not contributing so this would become

01:34:36zero when it contribute to the sum when

01:34:39this would not contribute to the sum now

01:34:42let us see some more examples they what

01:34:45I meant to say is even though this is

01:34:51one so if this is value is

01:34:55one this value is one and this value is

01:34:59one one then see this won't contribute

01:35:02why this is becoming one Zer this would

01:35:05become okay 1 one this would become

01:35:10two okay this will become three okay so

01:35:13this is this

01:35:16so This

01:35:21contributed okay whenever this is

01:35:28carried this would contribute something

01:35:31if I just make this as

01:35:33110 and this as

01:35:36one1 see now this bit won't contribute

01:35:40this is one this is again one and this

01:35:44is one Z so see Zero

01:35:47contribute so when will the bit

01:35:50contribute the bit would contribute in

01:35:54two condition the bit would be

01:35:57contributed when for both of them this

01:35:59bit is turned on for both A and B this

01:36:05bit is turned on so A and B turn

01:36:11on next what is the next what is the

01:36:14next sorry

01:36:17[Music]

01:36:26what is the next step of the next step

01:36:30is you would observe that

01:36:33whenever this

01:36:35value is greater

01:36:38than greater than see

01:36:44previous 0 like 0 and 1 is greater

01:36:49than or equal to 2 to the power 1

01:36:55these all values are not greater than

01:36:59are not greater than equal to 2 to the^

01:37:031

01:37:05okay okay greater than okay this is

01:37:09greater than this is let two this is one

01:37:12this is not greater than this is greater

01:37:14than this is

01:37:16three be three this would contribute two

01:37:20this is not able to contribute

01:37:25so this whenever the for the I index A

01:37:29and B is for the like for a and b when

01:37:33the I bit is turned down and it is

01:37:37greater than equal to 2 The Power I -1

01:37:43it is greater than equal to 2 the^ IUS 1

01:37:47they would contribute to our

01:37:51answer okay now

01:37:54a

01:37:56point so what we would do is we would

01:38:01just keep them in

01:38:03a 2d like twoo like we would now do the

01:38:07two- pointer thing so if this and this

01:38:12if

01:38:14the

01:38:17two okay when the sum is greater than

01:38:19two so we have now this is just like

01:38:23two- pointer approach where we keep Ln R

01:38:26so whenever Ln R whenever the sum is

01:38:31less than 2 The Power i-

01:38:351 okay then we would what we should

01:38:40do okay lnr so if we want to increase

01:38:44the sum of lnr we need to move forward

01:38:48the

01:38:49L if it is more than 2^ IUS

01:38:53one if it is more than we first include

01:38:57it to our

01:38:59answer and then we would move make that

01:39:03R go minus

01:39:06minus okay so we would sort the values

01:39:09and then we would find this so let me

01:39:11just show you this two pointer

01:39:13implementation because that is the most

01:39:14confusing

01:39:20part okay so now

01:39:25helper function we would make lnr here

01:39:30okay 2 The Power

01:39:33I that would contribute to the sum so

01:39:37that is 2 The Power I that is

01:39:39contributing to the sum so rest + IUS

01:39:43L and mod of else we would increase the

01:39:47sum by going this side we want 2 to the

01:39:50power I

01:39:52greater then only the sum of them the

01:39:56sum of them would also be equal to

01:40:13one 1 1 and 1 1

01:40:200 that won't really contribute like see

01:40:23this bit won't contribute like if I want

01:40:25to check if this bit would contribute or

01:40:27not that is the second bit would

01:40:29contribute or not that they won't

01:40:31contribute to the answer why

01:40:34because one and with one and with some

01:40:38of them so some of them is what one and

01:40:40one one 0o and one one and this is two

01:40:44that would make it zero and here it

01:40:46would come one so this won't contribute

01:40:48to the answer so one and one and 1 0 is

01:40:51equals to zero but when it would

01:40:54contribute whenever we have a condition

01:40:57like

01:40:58this one

01:41:01one and let's say this is

01:41:04zero one and one two so be whenever we

01:41:09have this carry

01:41:11thing it would contribute to the

01:41:14answer and when we would have this carry

01:41:17condition

01:41:20whenever I I say come

01:41:23is greater than or equal to 2 power

01:41:27I 2 power

01:41:30I then it would give you a carry to

01:41:35this okay so 2 to the power

01:41:41I I

01:41:45IUS this part should be greater than 2

01:41:47The Power I so to make it Greater what

01:41:49I'm doing is I'm taking all the values

01:41:53in that segment which are turned on I'm

01:41:56taking all the values which are turned

01:41:58on let's say this is 1 0 0 this is

01:42:01one 1 one one and this is one 0 0 again

01:42:07I'm taking all the bits and then I'm

01:42:09sorting

01:42:11it now after

01:42:14sorting if this and this is less than

01:42:19left over values left over

01:42:21Valu if the left it if it is less than

01:42:25left over values that is 2 the^ IUS 1

01:42:29then we would increase

01:42:31this if that is more we would come here

01:42:35to decrease the value

01:42:38okay I would explain the solution now it

01:42:40would get more you would understand it

01:42:43more we would consider 30 bits if for

01:42:47the current element the bit is turned

01:42:50on we would just insert them in a vector

01:42:55then we would sort that Vector so that

01:42:57we can do two pointers over it okay then

01:43:01we are sending it to a function a

01:43:04function what does this function see we

01:43:06are just doing two pointers over here if

01:43:09lnr plus is like what we want is we want

01:43:13lnr l+ R we want to find all l+ R

01:43:17greater than 2 to the power I if that

01:43:19value is greater than 2 to the power I

01:43:21we would add the value and and we would

01:43:23do R minus minus if that is less we

01:43:26would do

01:43:27l++ if that is greater than equal to we

01:43:30would include that to our answer it's

01:43:32just like the contribution of each bit

01:43:36with the fusion of two pointers

01:43:39comparatively a very complex problem but

01:43:42if you know bit masking and if you

01:43:44understand and the fuse together then

01:43:46only you would understand this that's it

01:43:48for today tell me the point where you

01:43:51are not able to understand this is the

01:43:52solu

01:43:56I've got it anyone who has not got it

01:43:58satjit Kumar tell

01:44:16me

01:44:19see this is the reality you should

01:44:22upgrade yourself to understand the last

01:44:27one for for the the bit manipulation

01:44:30part is clear but the transition point

01:44:32to point poins for

01:44:35Less okay I would give you a hint

01:44:40say the objective

01:44:45is then you learn two points and then

01:44:47come back to this video

01:44:50they don't bit turn

01:44:56[Music]

01:45:16okay car

01:45:18forward forward 1 + 1 plus one

01:45:26this becomes three that is one one

01:45:29so I would let me

01:45:37explain okay now see the point is I

01:45:43would see the contribution of all of

01:45:44them okay this is one this is one okay

01:45:50this would only contribute to the answer

01:45:53if let's say this

01:45:55is so if I want to know for this 1 Z

01:46:00and 1 Z this would only contribute to

01:46:04the answer if we have overflowing one

01:46:06from this side when will this one

01:46:09overflow if this value is greater than

01:46:14if this value is I is greater than 2

01:46:17power IUS

01:46:23and that would make it more sense let me

01:46:26give you example

01:46:28See Seven and Seven okay 7 and 7even is

01:46:32what 1 1

01:46:361 1 1

01:46:391 if I want to know if this bit would

01:46:42contribute to the answer or not I would

01:46:45just see these two

01:46:46bits these two bits this is 0 1 two so

01:46:51if these two bits are greater than equal

01:46:54to 2 to the^ 1 because this is the

01:46:57second bit so previous bit is this so if

01:47:00this bit is greater than 2 to the power

01:47:021 then only we would have a carry

01:47:04forward of one and then this would

01:47:06become one so now we know whenever for A

01:47:10and

01:47:11B and we want to know for the I bit if

01:47:15for A and B if it is greater than 2 to

01:47:17the power IUS one then we it would be

01:47:21considered in the answer of how this

01:47:24transition of low pointers became a

01:47:26solution we have something like a b c d

01:47:32e okay now if this and this if let's say

01:47:38these

01:47:39both if it

01:47:43is and these are all in the sorted form

01:47:46if that is less

01:47:48than is less than 2 power I and they

01:47:51didn't contribute

01:47:53this didn't contribute if let's say A

01:47:56Plus e if let's say

01:47:58a + e

01:48:02is the value is less than 2 to the^ I

01:48:05and they are not contributing so now I

01:48:07want to make it more so that they would

01:48:09contribute to make it more I need to

01:48:13make this pointer go on this side then B

01:48:16and E would have better sum and in there

01:48:20that would be more than 2 to the power I

01:48:24and

01:48:25if these two are greater than 2 the^ I

01:48:30then these all B with c b with D and B

01:48:34with e all will have 2 to the power I

01:48:39greater okay sorry I just drew the

01:48:43opposite one

01:48:44sorry AG B or C mil a 2 The Power I

01:48:49say then C with e would also have the

01:48:51sum greater than 2 The Power i d with e

01:48:54would also have the sum greater than 2

01:48:56the^ I say screen is

01:48:59visible so that is the point whenever we

01:49:02hit that it is greater than 2 the^ I we

01:49:05add R Rus L whenever it is less than 2

01:49:11to the power

01:49:12I whenever it is less than 2 to the

01:49:15power I we make this go to we make this

01:49:19go to this side that is

01:49:21l++ okay this would give me all the

01:49:25combinations so the explanation is

01:49:28simple if this is a sorted

01:49:31array and this value and this value have

01:49:342 to the^ I greater then this would also

01:49:37have with this this would also have with

01:49:39this e I'm just adding that so that we

01:49:42don't need to find our answer this is

01:49:45just

01:49:48like find all pair

01:49:55with some greater

01:49:58than greater than n or

01:50:02something count pairs with the given sum

01:50:05count P count number of pairs greater or

01:50:09equal to the greater Target given a

01:50:12sorted array find all the pairs which

01:50:14are some greater than equal to

01:50:18this yes I found this question somewhere

01:50:22in a forces

01:50:25blob now am I clear to to some kind of

01:50:30yes so now am I clear with the

01:50:33solution give me a quick yes or

01:50:36no am I clear I know this is kind of

01:50:40that

01:50:41intuition problem now give me a zero or

01:50:44one please I did a lot of hard work at

01:50:46least I want to know what is

01:50:51the what is the solution like what is

01:50:54the end end part of

01:50:57this it's clear for anyone whom it is

01:51:00not clear tell me this like you know two

01:51:04pointers to this extent you know bit

01:51:05manipulation to this extent you are you

01:51:08think you are well equipped but you

01:51:09didn't understand the solution tell me

01:51:11that anyone who thinks there is give me

01:51:13a zero I would take that as a feedback

01:51:15and improve it in the next discussion

01:51:18but

01:51:27make sense no one so that's it for today

01:51:32I did a lot of hard work to explain you

01:51:35this okay like the last problem was a

01:51:38very kind of a tough problem and I still

01:51:43try to connect all the

01:51:46dots okay okay fair enough so that's it

01:51:51for today if you liked up the Stream or

01:51:53if you were here till this point

01:51:54consider liking the video and leaving a

01:51:56comment on this and if you're watching

01:51:58the stream in the recquired version feel

01:52:00free to comment on this video so that I

01:52:02would be encouraged and I would be

01:52:04digging up the session more that's it

01:52:06for today thank you

ðŸŽ¥ Related Videos

ðŸ”¥ Recently Summarized Examples