Skip to main content

Posts

Showing posts from February, 2018

Bitwise Sieve w/ code sample

Sieve of Eratosthenes is explained HERE Bitwise sieve is an optimized implementation of  Sieve of Eratosthenes. It does the same thing but more memory efficient because it uses logic operations( &,|,>>,<< ) on binary numbers. In normal implementation, we use an array as flag to check if a number is prime or not.we know index of an array ( i.e  myarray[n]  ) is 32 bit long. If an array is 10 index long, that it has 32x10(=320) bits.  We use bits of that array as flag. that way we can flag numbers upto 320 as prime or not prime. i.e, how to check the flag status of 51 in myarray[ n ] ? We'll divide 5 by 32, that will give us the index number of the certain bit, then we'll mod 5 by 32, that will give us the certain bit position to check for 0 or 1. Remember bit positions are defined from right to left, starting from 0. Meaning LST = 0 and MST = 31. So we need to define two functions, one to set that certain bit as 0 or 1, another to check if  bit is 0 or

SPOJ 3410 - SAMER08F - Feynman

Problem Statement Explanation:   How many squares a (4x4) square holds? the answer is- 16 (1x1) squares + 4 (2x2) squares, 9 (3x3) squares, 1 (4x4) squares Meaning, the answer is n²+ (n-1)²+(n-2)²+.......+1² which is also equivalent to    Solution: #include<stdio.h> int main() {     int n,x;     while(scanf("%d",&n)&&n!=0)     {         x=(n*(n+1)*((2*n)+1))/6;         printf("%d\n",x);     }     return 0; }  

SPOJ 1112 - NSTEPS

Problem Statement Explanation : This might seem like a math problem. But it's not. There's a pattern in here. Firstly, figure out when output has no number. If you can figure it out then try to recognise the relation of the output with co-ordinates (x, y) Solution is given below: #include<stdio.h> int main() {     int t,x,y;     scanf("%d",&t ) ;     while(t--&&t>=0)     {         scanf("%d%d",&x,&y);         if(y==x||y==x-2)         {             if(x%2==0) printf("%d\n",x+y);             else printf("%d\n",x+y-1);         }         else         {             printf("No Number\n");         }     } }