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

Code Kata(link)

http://codekata.pragprog.com/

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]);

Console.ReadKey();

}

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));
            Console.ReadKey();
        }

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