Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com
And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Friday, February 14, 2014

BIT2-Search Bit Sum

Search Bit Sum

below given code is for bit2 spoj or Search Bit Sum spoj
in the below given code __lg() gives the last bit position of number eg: 7- 111 so last bit position is 2 starting from zero .
and 1LLU << i it means that we are shifting 1 to left by i and then converting it to unsigned long long .
and while loop in main function is actually binary search prototype for searching the number k;
In function totalbit formula for calculating total bit sum i got it from here
this was asked in amazon interview .
#include <stdio.h>
#include <iostream>
using namespace std;
unsigned long long totalbit(unsigned long long n){
    unsigned long long ans = 0;
    int x = 0;
    for(int i = __lg(n); i >= 0; --i)
        if(n & 1LLU << i)
            ans += ((1LLU << i) >> 1) * i + 1 + (1LLU << i) * x++;
    return ans;
}

int main(){
    int t;
    unsigned long long n, l, u, m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%llu",&n);
        l = 0; 
        u = n + 1;
        while(l != u)
        {
            m = (l + u ) / 2;
            if(totalbit(m) >= n) u = m;
            else l = m + 1;
        }
        if(totalbit(l) == n) 
            printf("%llu\n",l);
        else 
            printf("Does Not Exist.\n");
    }
}