New Start onwards: Learning Bitset in C++

 Bitset

This is a C++ STL library that can be used as bool and all bitwise operations can be performed on it.
It is declared as bitset<size> name; here size is the number of bits you want. For example, if size=10 it will act as a bool array of size 10. 

you can set ith bit by using "name.set(i);" but note the bit indexing starts from the right side and from 0. If our bit set is for example bitset<12>name; and we used name.set(5) the result will be 000000100000.

also, there's an interesting thing 


here in the above code, you will see in the val bitset we set 1,5 and 8th (indexes) and in diff bitset we perform an operation for each i which is true, diff|= (val>>i) or (diff =diff||(val>>i)) so we perform 'or'operation of diff using val. 

So what happens is let's say we have initial val 0010001000 where bit 3 and bit 7 is 1 or set.
if we perform operation val>>3 we will get 0000001001 we get bit 0 and bit 4 set. We can say that this shift operation caused (j-3) bit to get set (7-3 and 3-3) where j is every set bit on left of 3.So when we perform Val>>i we shift it by i and all the bits (j-i)  where j is every set bit on left or eqaul to i.

and this is O(n) operation for following code

for(i=0;i<=10;i++)  
{
    for(j=i;j<10;j++)
    {
        diff=val[j]-val[i];
    }
}

which is an O(n^2) operation.

we can similarly do for addition. we just have to perform left shift for that.
I am still learning it so I while I discover more operations I will keep adding.

This approach was used in the Codechef ADDSQURE question which came in October Long 2020 where I couldn't do it for full marks. Full marks solution O(n) for it and my O(n^2) solution are below.

Full marks O(n)

My solution O(n^2)

Comments

Post a Comment

Popular posts from this blog

LeetCode 3Sum

Question Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Brute force We can run 3 loops to check each possible triplets, we also need to eliminate the duplicates from both sides. this method will work but will work but will give time limit exceed after time constraints. To do this in given time limit we need to sort the array first and Create a loop that fixes the left most integer. This reduces the problem to 2sum for remaining array. For each loop iteration where duplicates are skipped, we need to do a left/right iteration using while loop. my code:
Read more

New start Day 2 (1/10/2020) codeforces 492B Vanya and Lantern

 question: (source: https://codeforces.com/problemset/problem/492/B)      Vanya And Lantern Vanya walks late at night along a straight street of length  l , lit by  n  lanterns. Consider the coordinate system with the beginning of the street corresponding to point  0 , and its end corresponding to the point  l . Then the  i -th lantern is at the point  a i . The lantern lights all points of the street that are at the distance of at most  d  from it, where  d  is some positive number, common for all lanterns. Vanya wonders: what is the minimum light radius  d  should the lanterns have to light the whole street? Input The first line contains two integers  n ,  l  ( 1 ≤  n  ≤ 1000 ,  1 ≤  l  ≤ 10 9 ) — the number of lanterns and the length of the street respectively. The next line contains  n  integers  a i  ( 0 ≤  a i  ≤  l ). Multiple lanterns can be loca...
Read more

Heap (min)

 Heap Heap is a data structure used to store numbers in form of binary tree i.e each node has two children. Heap is the data structure behind PriorityQueue. Insert and pop operation inside a heap is oh log(n) complexity and can be used in multiple insert and pop operation questions. It is efficient and used in fastest sorting as well as sorting only takes nlog(n) complexity at worst case. Important Functions for heap: 1.  Heapify: This function is a top down approach to set an given array into heap. The idea is to set the top priority Item at the parent node of given subtree of 3. We will compare priority of left item from parent and then from right item to that of winner of parent and left and then swap the top priority with parent item. If top priority wasn't the parent item then we call the heapify again for the right or left node with which the value was swapped. If we have a given array then we can run a loop into that array from bottom of tree to top (excluding leafs),i....
Read more