# Euler 1

/// <summary>

/// If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9.

/// The sum of these multiples is 23.Find the sum of all the multiples of 3 or 5 below 1000.

/// </summary>

var val = Enumerable.Range(0, 1000).Sum( o => ( (o % 3 == 0) || (o % 5 == 0) ) ? o : 0 );

# List based on an array implementation

public class ArrayList<T>
{
T[] _innerArray = new T[4];
int _size = 0;

private void ResizeIfItNeeds()
{
if (_innerArray.Length == _size)
Array.Resize<T>(ref _innerArray, _size * 2);
}

private bool IsRangeValid(int position)
{
return ((position >= 0) && (position <= _size));
}

public int Count
{
get { return _size; }
}

public void InsertAt(T element, int position)
{
if (!IsRangeValid(position))
throw new ArgumentOutOfRangeException();

ResizeIfItNeeds();

Array.Copy(_innerArray, position, _innerArray, position + 1, _size – position);
_innerArray[position] = element;
_size++;
}

public T GetElementAt(int position)
{
if (!IsRangeValid(position))
throw new ArgumentOutOfRangeException();

return _innerArray[position];
}

public long RemoveAt(int position)
{
if (!IsRangeValid(position))
throw new ArgumentOutOfRangeException();

Array.Copy(_innerArray, position + 1, _innerArray, position, _size – position + 1);
return _size–;
}

public int GetPosition(T element, int startIndex, int length)
{
if (!IsRangeValid(startIndex + length) || !IsRangeValid(startIndex))
throw new ArgumentOutOfRangeException();

if (length == 1)
{
if (Object.Equals(element, _innerArray[startIndex]))
return startIndex;
else return -1;
}

int lastIndex = startIndex + length – 1;
int rangeSize = startIndex + length / 2;

int i = startIndex;
int j = 0;
for (; i <= rangeSize; i++, j++)
{
if (Object.Equals(_innerArray[i], element))
return i;
if (Object.Equals(_innerArray[lastIndex – j], element))
return lastIndex – j;
j++;
}
return -1;
}

public void Clear()
{
Array.Clear(_innerArray, 0, _innerArray.Length);
}
}

# Getting GCD (based on division by 2 algorithm)

/// <summary>
/// Getting greatest common divisor by using next his properties:
/// GCD(2a, 2b) = 2 x GCD(a,b) and GCD(2a, b) = GCD(a, b), if b is odd digit.
/// </summary>
private static int GetGCD(int a, int b)
{
int m = a;
int n = b;
int d = 1;
while( ! ((m == 0) || (n ==0)) )
{
if ( (m % 2 == 0) && (n % 2 == 0) )
{
m/=  2;
n/= 2;
d *= 2;
}
else if (m % 2 == 0)
{
m/= 2;
}
else if (n % 2 == 0)
{
n/= 2;
}
else
{
if (m >= n)
m = m – n;
else
n = n – m;
}
}
if (m != 0)
return m * d;
else return n * d;
}

# Getting gcd and lcm at the same time

/// <summary>
/// We can get both least common multiple and greatest common divisor
/// at the same time. By using that m*u + n*v has constant value and at the start time
/// m*u + n*v = 2*a*b and LCM(a, b) = a * b / GCD(a, b). If m = 0 or n = 0 then n is GCD
/// or m is GCD, so we can get lcm by division v by 2 or u by 2;
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
private static int[] GetLCMandGCD(int a, int b)
{
int m = a;
int n = b;
int u = b;
int v = a;
int []result = new int[2];
while(! ( (m == 0) || (n == 0) ) )
{
if (m >= n)
{
m = m – n; v = v + u;
}
else
{
n = n – m; u = u + v;
}
}
if (m == 0)
{
result[0] = v / 2;
result[1] = n;
}
else
{
result[0] = u /2;
result[1] = m;
}
return result;
}

# Least common multiple

/// <summary>
/// lcm(a, b) = a * b / gcd(a, b)
/// </summary>
private static int GetLCM(int a, int b)
{
return a * b / GetGCD(a, b);
}

private static int GetGCD(int a, int b)
{
if (b == 0)
return a;
return GetGCD(b, a % b);
}

# Extended Euclidean algorithm

static void Main(string[] args)
{
//Solving ax + by = gcd(a, b);
int[] result = SolveByIterativeExtendedEuclideanAlgorithm(21, 9);
Console.WriteLine("Iterative result: x:{0}, y:{1}", result[0], result[1]);
result = SolveByRecursiveExtendedEuclideanAlgorithm(21, 9);
Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);
result = SolveByIterativeExtendedEuclideanAlgorithm2(21, 9);
Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);
}

/// <summary>
/// Extended Euclidean algorithm
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
/// <returns></returns>
private static int[] SolveByIterativeExtendedEuclideanAlgorithm(int a, int b)
{
//Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
int lastX = 1, x = 0;
int lastY = 0, y = 1;
int temp = 0;
int quotient = 0;
while(b != 0)
{
temp = b;
quotient = a / b;
b = a % b;
a = temp;
//Compute xi+1= xi-1- qixi
temp = x;
x = lastX – quotient * x;
lastX = temp;
//Compute yi+1= yi-1- qiyi
temp = y;
y = lastY – quotient * y;
lastY = temp;
}
//The answers are the second-to-last of xn and yn.
return new int[] { lastX, lastY };
}

/// <summary>
/// Extended Euclidean algorithm
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
/// <returns></returns>
private static int[] SolveByRecursiveExtendedEuclideanAlgorithm(int a, int b)
{
// If a is divisible by b, the algorithm ends and return the trivial solution x = 0, y = 1.
if ((a % b) == 0)
return new int[] { 0, 1 };
//Otherwise, repeat the algorithm with b and a modulus b, storing the solution as x’ and y’.
int[] result = SolveByRecursiveExtendedEuclideanAlgorithm(b, a % b);
//Then, the solution to the current equation is x = y’, and y = x’ minus y’ times quotient of a divided by b
return new int[] {result[1], result[0] – a / b * result[1] };
}

private static int[] SolveByIterativeExtendedEuclideanAlgorithm2(int a, int b)
{
int m = a;
int n = b;
int p = 1;
int q = 0;
int r = 0;
int s = 1;
while (! ((m == 0) || (n == 0)) )
{
if (m >= n)
{
m = m – n;
p = p – r;
q = q – s;
}
else
{
n = n – m;
r = r – p;
s = s – q;
}
}
if (m == 0)
{
return new int[] { r, s};
}
else
{
return new int[] { p, q};
}
}

# 3 ways to get greatest common divisor (gcd)

static int GetGCD(int a, int b)
{
int k = a;
if (a > b)
k = b;
while (! ((a%k == 0) && (b%k == 0)))
k–;
return k;
}

static int GetGCDByEuclidean(int a, int b)
{
if (a > b)
return InternalGetGCDByEaclidean(a, b);
else return InternalGetGCDByEaclidean(b, a);
}

static int InternalGetGCDByEaclidean(int g, int s)
{
if (s == 0)
return g;
return InternalGetGCDByEaclidean(s, g % s);
}

static int GetGCDByEuclidean2(int a, int b)
{
while(!((a == 0)||(b == 0)))
{
if (a > b)
a = a – b;
else b = b – a;
}
if (a != 0)
return a;
else return b;
}

# Sum of 1/1! + 1/2! + … + 1/n!

/// <summary>
/// O(n) algorithm for calculation Sum of 1/0! + 1/1! + 1/2! + … + 1/n!
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
private static double SumOfDivFactorial(int n)
{
double sum = 1.0d;
double temp = 1;
int i = 1;
while (i < n + 1)
{
temp *= i;
sum += 1.0d / temp;
i++;
}
return sum;
}

# Calculating Fibonacci Numbers

/// <summary>
/// O(Log2N) time algorithm for calculation of N Fibonacci’s number
/// F(n) = F(n-1) + F(n-2) where F(0) = 0 and F(1) = 1.
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
Console.WriteLine(GetN(10));
}
/// <summary>
/// A 2-dimensional system of linear difference equations that describes the Fibonacci sequence is
/// |Fk+2|   |1 1|  |Fk+1|
/// |       | = |    |x|       |
/// |Fk+1|   |1 0|  |Fk    |
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
private static int GetN(int number)
{
if (number == 0) return 0;
if (number == 1) return 1;
number -= 2;
int[,] result = new int[2, 2] { { 1, 1 }, { 1, 0 } };
int[,] even = new int[2, 2] { { 1, 1 }, { 1, 0 } };
while (number != 0)
{
if ((number % 2) == 0)
{
even = Multiply(even, even);
number /= 2;
}
else
{
result = Multiply(result, even);
number–;
}
}
return result[0, 0];
}

/// <summary>
///           n
/// Ci,j =  Σ Ai,r * Br,j = Ai,1 * B1,j + Ai,2 * B2,j + … + Ai,n * Bn,j;
///          r=1
/// </summary>
/// <param name="first"></param>
/// <param name="second"></param>
/// <returns></returns>
private static int[,] Multiply(int[,] first, int[,] second)
{
int[,] result = new int[2, 2];
result[0, 0] = first[0, 0] * second[0, 0] + first[0, 1] * second[1, 0];
result[0, 1] = first[0, 0] * second[0, 1] + first[0, 1] * second[1, 1];
result[1, 0] = first[1, 0] * second[0, 0] + first[1, 1] * second[1, 0];
result[1, 1] = first[1, 0] * second[0, 1] + first[1, 1] * second[1, 1];
return result;
}