Understanding Vectors and Their Applications

Hi everyone and welcome to the complete DSA series in which today we are going to study about vectors. If you want to study any other concept in DSA, then it will be available on this channel in this playlist. If we want, we can go from here and study. So let's start talking about vectors. Vectors are basically our next data structure which we will study in detail in today's chapter. And this data structure is very array-like. When we visualize an array, it looks like an array with different blocks in it, which we store data in. And we also have indices and indexes like arrays. So, this is how we visualize our vector. What are vectors? They are dynamic in nature. Dynamic in nature means that they do not have a fixed size. Their size can change. This is a major difference between arrays and vectors. Now before reading vectors, we should know one important thing which is STL. STL is Standard Template Library of C++. STL is basically a library, we can imagine it as a toolbox, in which the implementation code of many data structures is already written. Many of our data structures like stack, hash table, queue, and many other data structures. They have to be implemented from scratch in any programming language. But whenever we are in an interview for placement, internship, coding test, we have limited time. So we cannot implement all these data structures from scratch to solve a single question. So in STL, in this library, their implementation has already been written. So we directly pick these data structures from this library as a tool. And then we use that tool to solve our question. So the implementation of vector is written in this library and we just have to use vectors directly to solve our questions. Now how the vectors are implemented internally, we will discuss that in this chapter also. So it is not like we will skip an important part. We will discuss that implementation also but usage is more important. Now using STL is allowed in placements and interviews. So we are not doing anything that we are taking out a lot of shortcuts. We solve our questions using STL only in DSA. And in this same STL we have many tools, one of which is vector. So we take the vector tool and we have to directly implement it, that is, we start making different vectors for ourselves. And in STL, the vector that happens, we will read Q in the future, we will read stack in the future, we will read set in the future and we will read different data structures. So all these data structures are called STL containers. Containers means that these are containers to store some kind of data. So first of all let's talk about our first STL container which is a vector. Now we have already discussed the vector, we imagine it as an array. But inside the array, the size is fixed. So if we have made an array to store information of 100 students, then if tomorrow there are 1000 students, then we will not be able to use this array. So to solve this problem, we have vectors and vectors are dynamically resized after implementation. If we want, we can increase the size of our vector in memory. There are different syntaxes to create vectors. The first syntax is this. We write vector. then in angular brackets we write type of the vector, that what type will be stored in it, then we tell the name of our vector. So, in this way we can declare a vector for ourselves. So, let's come to the code once, and in the code we create a vector of integers, which we have named vec. Now, when we create a vector in this way, first of all, the size of this vector will be equal to zero. Why? Because there is no element stored in it, so by default this vector is of size zero. Also, when we create a vector, we will get an error. The error is because to create vectors, we have to include our vector header file. If we don't include this header file, we will get an error. Because what is vector? Where is its implementation? The implementation of vector is written in STL and that is why we have to include this header file. Now, you might have noticed online that instead of this file, what do people do? dot h, in many places you must have seen this header file including many students. Now this header file, students include this header file to solve questions on many coding platforms. But I will not advise you to include this. Why? Because generally in interviews you can be asked which header file is of individual vector and which header file is of other data structure so we should have that knowledge plus because we are starting in C++ and learning data structures for the first time so we should have an idea of which header file is of which data structure and generally in any organization if code is written in C++ there is a better approach to include individual header files because if we include other things then we can have many namespace conflicts or we might be including many such things which we will not need in the code so it is a better cleaner approach that when we are starting to learn DSA we should include individual header files only I have said this stretch because it is important from the perspective of learning so in this way we create our vector and the red line has now disappeared because there is no error now now the vector size is 0 so if we try to see out vector of let's suppose 0. In that case, we will get an error of this type which is called segmentation fault. Segmentation fault means that we are trying to access a place in memory which is not possible to access, which does not have permission for us. Why? Because when index 0 does not exist in vector, when vector is empty, then error will come here. Next method to create vectors is something like this. In which we declare a vector and write equal to on the right side. Just like we initialize Mary with some elements, here also we initialize our vector with some elements. Let's suppose 1, 2, 3. So now the vector that has been created, we have created of 3 sizes. Now if we print vector of 0 in this, then we know that we will get 1 printed. This is equal to 1. Also one more thing you might be noticing. That I have added an additional thing in my command. Which is hyphen standard is equal to C++ 11. Adding this is important. If you are using vectors and there is an error in your terminal when compiling. Then I have to tell you that we are using C++ 11 standard. So that's why I have written this flag in my command. Now how will this vector look in memory? Our vector will look like an array in memory whose size is equal to 3 in which elements are 1, 2, 3 and in which index is equal to 0, 1 and 2 Now let's see the third method by which we can initialize our vector We create the vector in this way but we pass two values in it In which the first value is the size of the vector and second value is what value should be on every index so when we define our vector in this way then we will get a 3 size vector and value will be stored on every index equal to 0 we can also test it if we create a vector of size 5 and initialize the values in it, then we can see out a vector of 0 and similarly this will be a vector of 1, 2, 3 and 4. So all the values that will be printed will be equal to 0. Above the vectors, we generally create a special type of loop which we call a for each loop. How does it work? We can look at it as a form. and in for we write the name of our vector, let's suppose our vector name is Vec and in left side we write an iterator but this time our iterator, if we use an iterator like i or j so this time it will not store the index value this time iterator will store the value stored on each index of our vector means this time i is not the index but the value on the index itself for example if we write int i So, the value stored on that index is always going to be inside i. Let's test this. For example, here we decide to use a for each loop. So, for that if we write int i, we write colon and after that the name of our vector. And every time we make our i to be cout. And the type of this iterator will be equivalent to the type of our vector. So, we will run this. So we will have all the values equal to 0 and print them. In fact, let's take one more example. This time let's create a character vector in which we are going to store some characters. We will have A, we will get B, C, D and E. So this time we will have to keep the size of our iterator as a character. So if we print it, we will have all the characters printed. Also this I, generally we don't call it I. We call it A. we can give it some other name which is more readable, we can call it value. So we will know that we are trying to access the value of every index of our vector. So this is the syntax for writing a for each loop. And generally when we are using STL containers like this, we are going to be frequently using these for each loops. Now whenever we talk about vectors, we have talked about how to create empty vectors, how to create with some values, how to do it with fixed size. But in vectors, we can also do add, delete and all these operations. And to do these operations, we are going to learn about some vector functions. Basically, there are many different functions associated with vectors which help us to do different operations. The first function is our size function which returns the size of the vector. So here let us clear this. If I want to print the size of this vector. So we will simply do cout size equal to. We write vector dot size. We call our function. So in this way our size will be printed which is equal to 5. Here if we remove a character. So change will come in our size. And size is going to be equal to 4. Similarly, we have another function called pushback. Let's suppose we have created an empty vector. Here, we have created this empty vector. Let's keep its type as integer. If we print its size, then we will get print size is equal to 0. And since it does not have any element, then our loop will not run. But if we have to push an element inside this vector, then how do we push it? To push it, we use vector.push. underscore back function which pushes the element to the last of our vector. Like initially the size of vector is 0 so as soon as we push any element our vector will become of one size and in which let's suppose we stored the value 25 so 25 value will be stored here. So let's push back 25 and after that what we will do we will print our size once again. After push back our size is done. Let's clear this and run. So size was 0 earlier. After pushback, our size became equal to 1. Here we need to make a data type integer to print our vector value. So we will also get 25 printed. So in this way, our size increases as we push elements. If we want, we can push back 3 elements here. 25, 35 and 45. So in this case, our new vector size is going to be equal to 3. and we can see that the order in which we have pushed back our elements are being added to that order like 25 was 25, after 25 we have 35 so when we are pushing back, we are pushing elements in the last in our vector just like we have push back, we have this function called pop back push means in programming that we are adding something, inserting something pop means we are deleting something So pop back means that we want to delete the element in the last. As we delete it, the size of the vector will be equal to 2 again. So let's test this too. We created an empty vector here. In which we pushed 3 elements. Now we want to simply pop back our value in the vector. When we pop back, we don't need to tell the value. Because by default, our vector knows what its last index is. So in pop back, the last index value will always pop. So, from here, which value will be deleted from the vector? 45 is going to be deleted because it is on the last index. So, when we print values in this loop, then 45 will not be printed. Let's print this. In the beginning, size 3 was there, but only 25 and 35 were printed because 45 was deleted internally from the memory. Apart from this, we have another function which is called front. Front means that we are going to print the starting value of the vector, i.e. the value on the front. For example, if we remove this loop and do cout, vector.front so we will get front value which is going to be 25 similarly we have back which returns last value so last value is 35 last value is 35 because we deleted 45 and we have one more function which is called at function at is basically another syntax for accessing a value at a particular index for example we wrote vectors of some index i. So we are going to get ith index value. This is the alternate way of writing this. Vector dot at index i. So this is going to give us the same value. Vector dot at zero. So the zero-th index value will be printed which is equal to 25. If we want to look at the value at index 1 it is going to be 35. If we want to look at the value of index 2 it is going to give us an error. Why the error? Because the value on index number 2 does not exist anymore. So, we are trying to access these things again which is not possible. So, we should never go outside the index and access the values. Now, we have some additional functions related to vectors which we generally use when we are talking about iterators. But, we have not talked about iterators yet and in fact, it is not relevant for us now. So, I might make a C++ one shot for all the STL containers which we will do later. We will cover that in that video but for now we don't need to know about other functions. Next we are going to talk about static versus dynamic allocation of memory. Basically, in this section we are going to learn how vectors are implemented internally in memory. Whenever we talk about memory, we have two types of memory. One is static memory. Static memory is allocated in compile time. Generally when we create an integer array of size 5, this memory is allocated in compile time. We already talked about how our code runs in two stages. First is the compilation stage, in which compiler checks for syntaxical errors or other things like whether all header files are properly included or not. So all those things are checked in compile time. Second stage is execution which is also called running stage. So static allocation of memory is basically the memory which is allocated at compile time. So if you create an array like this, then that array will be created at compile time itself. That array will come to us. Dynamic allocation of memory is done at runtime. At runtime or execution time. Basically when we write a code, Here in the code we have written that we have to make vector of integer vec, But we did not give any element in it. initially at compile time, a vector of 0 size will be created and at runtime, this pushback function will be executed and element will be pushed inside that vector so at runtime, the size of that vector will increase because it has to store more elements so to increase the size of the vector the new memory that is being allocated when is it being done? it is being done dynamically so when is it being done dynamically? inside runtime when our program is executing so our vectors The memory allocated to vectors is dynamically allocated in runtime. That is why we said that vectors can resize. They can change their size. Whereas array size is fixed. And generally when we do programming and DSA, in majority cases we need array to resize. So that is why we use vectors frequently in our codes. But the logic of vectors, the question that can be solved by vector, can be solved by the same question by array. So the logic we made in the array chapter, we are going to re-implement in the vectors chapter. Now there is one more difference in static and dynamic allocation. Static allocation, we had already talked about, is a memory of two types. One is our stack memory, in which we had talked about stack calls, function calls. One is our heap memory. Static allocation is in the stack memory. So the array that is being created, it is getting created inside the stack itself. But... dynamic allocation is in our heap memory in fact whatever memory is dynamically allocated i.e. in runtime we are allocating all of them in heap so whenever we are asked in interviews what are the differences between static and dynamic allocation so we can tell three differences first of all it is in compile time and in runtime second is in stack and in heap third we can include examples in them now we have come to know vectors are following dynamic memory allocation in which way they are allocated in the following way But how exactly do vectors create in memory? Let's suppose we have written vector of integer vec in our code. Like this. So we will have a vector of 0 size created. Which means we don't have anything in memory. When we push back an element in this vector for the first time. Let's suppose we push back value 0. So we have a vector of 1 size created. In which this 0 value will be stored. So our vector will look something like this. Now when next time we push back another element in it, let's suppose we push back value 1. So here this new value is first of all tried to store in the old vector. Internally vector are only internally vector arrays. So the first time we made our vector of size 1 to store this 0, we made an array in memory which was equal to the size of the array 1. So vector is nothing, internally array is there in memory. and second time when we will try to store elements then it will try to store in the same array but this array is filled so what happens in memory, the old array its size is doubled and a new array is created for example here we doubled the size of 1 so now we have an array of 2 sizes now in this array we copied the old value 0 we also store the new value 1 here now this new array this will basically become our new vector and the old one will be deleted from memory and this work happens automatically we don't have to do it, it is happening automatically now let's suppose tomorrow we push back one more new element 2 in our vector now 2 will be stored in this array first but there is no space in this array then what will happen, a double size array will be created in memory means 4 size array this time it is going to be created old values will be copied in it and new value will be stored here new vector will be created for us and the old array will be deleted from memory. So now our vector looks something like this. Now these vectors have basically two properties. One is size property. Size means number of elements. One is capacity property. Capacity means how much capacity is there in it, how much space is there in it, how much space is there in this internal array which we are giving vector name, how much space is there in it, how many elements can be stored in worst case. Now in this case, the size of vector is 3 because it has only 3 elements. But what is capacity? Capacity is equal to 4. Means one more element can be stored here. So this thing that we talked about that every time size of internally array gets smaller, After that our internal array doubles, vector doubles. How to verify this? We can write exactly the same code and after writing this code, when we print size and capacity. So size will print 3 and capacity will print 4. Let's test this also. Let us create a vector which has no element. After that inside the vector we are going to push back some values. First we push back 0, then we push back 1 and Here 1 will come and here 2 will come. After this we want to cout the vector size which is going to be equal to 3. And we want to cout the vector capacity. We have another function called capacity to print. And vector capacity is going to be equal to 4. So we will print this. First value is 3, second value is 4. So basically the logic we have discussed overall. Internally in memory these things are happening. and here if we do vector.pushback 3 and vector.pushback 4 so what will happen in both cases when we do pushback 3 then 3 will be stored here but when we do pushback 4 then this place will get smaller because 4 will be stored here so we will create another array of its double size in which 0, 1, 2, 3 will be copied and 4 will be a new store but the remaining 3 places will still be empty so if the old capacity was 4, the new capacity is always double the size is not doubled, the capacity is doubled this time the capacity will be doubled to equal to 8 so after writing these two lines, if we print the size, size is going to be equal to 5 capacity is going to be equal to 8 we can verify this too here we gave 2 more pushback statements for 3 and 4 So this time size will be equal to 5 and capacity will be equal to 8. So we are getting the same values printed. So this is how a vector works internally in the memory. A vector is nothing, it is just an array in the memory. We just keep on creating double sized arrays so that the programmers feel that the vector is magically increasing in size. But it is not magical, internally, automatically this work is happening in C++. Next we are going to solve a problem which is called a single number. I gave you the same question in the last chapter as a homework problem that we have a given array. In this array, we have many different elements. Like 1, 4, 5, etc. We have to print unique elements from these. So, 4 or 5 are unique elements because their copies do not exist. Now, we have such a question. So, here the question is not more important than the question. More important than the question is how to solve the questions. So, we are going to see the question of our lead code for the first time. Whenever we are learning DSA, we will learn the concepts of DSA. We will solve many questions in lectures and classes. But it is important to practice on online platforms. Because the more you practice, the better you are going to get at DSA. This is a fact. So DSA concepts should come. It is very important to practice. Because eventually when you sit in a coding test or interview, it is not necessary that we will get the question we have seen. In some cases, the question we have seen can come. In some cases, we may get new questions and we will learn to solve new questions only when we practice a lot of questions. So we are starting with a very simple and easy level question. The question is problem number 136 on Leetcode. Simply go and create a free account on Leetcode and you can search for this problem in problems. Now when we are given a problem, generally there are three levels of easy, medium and hard problems. We always have to start by solving easy problems. Slowly we move towards medium problems and then slowly we move towards hard problems. Don't start solving medium or hard problems in the beginning. In the beginning, make a little hold on easy, feel confident in it. Then make a hold on medium, feel confident in it. Then go towards hard level problems. Now whenever we are given a question, the question is given to us in this way. Like here the question is given a non-empty area of integers, nums. Nums is non-empty, means it will not be empty, it will have some elements, such an array is given. Now we said it is an array, but on the right side, the C++ boilerplate code has a vector written in it. And generally this happens in questions. On coding platforms, the question will be of array, but there will be a use vector in it. So this is a very normal practice. Every element appears twice except for one. This is our nums, in this every element appears twice except for one element, it will come only once. Find that single one. We have to find that one element. And there are many related examples given to us from this question. So let's see this example once. In the example, we have 4, 1, 2, 1, 2. So let's draw this array once. Array is 4, 1, 2, 1, 2. Or let's call it our nums, it is our nums vector. So 1 is coming twice in this. 2 is also coming twice. But 4 is coming only once, so its answer should be equal to 4. Now we have to find out this answer, this unique element. Now whenever we have to solve questions on the platform, generally we don't have to write the entire code. We don't have to write boilerplate code here. We are given a class and a function in the class. Now what is class, why is it written public here, we will talk about all these things in the object orientation chapter of OOPS. We have to focus only on our function. Let's see this function. In this function, the return type integer is there. The name of the function is single number. All these things are already given and this vector is given with the name of nums. And we will write our complete answer in this function. The final answer is going to be a single number. we will return this then only it is return type integer. Now generally this vector given in the function along with this it is given as ampersand. As we know that normal vector looks something like this. So many students must be thinking that what is ampersand doing here. Basically whatever are our C++ containers C++ container means like a vector. Vector is a C++ container. Whenever we pass them in functions they are always by default pass by value. But we want the changes in this function to reflect. So we pass them by pass by reference instead of pass by value. And to pass by reference, we can put an ampersand in front of their name. It either comes in front of the name or we can put it here also. In both cases, we just have to put an ampersand. What happens by putting an ampersand? Our original copy or we will not call it copy. The original vector of this type, basically creates an alias. Like Gangadhar's name is Shaktimaan or Tony Stark's name is Iron Man. So these are aliases, which means an alternate name. So we create an alias, an alternate name and when we say nums, we are talking about the original. That is why this ampersand is used to pass this vector with reference. So if you do any changes in this function, in this vector, then it will reflect in the main function. So these are some basic things which we should know before we start solving any question. Now here we have some constraints in the question. Constraints means limits. These limits will be understood when we read the time complexity chapter. Otherwise, I have already made a C++ one shot which I will add in this playlist. After this chapter, I would advise you to go and see that one shot. That one shot is about... Time and Space Complexity for Interviews. In that one shot, you will understand half of the one shot. Meaning half chapter, half lecture will be understood to us. Because there are easy things in it. Half lecture we will not understand that much. Because in that, I have talked about the data structures algorithm which we will learn later. But it is necessary to see it. This will give us an idea of what time complexity and space complexity means. And why are these constraints written? What do we calculate through these constraints? That is the thing that I am giving you as a homework problem. So let's come back to the question. The question is given in this way. Now if we want, we can solve this question with nested loops. Like I gave the homework of arrays, it could have been done with nested loops. We can solve this question with nested loops too. But here the line written is linear runtime complexity. This means that you don't have to use nested loops. You have to make only one loop. We have to write only one loop. Now solving this question with only one loop as a beginner can seem a little tricky. Unless and until we have already learned a lot about bit manipulation. So this question will teach us a lot of new things. One thing which will teach us this question is that the bits we talked about, the bitwise operators we talked about, how they are used to solve questions practically, this question will teach us that. Basically, I know I have all these numbers. I have to find a unique number from these. And unique number is equal to 4, so I have to print 4. Now, before solving this problem, it's a bit like... Let's make a small mindset because it is not important to solve the problem. How is that problem being solved? What is the logic behind it? What is the thought process? It is very important to understand that. Let's suppose we have a very small problem. We have a number 4, a number 1 and a number minus 4. We know that every number has a negative available. There is only one number whose negative is not available and we have to find out that number. So how do we find out? If we have this number, then what do we do? We simply do 4 plus 1 minus 4. It will cancel out from 4 minus 4 and we will have 1 left so 1 will be our answer. Basically if plus minus was there then we know that plus and minus are in equal magnitude so we can cancel out each other. And if we got a bigger version of this problem. Like we would get 4 plus 1. plus 2, minus 1, minus 2 we cancel 1 with 1, 2 with 2, 4 comes to the answer so if we were given numbers in the form of plus minus sign then it would have been very simple for us because we just have to add everything we will always cancel out the value of plus and minus and we will get the final answer and our problem has a lot of logic on this basically, what we have to do is we know that every number we have duplicate of it there is only one unique number so we have to find a way to cancel out the number with duplicate and if we find this way then all the duplicates will cancel out from each other and only unique number will be left so what is the way in programming to cancel out two same numbers with each other and that way is hidden in bitwise operators specifically if I talk about bitwise in XOR we had read XOR operator, what were the rules of XOR operator 0 XOR 0 is 0, 1 XOR 1 is 0 0 XOR 1 is 1 and 1 XOR 0 is 1 these were our rules so what does XOR operator do, if it has same values then it cancels out those same values, cancel out means it makes them 0 only so this imp important property which XOR brings with it. Now whenever we talk about numbers, for example we take this 2 and this 2, we have 2 and we have 2, but what is 2 internally, what is it inside the computer, it is binary, the binary form of 2 is 1 0, the binary form of this 2 will also be 1 0, so for now let's just look at their binary forms, this is the first 2, this is the second 2, now if I take XOR of these two, then 1 0, 1 0, 1 0, 1 0, 1 0, So, what will be XOR with 1, 0? XOR with 0 is 0. XOR with 1 is 0. So, the XOR of two numbers whose value is same will always be equal to 0. That means they will cancel out. Just like plus 2 and minus 2 cancel out and give 0, similarly, XOR with 2 of 2 also cancel out and give 0. So, in bits, XOR performs the cancellation work which we needed. If you want, let's understand this through another example. Because I want you to remember this from today's class. Let's suppose we have a number equal to 6. 6 is equal to 110. Let's take the XOR of 110 with 110. Meaning 6 XOR 6. So 0 0 is cancelled out, 11 is cancelled out, 11 is cancelled out. The answer is equal to 0. So if you take XOR of any number with the same number, then always the value will be equal to 0. So if we talk about these numbers stored in the array. If we talk about these numbers, then let's suppose we take XOR of 1 with 1. Then this value will be 0. we will take 2's XOR with 2, so this value will be 0 and only 4 will be left. Now this XOR, we don't know which number is front and which number is back, so what we will do is, we are going to take XOR of all arrays at once. That means we will run a loop and take all the values of all arrays XOR together. And when we will take XOR of all arrays together, basically we will take 4 XOR 1, XOR 2, XOR 1, XOR 2. Now we know these numbers, you can take XOR of first, means first take 2 and 1. then take it with 2 and then with 1, the final answer is always the same so when we have taken the overall XOR of these values, then I know that XOR is going to come 0 so in the last value, if XOR of all these will be 0, then 4 XOR 5 value will be left and what is 4 XOR 5? 4 is 1 0 0, 0 is 0 so XOR of 0 and 0 will be 0, XOR of 0 and 0 will be 0, XOR of 1 and 0 will be 1 only so what will be the final answer? Final answer will be 4 only basically from here I am trying to show you a property now if we take any number N and we will take its XOR with 0 so whatever 0 will be in N when it will be XOR with 0 then it will remain 0, it will remain the same and will not change and whatever 1 will be in N it will always be XOR with 0 and its final answer will be equal to 1 so it will not change so all the bits of N will remain the same so from here we have to remember 2 properties first of all, any number XOR of N is XOR with 0 and second of all, any number XOR of 0 is the same number. These are two major learnings which we have to remember and we can use them not only in this question but in many other questions. So when we want to find our single number or our unique value from this question, then basically what we have to do is, basically we have to run a loop of all these numbers and take an XOR. And our final answer that is going to be equal to n, n means our unique value. And in fact we can solve this with a small example. For example, we have we have 3 numbers, we have 4, we have 1, we have 1 when we take 4 xor1, 001 this value will come to us as 101 so both of them will have xor1, 01 with this we will take xor again with 1 so this will be 001 equal and 100 is equal to 4 and both of them have cancelled out, we have only 4 left so this is the way to get unique element from any given array in which every element is repeating because xor will cancel out the repetitions and we will have a unique element. So what we can do is we can take an answer equal to zero. We can run a loop on all the vectors. Means integer which will be the value on every index. In the vector, let's call it nums. We will run a loop on every vector in nums. And what will be the answer every time? I have to take the XOR of every index in the answer. So answer will be equal to, we will take the XOR of answer on next index. Next index means this value. So with every value, Finally, all the values in the answer will be cancelled out. Only one last unique value will be left. We will return our answer from here. So, this way our logic will be complete. We have used only one loop in it. Means we have followed this condition of linear runtime complexity. Constant space means you can make single variables. So, we have made only single variable, only answer. So, this constant extra space is satisfying all the conditions. So let's write the code for this. In the code, this is our function. We have to take an answer which we will initialize with 0. Then we will run an for each loop integer value in our nums. Answer is going to be answer.exhort value. And finally we will return our answer. First of all, we will try to run this code. All test cases are passing. Now we will submit this. After submitting, our solution is accepted. Also this thing here, We can also do this in short. We can write this as XOR equal to. If we write it like this, then our code will be successfully compiled. So I hope we understood two things here. First of all, how to read and solve questions on platforms like Leadcode. Second thing, the old things that we read, which seemed very simple to us, like Bitwise operators, how those small things can be used to solve big questions. So, nothing is small or unimportant, everything has its own use towards the question of some DSA. So, we have completed this question here. Next chapter will be Arrays part 2, in which we are going to solve a lot of questions. Now we will solve those questions through vectors, but we will name that chapter Arrays part 2. So, in today's chapter, we basically discussed what was STL, what is a vector, how do we use different functions inside the vector, static versus dynamic. We talked about memory allocation. Apart from that, we saw how vectors are created internally in memory. Plus, we saw that in Leetcode or any other platform, the way to solve all the questions is almost the same. Whether you solve the questions on Codeforces, whether you solve the questions on Codechef, whether you solve the questions on Hackerearth, generally you would have given a question, you would have to complete some function and that's it. On some platforms, you may have to write the entire code, you may have to submit the file, But there will be no problem because we are writing the code in Visual Studio Code. And along with that we also solved this question called single number. In which we used bit or bitwise operator. So we have covered all these things in today's chapter. Two things I will give you very simple things, homework problem. First of all you have to write the code of linear search on a vector. Second thing you have to write the code of reverse on a vector. And this reverse code has to be written in function. And when you pass this function as a vector, you have to notice one thing that the vector that is being reversed in the function, will it reflect in the main function as well? And if it doesn't reflect, then how will you pass by reference for it? We have already learnt that by looking at the question of leetcode. So how can you implement that in your code? You have to do that too. So these are two things that you have to try as a homework problem. Also, you can also go on leetcode and try to solve easy level array problems or vector problems. You can start trying easy level problems little by little. It is possible that if it is not solved by us now, then there is nothing to worry about. Gradually, as we will learn more data structures and things, our problem will start to be solved more. So that's it in this lecture. From the next chapter, we will start solving the questions of many areas. That's it for today. See you in the next video. Till then keep learning and keep exploring.

So let's start talking about vectors. Vectors are basically our next data structure which we will study in detail in today's chapter. And this data structure is very array-like. When we visualize an array, it looks like an array with different blocks in it, which we store data in. And we also have indices and indexes like arrays.

So, this is how we visualize our vector. What are vectors? They are dynamic in nature. Dynamic in nature means that they do not have a fixed size.

Their size can change. This is a major difference between arrays and vectors. Now before reading vectors, we should know one important thing which is STL.

STL is Standard Template Library of C++. STL is basically a library, we can imagine it as a toolbox, in which the implementation code of many data structures is already written. Many of our data structures like stack, hash table, queue, and many other data structures.

They have to be implemented from scratch in any programming language. But whenever we are in an interview for placement, internship, coding test, we have limited time. So we cannot implement all these data structures from scratch to solve a single question. So in STL, in this library, their implementation has already been written.

So we directly pick these data structures from this library as a tool. And then we use that tool to solve our question. So the implementation of vector is written in this library and we just have to use vectors directly to solve our questions. Now how the vectors are implemented internally, we will discuss that in this chapter also. So it is not like we will skip an important part.

We will discuss that implementation also but usage is more important. Now using STL is allowed in placements and interviews. So we are not doing anything that we are taking out a lot of shortcuts. We solve our questions using STL only in DSA. And in this same STL we have many tools, one of which is vector.

So we take the vector tool and we have to directly implement it, that is, we start making different vectors for ourselves. And in STL, the vector that happens, we will read Q in the future, we will read stack in the future, we will read set in the future and we will read different data structures. So all these data structures are called STL containers.

Containers means that these are containers to store some kind of data. So first of all let's talk about our first STL container which is a vector. Now we have already discussed the vector, we imagine it as an array.

But inside the array, the size is fixed. So if we have made an array to store information of 100 students, then if tomorrow there are 1000 students, then we will not be able to use this array. So to solve this problem, we have vectors and vectors are dynamically resized after implementation.

If we want, we can increase the size of our vector in memory. There are different syntaxes to create vectors. The first syntax is this.

We write vector. then in angular brackets we write type of the vector, that what type will be stored in it, then we tell the name of our vector. So, in this way we can declare a vector for ourselves. So, let's come to the code once, and in the code we create a vector of integers, which we have named vec. Now, when we create a vector in this way, first of all, the size of this vector will be equal to zero.

Why? Because there is no element stored in it, so by default this vector is of size zero. Also, when we create a vector, we will get an error. The error is because to create vectors, we have to include our vector header file.

If we don't include this header file, we will get an error. Because what is vector? Where is its implementation?

The implementation of vector is written in STL and that is why we have to include this header file. Now, you might have noticed online that instead of this file, what do people do? dot h, in many places you must have seen this header file including many students.

Now this header file, students include this header file to solve questions on many coding platforms. But I will not advise you to include this. Why?

Because generally in interviews you can be asked which header file is of individual vector and which header file is of other data structure so we should have that knowledge plus because we are starting in C++ and learning data structures for the first time so we should have an idea of which header file is of which data structure and generally in any organization if code is written in C++ there is a better approach to include individual header files because if we include other things then we can have many namespace conflicts or we might be including many such things which we will not need in the code so it is a better cleaner approach that when we are starting to learn DSA we should include individual header files only I have said this stretch because it is important from the perspective of learning so in this way we create our vector and the red line has now disappeared because there is no error now now the vector size is 0 so if we try to see out vector of let's suppose 0. In that case, we will get an error of this type which is called segmentation fault. Segmentation fault means that we are trying to access a place in memory which is not possible to access, which does not have permission for us. Why? Because when index 0 does not exist in vector, when vector is empty, then error will come here. Next method to create vectors is something like this.

In which we declare a vector and write equal to on the right side. Just like we initialize Mary with some elements, here also we initialize our vector with some elements. Let's suppose 1, 2, 3. So now the vector that has been created, we have created of 3 sizes. Now if we print vector of 0 in this, then we know that we will get 1 printed. This is equal to 1. Also one more thing you might be noticing.

That I have added an additional thing in my command. Which is hyphen standard is equal to C++ 11. Adding this is important. If you are using vectors and there is an error in your terminal when compiling.

Then I have to tell you that we are using C++ 11 standard. So that's why I have written this flag in my command. Now how will this vector look in memory?

Our vector will look like an array in memory whose size is equal to 3 in which elements are 1, 2, 3 and in which index is equal to 0, 1 and 2 Now let's see the third method by which we can initialize our vector We create the vector in this way but we pass two values in it In which the first value is the size of the vector and second value is what value should be on every index so when we define our vector in this way then we will get a 3 size vector and value will be stored on every index equal to 0 we can also test it if we create a vector of size 5 and initialize the values in it, then we can see out a vector of 0 and similarly this will be a vector of 1, 2, 3 and 4. So all the values that will be printed will be equal to 0. Above the vectors, we generally create a special type of loop which we call a for each loop. How does it work? We can look at it as a form.

and in for we write the name of our vector, let's suppose our vector name is Vec and in left side we write an iterator but this time our iterator, if we use an iterator like i or j so this time it will not store the index value this time iterator will store the value stored on each index of our vector means this time i is not the index but the value on the index itself for example if we write int i So, the value stored on that index is always going to be inside i. Let's test this. For example, here we decide to use a for each loop. So, for that if we write int i, we write colon and after that the name of our vector.

And every time we make our i to be cout. And the type of this iterator will be equivalent to the type of our vector. So, we will run this.

So we will have all the values equal to 0 and print them. In fact, let's take one more example. This time let's create a character vector in which we are going to store some characters.

We will have A, we will get B, C, D and E. So this time we will have to keep the size of our iterator as a character. So if we print it, we will have all the characters printed. Also this I, generally we don't call it I. We call it A.

we can give it some other name which is more readable, we can call it value. So we will know that we are trying to access the value of every index of our vector. So this is the syntax for writing a for each loop.

And generally when we are using STL containers like this, we are going to be frequently using these for each loops. Now whenever we talk about vectors, we have talked about how to create empty vectors, how to create with some values, how to do it with fixed size. But in vectors, we can also do add, delete and all these operations. And to do these operations, we are going to learn about some vector functions. Basically, there are many different functions associated with vectors which help us to do different operations.

The first function is our size function which returns the size of the vector. So here let us clear this. If I want to print the size of this vector.

So we will simply do cout size equal to. We write vector dot size. We call our function. So in this way our size will be printed which is equal to 5. Here if we remove a character. So change will come in our size.

And size is going to be equal to 4. Similarly, we have another function called pushback. Let's suppose we have created an empty vector. Here, we have created this empty vector.

Let's keep its type as integer. If we print its size, then we will get print size is equal to 0. And since it does not have any element, then our loop will not run. But if we have to push an element inside this vector, then how do we push it? To push it, we use vector.push.

underscore back function which pushes the element to the last of our vector. Like initially the size of vector is 0 so as soon as we push any element our vector will become of one size and in which let's suppose we stored the value 25 so 25 value will be stored here. So let's push back 25 and after that what we will do we will print our size once again.

After push back our size is done. Let's clear this and run. So size was 0 earlier.

After pushback, our size became equal to 1. Here we need to make a data type integer to print our vector value. So we will also get 25 printed. So in this way, our size increases as we push elements.

If we want, we can push back 3 elements here. 25, 35 and 45. So in this case, our new vector size is going to be equal to 3. and we can see that the order in which we have pushed back our elements are being added to that order like 25 was 25, after 25 we have 35 so when we are pushing back, we are pushing elements in the last in our vector just like we have push back, we have this function called pop back push means in programming that we are adding something, inserting something pop means we are deleting something So pop back means that we want to delete the element in the last. As we delete it, the size of the vector will be equal to 2 again. So let's test this too.

We created an empty vector here. In which we pushed 3 elements. Now we want to simply pop back our value in the vector. When we pop back, we don't need to tell the value.

Because by default, our vector knows what its last index is. So in pop back, the last index value will always pop. So, from here, which value will be deleted from the vector? 45 is going to be deleted because it is on the last index. So, when we print values in this loop, then 45 will not be printed.

Let's print this. In the beginning, size 3 was there, but only 25 and 35 were printed because 45 was deleted internally from the memory. Apart from this, we have another function which is called front. Front means that we are going to print the starting value of the vector, i.e. the value on the front. For example, if we remove this loop and do cout, vector.front so we will get front value which is going to be 25 similarly we have back which returns last value so last value is 35 last value is 35 because we deleted 45 and we have one more function which is called at function at is basically another syntax for accessing a value at a particular index for example we wrote vectors of some index i.

So we are going to get ith index value. This is the alternate way of writing this. Vector dot at index i.

So this is going to give us the same value. Vector dot at zero. So the zero-th index value will be printed which is equal to 25. If we want to look at the value at index 1 it is going to be 35. If we want to look at the value of index 2 it is going to give us an error.

Why the error? Because the value on index number 2 does not exist anymore. So, we are trying to access these things again which is not possible.

So, we should never go outside the index and access the values. Now, we have some additional functions related to vectors which we generally use when we are talking about iterators. But, we have not talked about iterators yet and in fact, it is not relevant for us now.

So, I might make a C++ one shot for all the STL containers which we will do later. We will cover that in that video but for now we don't need to know about other functions. Next we are going to talk about static versus dynamic allocation of memory.

Basically, in this section we are going to learn how vectors are implemented internally in memory. Whenever we talk about memory, we have two types of memory. One is static memory. Static memory is allocated in compile time. Generally when we create an integer array of size 5, this memory is allocated in compile time.

We already talked about how our code runs in two stages. First is the compilation stage, in which compiler checks for syntaxical errors or other things like whether all header files are properly included or not. So all those things are checked in compile time. Second stage is execution which is also called running stage.

So static allocation of memory is basically the memory which is allocated at compile time. So if you create an array like this, then that array will be created at compile time itself. That array will come to us.

Dynamic allocation of memory is done at runtime. At runtime or execution time. Basically when we write a code, Here in the code we have written that we have to make vector of integer vec, But we did not give any element in it.

initially at compile time, a vector of 0 size will be created and at runtime, this pushback function will be executed and element will be pushed inside that vector so at runtime, the size of that vector will increase because it has to store more elements so to increase the size of the vector the new memory that is being allocated when is it being done? it is being done dynamically so when is it being done dynamically? inside runtime when our program is executing so our vectors The memory allocated to vectors is dynamically allocated in runtime. That is why we said that vectors can resize. They can change their size.

Whereas array size is fixed. And generally when we do programming and DSA, in majority cases we need array to resize. So that is why we use vectors frequently in our codes.

But the logic of vectors, the question that can be solved by vector, can be solved by the same question by array. So the logic we made in the array chapter, we are going to re-implement in the vectors chapter. Now there is one more difference in static and dynamic allocation.

Static allocation, we had already talked about, is a memory of two types. One is our stack memory, in which we had talked about stack calls, function calls. One is our heap memory. Static allocation is in the stack memory. So the array that is being created, it is getting created inside the stack itself.

But... dynamic allocation is in our heap memory in fact whatever memory is dynamically allocated i.e. in runtime we are allocating all of them in heap so whenever we are asked in interviews what are the differences between static and dynamic allocation so we can tell three differences first of all it is in compile time and in runtime second is in stack and in heap third we can include examples in them now we have come to know vectors are following dynamic memory allocation in which way they are allocated in the following way But how exactly do vectors create in memory? Let's suppose we have written vector of integer vec in our code. Like this. So we will have a vector of 0 size created.

Which means we don't have anything in memory. When we push back an element in this vector for the first time. Let's suppose we push back value 0. So we have a vector of 1 size created. In which this 0 value will be stored.

So our vector will look something like this. Now when next time we push back another element in it, let's suppose we push back value 1. So here this new value is first of all tried to store in the old vector. Internally vector are only internally vector arrays. So the first time we made our vector of size 1 to store this 0, we made an array in memory which was equal to the size of the array 1. So vector is nothing, internally array is there in memory.

and second time when we will try to store elements then it will try to store in the same array but this array is filled so what happens in memory, the old array its size is doubled and a new array is created for example here we doubled the size of 1 so now we have an array of 2 sizes now in this array we copied the old value 0 we also store the new value 1 here now this new array this will basically become our new vector and the old one will be deleted from memory and this work happens automatically we don't have to do it, it is happening automatically now let's suppose tomorrow we push back one more new element 2 in our vector now 2 will be stored in this array first but there is no space in this array then what will happen, a double size array will be created in memory means 4 size array this time it is going to be created old values will be copied in it and new value will be stored here new vector will be created for us and the old array will be deleted from memory. So now our vector looks something like this. Now these vectors have basically two properties. One is size property. Size means number of elements.

One is capacity property. Capacity means how much capacity is there in it, how much space is there in it, how much space is there in this internal array which we are giving vector name, how much space is there in it, how many elements can be stored in worst case. Now in this case, the size of vector is 3 because it has only 3 elements.

But what is capacity? Capacity is equal to 4. Means one more element can be stored here. So this thing that we talked about that every time size of internally array gets smaller, After that our internal array doubles, vector doubles.

How to verify this? We can write exactly the same code and after writing this code, when we print size and capacity. So size will print 3 and capacity will print 4. Let's test this also. Let us create a vector which has no element. After that inside the vector we are going to push back some values.

First we push back 0, then we push back 1 and Here 1 will come and here 2 will come. After this we want to cout the vector size which is going to be equal to 3. And we want to cout the vector capacity. We have another function called capacity to print.

And vector capacity is going to be equal to 4. So we will print this. First value is 3, second value is 4. So basically the logic we have discussed overall. Internally in memory these things are happening. and here if we do vector.pushback 3 and vector.pushback 4 so what will happen in both cases when we do pushback 3 then 3 will be stored here but when we do pushback 4 then this place will get smaller because 4 will be stored here so we will create another array of its double size in which 0, 1, 2, 3 will be copied and 4 will be a new store but the remaining 3 places will still be empty so if the old capacity was 4, the new capacity is always double the size is not doubled, the capacity is doubled this time the capacity will be doubled to equal to 8 so after writing these two lines, if we print the size, size is going to be equal to 5 capacity is going to be equal to 8 we can verify this too here we gave 2 more pushback statements for 3 and 4 So this time size will be equal to 5 and capacity will be equal to 8. So we are getting the same values printed. So this is how a vector works internally in the memory.

A vector is nothing, it is just an array in the memory. We just keep on creating double sized arrays so that the programmers feel that the vector is magically increasing in size. But it is not magical, internally, automatically this work is happening in C++.

Next we are going to solve a problem which is called a single number. I gave you the same question in the last chapter as a homework problem that we have a given array. In this array, we have many different elements.

Like 1, 4, 5, etc. We have to print unique elements from these. So, 4 or 5 are unique elements because their copies do not exist.

Now, we have such a question. So, here the question is not more important than the question. More important than the question is how to solve the questions.

So, we are going to see the question of our lead code for the first time. Whenever we are learning DSA, we will learn the concepts of DSA. We will solve many questions in lectures and classes. But it is important to practice on online platforms. Because the more you practice, the better you are going to get at DSA.

This is a fact. So DSA concepts should come. It is very important to practice. Because eventually when you sit in a coding test or interview, it is not necessary that we will get the question we have seen.

In some cases, the question we have seen can come. In some cases, we may get new questions and we will learn to solve new questions only when we practice a lot of questions. So we are starting with a very simple and easy level question.

The question is problem number 136 on Leetcode. Simply go and create a free account on Leetcode and you can search for this problem in problems. Now when we are given a problem, generally there are three levels of easy, medium and hard problems. We always have to start by solving easy problems.

Slowly we move towards medium problems and then slowly we move towards hard problems. Don't start solving medium or hard problems in the beginning. In the beginning, make a little hold on easy, feel confident in it.

Then make a hold on medium, feel confident in it. Then go towards hard level problems. Now whenever we are given a question, the question is given to us in this way.

Like here the question is given a non-empty area of integers, nums. Nums is non-empty, means it will not be empty, it will have some elements, such an array is given. Now we said it is an array, but on the right side, the C++ boilerplate code has a vector written in it. And generally this happens in questions. On coding platforms, the question will be of array, but there will be a use vector in it.

So this is a very normal practice. Every element appears twice except for one. This is our nums, in this every element appears twice except for one element, it will come only once.

Find that single one. We have to find that one element. And there are many related examples given to us from this question.

So let's see this example once. In the example, we have 4, 1, 2, 1, 2. So let's draw this array once. Array is 4, 1, 2, 1, 2. Or let's call it our nums, it is our nums vector.

So 1 is coming twice in this. 2 is also coming twice. But 4 is coming only once, so its answer should be equal to 4. Now we have to find out this answer, this unique element.

Now whenever we have to solve questions on the platform, generally we don't have to write the entire code. We don't have to write boilerplate code here. We are given a class and a function in the class. Now what is class, why is it written public here, we will talk about all these things in the object orientation chapter of OOPS. We have to focus only on our function.

Let's see this function. In this function, the return type integer is there. The name of the function is single number.

All these things are already given and this vector is given with the name of nums. And we will write our complete answer in this function. The final answer is going to be a single number. we will return this then only it is return type integer.

Now generally this vector given in the function along with this it is given as ampersand. As we know that normal vector looks something like this. So many students must be thinking that what is ampersand doing here.

Basically whatever are our C++ containers C++ container means like a vector. Vector is a C++ container. Whenever we pass them in functions they are always by default pass by value.

But we want the changes in this function to reflect. So we pass them by pass by reference instead of pass by value. And to pass by reference, we can put an ampersand in front of their name.

It either comes in front of the name or we can put it here also. In both cases, we just have to put an ampersand. What happens by putting an ampersand? Our original copy or we will not call it copy.

The original vector of this type, basically creates an alias. Like Gangadhar's name is Shaktimaan or Tony Stark's name is Iron Man. So these are aliases, which means an alternate name.

So we create an alias, an alternate name and when we say nums, we are talking about the original. That is why this ampersand is used to pass this vector with reference. So if you do any changes in this function, in this vector, then it will reflect in the main function. So these are some basic things which we should know before we start solving any question. Now here we have some constraints in the question.

Constraints means limits. These limits will be understood when we read the time complexity chapter. Otherwise, I have already made a C++ one shot which I will add in this playlist.

After this chapter, I would advise you to go and see that one shot. That one shot is about... Time and Space Complexity for Interviews.

In that one shot, you will understand half of the one shot. Meaning half chapter, half lecture will be understood to us. Because there are easy things in it.

Half lecture we will not understand that much. Because in that, I have talked about the data structures algorithm which we will learn later. But it is necessary to see it.

This will give us an idea of what time complexity and space complexity means. And why are these constraints written? What do we calculate through these constraints?

That is the thing that I am giving you as a homework problem. So let's come back to the question. The question is given in this way. Now if we want, we can solve this question with nested loops.

Like I gave the homework of arrays, it could have been done with nested loops. We can solve this question with nested loops too. But here the line written is linear runtime complexity.

This means that you don't have to use nested loops. You have to make only one loop. We have to write only one loop.

Now solving this question with only one loop as a beginner can seem a little tricky. Unless and until we have already learned a lot about bit manipulation. So this question will teach us a lot of new things.

One thing which will teach us this question is that the bits we talked about, the bitwise operators we talked about, how they are used to solve questions practically, this question will teach us that. Basically, I know I have all these numbers. I have to find a unique number from these.

And unique number is equal to 4, so I have to print 4. Now, before solving this problem, it's a bit like... Let's make a small mindset because it is not important to solve the problem. How is that problem being solved? What is the logic behind it? What is the thought process?

It is very important to understand that. Let's suppose we have a very small problem. We have a number 4, a number 1 and a number minus 4. We know that every number has a negative available.

There is only one number whose negative is not available and we have to find out that number. So how do we find out? If we have this number, then what do we do?

We simply do 4 plus 1 minus 4. It will cancel out from 4 minus 4 and we will have 1 left so 1 will be our answer. Basically if plus minus was there then we know that plus and minus are in equal magnitude so we can cancel out each other. And if we got a bigger version of this problem. Like we would get 4 plus 1. plus 2, minus 1, minus 2 we cancel 1 with 1, 2 with 2, 4 comes to the answer so if we were given numbers in the form of plus minus sign then it would have been very simple for us because we just have to add everything we will always cancel out the value of plus and minus and we will get the final answer and our problem has a lot of logic on this basically, what we have to do is we know that every number we have duplicate of it there is only one unique number so we have to find a way to cancel out the number with duplicate and if we find this way then all the duplicates will cancel out from each other and only unique number will be left so what is the way in programming to cancel out two same numbers with each other and that way is hidden in bitwise operators specifically if I talk about bitwise in XOR we had read XOR operator, what were the rules of XOR operator 0 XOR 0 is 0, 1 XOR 1 is 0 0 XOR 1 is 1 and 1 XOR 0 is 1 these were our rules so what does XOR operator do, if it has same values then it cancels out those same values, cancel out means it makes them 0 only so this imp important property which XOR brings with it. Now whenever we talk about numbers, for example we take this 2 and this 2, we have 2 and we have 2, but what is 2 internally, what is it inside the computer, it is binary, the binary form of 2 is 1 0, the binary form of this 2 will also be 1 0, so for now let's just look at their binary forms, this is the first 2, this is the second 2, now if I take XOR of these two, then 1 0, 1 0, 1 0, 1 0, 1 0, So, what will be XOR with 1, 0?

XOR with 0 is 0. XOR with 1 is 0. So, the XOR of two numbers whose value is same will always be equal to 0. That means they will cancel out. Just like plus 2 and minus 2 cancel out and give 0, similarly, XOR with 2 of 2 also cancel out and give 0. So, in bits, XOR performs the cancellation work which we needed. If you want, let's understand this through another example. Because I want you to remember this from today's class.

Let's suppose we have a number equal to 6. 6 is equal to 110. Let's take the XOR of 110 with 110. Meaning 6 XOR 6. So 0 0 is cancelled out, 11 is cancelled out, 11 is cancelled out. The answer is equal to 0. So if you take XOR of any number with the same number, then always the value will be equal to 0. So if we talk about these numbers stored in the array. If we talk about these numbers, then let's suppose we take XOR of 1 with 1. Then this value will be 0. we will take 2's XOR with 2, so this value will be 0 and only 4 will be left. Now this XOR, we don't know which number is front and which number is back, so what we will do is, we are going to take XOR of all arrays at once. That means we will run a loop and take all the values of all arrays XOR together.

And when we will take XOR of all arrays together, basically we will take 4 XOR 1, XOR 2, XOR 1, XOR 2. Now we know these numbers, you can take XOR of first, means first take 2 and 1. then take it with 2 and then with 1, the final answer is always the same so when we have taken the overall XOR of these values, then I know that XOR is going to come 0 so in the last value, if XOR of all these will be 0, then 4 XOR 5 value will be left and what is 4 XOR 5? 4 is 1 0 0, 0 is 0 so XOR of 0 and 0 will be 0, XOR of 0 and 0 will be 0, XOR of 1 and 0 will be 1 only so what will be the final answer? Final answer will be 4 only basically from here I am trying to show you a property now if we take any number N and we will take its XOR with 0 so whatever 0 will be in N when it will be XOR with 0 then it will remain 0, it will remain the same and will not change and whatever 1 will be in N it will always be XOR with 0 and its final answer will be equal to 1 so it will not change so all the bits of N will remain the same so from here we have to remember 2 properties first of all, any number XOR of N is XOR with 0 and second of all, any number XOR of 0 is the same number. These are two major learnings which we have to remember and we can use them not only in this question but in many other questions.

So when we want to find our single number or our unique value from this question, then basically what we have to do is, basically we have to run a loop of all these numbers and take an XOR. And our final answer that is going to be equal to n, n means our unique value. And in fact we can solve this with a small example.

For example, we have we have 3 numbers, we have 4, we have 1, we have 1 when we take 4 xor1, 001 this value will come to us as 101 so both of them will have xor1, 01 with this we will take xor again with 1 so this will be 001 equal and 100 is equal to 4 and both of them have cancelled out, we have only 4 left so this is the way to get unique element from any given array in which every element is repeating because xor will cancel out the repetitions and we will have a unique element. So what we can do is we can take an answer equal to zero. We can run a loop on all the vectors.

Means integer which will be the value on every index. In the vector, let's call it nums. We will run a loop on every vector in nums. And what will be the answer every time?

I have to take the XOR of every index in the answer. So answer will be equal to, we will take the XOR of answer on next index. Next index means this value. So with every value, Finally, all the values in the answer will be cancelled out.

Only one last unique value will be left. We will return our answer from here. So, this way our logic will be complete.

We have used only one loop in it. Means we have followed this condition of linear runtime complexity. Constant space means you can make single variables. So, we have made only single variable, only answer. So, this constant extra space is satisfying all the conditions.

So let's write the code for this. In the code, this is our function. We have to take an answer which we will initialize with 0. Then we will run an for each loop integer value in our nums.

Answer is going to be answer.exhort value. And finally we will return our answer. First of all, we will try to run this code. All test cases are passing. Now we will submit this.

After submitting, our solution is accepted. Also this thing here, We can also do this in short. We can write this as XOR equal to. If we write it like this, then our code will be successfully compiled.

So I hope we understood two things here. First of all, how to read and solve questions on platforms like Leadcode. Second thing, the old things that we read, which seemed very simple to us, like Bitwise operators, how those small things can be used to solve big questions.

So, nothing is small or unimportant, everything has its own use towards the question of some DSA. So, we have completed this question here. Next chapter will be Arrays part 2, in which we are going to solve a lot of questions.

Now we will solve those questions through vectors, but we will name that chapter Arrays part 2. So, in today's chapter, we basically discussed what was STL, what is a vector, how do we use different functions inside the vector, static versus dynamic. We talked about memory allocation. Apart from that, we saw how vectors are created internally in memory.

Plus, we saw that in Leetcode or any other platform, the way to solve all the questions is almost the same. Whether you solve the questions on Codeforces, whether you solve the questions on Codechef, whether you solve the questions on Hackerearth, generally you would have given a question, you would have to complete some function and that's it. On some platforms, you may have to write the entire code, you may have to submit the file, But there will be no problem because we are writing the code in Visual Studio Code.

And along with that we also solved this question called single number. In which we used bit or bitwise operator. So we have covered all these things in today's chapter.

Two things I will give you very simple things, homework problem. First of all you have to write the code of linear search on a vector. Second thing you have to write the code of reverse on a vector.

And this reverse code has to be written in function. And when you pass this function as a vector, you have to notice one thing that the vector that is being reversed in the function, will it reflect in the main function as well? And if it doesn't reflect, then how will you pass by reference for it? We have already learnt that by looking at the question of leetcode.

So how can you implement that in your code? You have to do that too. So these are two things that you have to try as a homework problem.

Also, you can also go on leetcode and try to solve easy level array problems or vector problems. You can start trying easy level problems little by little. It is possible that if it is not solved by us now, then there is nothing to worry about. Gradually, as we will learn more data structures and things, our problem will start to be solved more.

So that's it in this lecture. From the next chapter, we will start solving the questions of many areas. That's it for today.

See you in the next video. Till then keep learning and keep exploring.

Transcript for:Understanding Vectors and Their Applications

Transcript for:
Understanding Vectors and Their Applications