Currently studing bit-manipulation and like to share some interesting catch that i got.

1. As last bit for a give number n is (n&1), but we can also got this value through ((n)&(-n)).

2. If we have given two numbers a and b, and ask to count number of bit change in a to conver a to b, is simply count 1's set bit in (a^b), where ^ is xor operator.

3. Best way to count 1's set bit for any nuber n by using n=(n&(n-1);

   while(n) { n=n&(n-1); count_setbit++; //Count 1's set bit. }

4. Programme to generate all possible subsequence of a given string

   #include <bits/stdc++.h>
           using namespace std;
           int main()
           {
               string s;   cin>>s;
   
               int len=s.size();
   
               for(int i=0;i<1<<len;i++)
               {
                   int n=i;    string ans="";
   
                   for(int j=0;j<len;j++)
                   if(n&(1<<j))
                   ans+=s[j];
                   cout<<ans<<"\n";
               } 
               return 0;
           }

I'm parise if you share more initiation like this.

Your text to link here...

JUst Posting it for revision purpose.

First solution, n adds and 1 mod First, let's make ai = x * n + i (for some x). Then, let's mod the whole array with n (making ai = i). If the "add update" changed one index, we can just add i + n - ai%n to index i. The problem is, if we make ai = x * n + i, then update an index j > i, ai will be ruined. Just start from the back of the array!

Second solution, 1 add and n mods Note: for any a, b, if b > a, a%b = a. Additionally, if a ≥ b > a/2, a%b = a - b.

Let's add 5x10^5 to the whole array, loop over ai (in order), and mod prefix i with ai - i. Why does this work? Notice that ai%(ai - i) = ai - (ai - i) = i (the second note). Also, ai won't be changed afterwards (the first note).