Competitive Programming - Concepts with examples

We may face many Interview Questions which can ask us to find the Sum of XOR of all pairs of the array OR  Sum of XOR of all subsets   Generally, the constraints for these questions are very high with the value of each array element to be as large as 10^18. So that is a catch to use Bit manipulation method to solve the questions. We will be discussing some of these questions in this post.   Question  1:  Sum of XOR of all possible subsets   Given an array arr[] of size n, we need to find sum of all the values that comes from XORing all   the elements of the subsets.   Input                                                Output  3                                             ...

We are given an array a[], and we want to be able to perform two types of operations on it. Change the value stored at an index i. (This is called a  point update  operation) Find the sum of a prefix of length k. (This is called a  range sum  query) Solving this question using brute force method would result in a time complexity of O(k) for finding the sum.  Using segment tree the same can be done in O(logK) time. How much better can BIT do to the time complexity?  Ans: No Better.. Time complexity will be same as O(logK) Then why use it? Ans: B ecause binary indexed trees require less space and are  very easy to implement  during programming contests (the  total code is not more than 8-10 lines ).   We know the fact that each integer can be represented as sum of powers of two. Similarly, for a given array of size N, we can maintain an array BIT[] such that, at any index we can store sum of some numb...

A Trie because of its re Trie Val property can be used to solve many problems that require to find the maximum XOR values or problems involving XOR. In this post, we will discuss similar problems where Trie can be used to solve them. Reference Links: Tutorials on Trie   Lets Jump to some questions  : Question  1:   MAX_XOR Given an array of integers , we have to find two elements whose XOR is maximum. Explanation: We First insert our numbers as bits in the Trie as we go. Now for finding the max XOR we start from the MSB and check along.  Let's say our number Y is b1,b2...bn, where b1,b2.. are binary bits. We start from b1. Now for the XOR to be maximum, we'll try to make most significant bit 1 after taking XOR. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favorable option is not there, we'll go other side. Doing this all over for i=1 to n, we'll get the maximum XOR possible. ...