Josephus Recurrence

Famous Josephus's problem solution.

Recursive solution:

int josephus(int n, int m)   
{   
 if (n == 1)  
      return 0;   
 return (josephus (n-1, m) + m) % n;   
}

Iterative solution:

ans=0;
for(i=2;i<=n;i++)
{
 ans=(ans+m)%i;
}

when m=2, then the following will be useful. Found it here.

int f(int n) 
{
    if(n == 1) return 1;
    return (f((n-(n&1))>>1)<<1) + ((n&1)?1:-1);
}

Extended euclid algorithm

While the euclidean algorithm simply finds the greatest common divisor of two numbers a and b, The extended euclidean algorithm finds the GCD also factors in addition to x and y such that:

That is, it finds the coefficients by which the GCD of two numbers expressed in terms of the numbers themselves.
Details can be found here and here.

Implementation of extended euclidean algorithm-

int gcd ( int a, int b, int & x, int & y ) {
	if ( a == 0 ) {
		x = 0 ; y = 1 ;
		return b ;
	}
	int x1, y1 ;
	int d = gcd ( b % a, a, x1, y1 ) ;
	x = y1 - ( b / a ) * x1 ;
	y = x1 ;
	return d ;
} 

This is a recursive function, which still returns the GCD of the numbers a and b, But apart from that- the value of x and y passed as reference to the function.

Here is another c++ implementation which uses class to handle the value of x,y and d.  I found it here.

class Euclid {
public:
    i64 x, y, d;
    Euclid() {}
    Euclid(i64 _x, i64 _y, i64 _d) : x(_x), y(_y), d(_d) {}
};
 
Euclid egcd(i64 a, i64 b) {
    if(!b) return Euclid(1, 0, a);
    Euclid r = egcd(b, a % b);
    return Euclid(r.y, r.x - a / b * r.y, r.d);
}

Big Mod

Big Mod algorithm simply use the modular arithmetic to find the value of-

(a^p)%m.

Big Mod recursive approach-

int bigmod ( long long a, int p, int m )
{
    if ( p == 0 )return 1; // If power is 0 ( a ^ 0 ), return 1

    if ( p & 1 ) // If power is odd
    {
        return ( ( a % m ) * ( bigmod ( a, p - 1, m ) ) ) % m;
    }
    else
    {
        long long tmp = bigmod ( a, p / 2, m ); 
        return ( tmp * tmp ) % m;
    }
}

Big Mod Iterative approach-

long long bigmod ( long long a, long long p, long long m )
{
    long long res = 1;
    long long x = a;
    
    while ( p )
    {
        if ( p & 1 ) //p is odd
        {
            res = ( res * x ) % m;
        }
        x = ( x * x ) % m;
        p = p >> 1;
    }

    return res;
}

Last non-zero digit of factorial

To find the last non-zero digit of a factorial number, the idea is to remove the extra zeroes in every step multiplying the numbers and don't need to hold the whole big number, just a small digit numbers from the last non-zero digits.
Here goes the code-

#include<stdio.h>
int main()
{
    long long int ans;
        int num;
        scanf("%d",&num);
 
        ans=1;
        for(int i=2;i<=num;i++)
        {
                ans=ans*i;
 
                while(ans%10==0)
                {
                        ans/=10;
                }
                ans%=10000000;
        }
        printf("%lld\n",ans%10);
 
        return 0;
}

Trailing zero in factorial

Finding number of trailing zero in factorial-

#include <stdio.h>
int main()
{
	int n,total,deno;
        scanf("%d",&n);
		
	total=0;
	deno=5;
	while(deno<=n)
	{
		total+=n/deno;
		deno*=5;
	}
	printf("%d\n",total);

	return 0;
}

Sum of Divisors of a Number

Sum of divisors of a Number can be found by the following formula.

Now the code. Following function calculate sum of divisors of a number-

#define i64 long long

i64 power(i64 N,i64 P)
{
	i64 sum=1,i;
	
	if(P==0)return 1;
	else
	{
		for(i=1;i<=P;i++)
			sum=sum*N;
		return sum;
	}
}

i64 sumofdivisor(i64 n)
{
	i64 sum=1,i,count;
	i64 sq=(i64)sqrt(n);
	
	for(i=0;prime[i]<=sq;i++)
	{
		count=0;
		while(n%prime[i]==0)
		{
			count++;
			n/=prime[i];
		}
		sum*=(i64)(power(prime[i],count+1)-1)/(prime[i]-1);
	}
	if(n>1)
		sum*=(n+1);
	return sum;
}

Bitwise sieve

Here is an implementation of Bitwise sieve. For full explanation See this and this-

#define MAX 100000000//max num to prime
#define LMT 10000 //sqrt(MAX)

int flag[MAX/64];
int prime[100000000],total;

#define chkC(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define setC(n) (flag[n>>6]|=(1<<((n>>1)&31)))

void sieve() 
{
	unsigned i,j,k;

	flag[0]|=0;
	for(i=3;i<LMT;i+=2)
		if(!chkC(i))
			for(j=i*i,k=i<<1;j<MAX;j+=k)
				setC(j);

	prime[(j=0)++] = 2;//prime starts from 0 position
	for(i=3;i<MAX;i+=2)
		if(!chkC(i))
		{
			prime[j++] = i;
			//printf("%d\n",primes[j-1]);
		}
	total = j-1;
}

Number of divisor

To find the number of divisors of a number, first calculate find by sieve and then try this-

int number_of_divisor(int num)
{
 int j,count,div=1;
 for(j=0;prime[j]<=sqrt(num);j++) //prime array holds the prime numbers
 {
  count=0;
  while(num%prime[j]==0)
  {
   count++;
   num/=prime[j];
  }
  div*=(count+1);
 }
 if(num>1)
  div<<=1;
 return div;
}

This function returns the number of divisors of the given number.

Number of digits in factorial

This program calculate how many digit in factorial of the number in given base
Anyone can just calculate number of digits in decimal, then b=10 always.

#include <stdio.h>
#include <math.h>
int main()
{
	int number,i,base,digit;
	double c,a=0;

	printf("Give the base and the number: ");
	scanf ("%d%d",&base,&number);

	c=log10(base);
	for (i=number;i>=1;i--) {

		a+=(log10(i))/c; 
	}
	digit=a+1;
	printf ("%d\n",digit);

	return 0;
}

Sieve of Eratosthenes (Prime Finding)

The most popular prime finding method aka Sieve of Eratosthenes.

#define MAX 35000
#define lim 200

bool a[MAX];
int prime[MAX];

void sieve()
{
	int i,j;
	a[0]=1;a[1]=1;          //1 denotes not prime

	for(i=3;i<=lim;i+=2)    //even numbers are exclusive
	{
		if(a[i]==0)     //0 denotes prime
		{
			for(j=i*i;j < MAX;j+=i)
				a[j]=1;
		}
	}

	prime[0]=2;
	j=1;
	for(i=3;i < MAX;i+=2)     //even numbers are exclusive
	{
		if(a[i]==0)
			prime[j++]=i;
	}
}

GCD (Greatest Common Divisor)

Here are 3 different code for GCD, But the main Idea is always same-

//iterative gcd
int gcd ( int a, int b )
{
  int c;
  while ( b != 0 ) {
     c = b; b = a%b;  a = c;
  }
  return b;
}


//bitwise gcd
int gcd(int a, int b)
{

//actually this code is same as the previous
while(b) 
		b ^= a ^= b ^= a %= b;  //b^=a^=b^=a means swap(a,b)

return a;
}


//recursive gcd
int g_c_d(int a,int b)
{
	if(b==0)
		return a;
	else 
		return g_c_d(b,a%b);
}

Here is another short version of gcd using ternary operators:

int gcd ( int a, int b ) {
	return b ? gcd ( b, a % b ) : a ;
}