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;
}

Factorial factorization

This function calculates the factorization of the given number's factorial.

int factors(int num)
{
    int i,tmp,cnt;
    
    for(i=0;i<max_prime && prime[i]<=num;i++)
    {
        cnt=0;
        tmp=num;
        cout<< prime[i] << " ";
        while(tmp>0)
        {
            cnt+=floor(tmp/prime[i]);
            tmp/=prime[i];
        }
        cout<< cnt << endl;
    }
}

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.

Negative Base Conversion

Though, First time it may be a surprising fact that, "NEGATIVE BASE!!!", But it really exists. :)
Here goes it.Click Here for details.

NegaTernary(-3) Base conversion python implementation:

def negaternary(i):
    digits = []
    while i != 0:
        i, remainder = divmod(i, -3)
        if remainder < 0:
            i, remainder = i + 1, remainder + 3
        digits.insert(0, str (remainder))
    return ''.join(digits)

And Here is NegaBinary(-2) Base conversion in C:

#include<stdio.h>
int main()
{
	char a[100];
	int num,temp;

	while(~scanf("%d",&num))
	{
	while(num!=0)
	{
		temp=num%(-2);
		num/=(-2);
        if(temp < 0)
		{
			num+=1;
			temp+=2;
		}
		printf("%d ",temp);
	}
	puts("");
	}

	return 0;
}

Any Base Conversion

C++ implementation of Any Base to Any Base Conversion.

#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define all(x) x.begin(),x.end()

template<class t> inline t power(t num,t p)
{
    if(!p)    return 1;return (num*power(num,p-1));
}

bool islow(char ch){if(ch>='a' && ch<='z') return true; return false;}
bool isupp(char ch){if(ch>='A' && ch<='Z') return true; return false;}
bool isdig(char ch){if(ch>='0' && ch<='9') return true; return false;}

//any base to decimal conversion
int todec(string s,int base)
{
    int i,j,temp,len,sum=0;

    len=s.length()-1;
    for(i=0,j=len;i<=len;i++,j--)
    {
        char ch=s.at(i);
        if(isdig(ch))         temp=ch-'0';
        else if(islow(ch))    temp=10+ch-'a';
        else if(isupp(ch))    temp=10+ch-'A';

        sum+=(temp*(power(base,j)));
    }

    return sum;
}


//decimal to any base conversion
string tobase(int num,int base)
{
    int temp;
    string s;
    char ch;
    if(!num)    return "0"; //special '0' case handling

    while(num>0)
    {
        temp=num%base;
        num/=base;
        if(temp<=9) s+=(temp+'0');
        else        s+=((temp-10)+'A');
    }
    reverse(all(s));
    return s;
}

Binary to Decimal and Decimal to Binary conversion

Here is a short code for Binary to Decimal Conversion-

int to_dec(string str)
{
    int num=0,i;
    int mask=1;

    for(i=str.length()-1;i>=0;i--)
    {
        if(str.at(i)=='1')
            num|=mask;
        mask<<=1;
    }

        cout << num << endl;
    
    return num;
}

And a short code for Decimal to Binary Conversion-

string to_bin(int num)
{
    string str="";
    int mask=1;

    while(num)
    {
        if(num&mask)
            str="1"+str;
        else
            str="0"+str;

        num>>=1;
    }

    cout << str << endl;
    return str;
}