Skip to content

Instantly share code, notes, and snippets.

@descorp
Last active October 3, 2017 10:48
Show Gist options
  • Select an option

  • Save descorp/4b7c3d7d0d57e55f7e7bc2f7b1fe976b to your computer and use it in GitHub Desktop.

Select an option

Save descorp/4b7c3d7d0d57e55f7e7bc2f7b1fe976b to your computer and use it in GitHub Desktop.
C# BigNumbers on linked lists: calculating Factorial
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
struct BigNumber
{
LinkedDigit data;
public BigNumber(int value)
{
var input = GetAsRevertDigitArray(value);
data = new LinkedDigit(input[0]);
var current = data;
foreach (var digit in input.Skip(1))
{
current.Next = new LinkedDigit(digit);
current = current.Next;
}
}
public void Multiply(int value)
{
var multiplyer = GetAsRevertDigitArray(value);
var sum = new BigNumber(0);
for (int i = 0; i < multiplyer.Length; i++)
{
var digit = multiplyer[i];
var row = Copy();
var currentDigit = row.data;
while (currentDigit != null) {
currentDigit.Multiply(digit);
currentDigit = currentDigit.Next;
}
row.MoveBy10(i);
sum.Append(row);
}
data = sum.data;
Finalise();
}
public void Append(BigNumber other) {
var currentA = this.data;
var currentB = other.data;
LinkedDigit previousA = null;
while (currentA != null || currentB != null) {
if (currentB == null) {
return;
}
if (currentA != null) {
currentA.Append(currentB.Value);
} else {
currentA = new LinkedDigit(currentB.Value);
previousA.Next = currentA;
}
previousA = currentA;
currentA = currentA?.Next;
currentB = currentB?.Next;
}
}
public void MoveBy10(int times)
{
for (int i = 0; i < times; i++)
{
var temp = data;
data = new LinkedDigit(0);
data.Next = temp;
}
}
public string Print()
{
var result = "";
var current = data;
while (current != null)
{
result = current.Value + result;
current = current.Next;
}
return result;
}
public BigNumber Copy()
{
var result = new BigNumber(data.Value);
var current_new = result.data;
var current = data.Next;
while (current != null)
{
current_new.Next = new LinkedDigit(current.Value);
current = current.Next;
current_new = current_new.Next;
}
return result;
}
void Finalise() {
var current = data;
while (current != null)
{
current.Value += current.Addition;
current = current.Next;
}
}
class LinkedDigit
{
public byte Addition { get; set; }
public byte Value { get; set; }
public LinkedDigit Next { get; set; }
public LinkedDigit(byte value)
{
Value = value;
}
public void Multiply(byte value)
{
var multiplication = Value * value;
var ones = multiplication % 10;
var tens = multiplication / 10;
Value = 0;
Append((byte)ones);
if (tens > 0)
{
if (Next == null)
{
Next = new LinkedDigit(0);
}
Next.Addition += (byte)tens;
}
}
public void Append(byte value) {
var sum = value + Value + Addition;
Addition = 0;
if (sum > 9) {
if (Next == null) {
Next = new LinkedDigit(0);
}
Next.Addition += 1;
Value = (byte)(sum % 10);
} else {
Value = (byte)sum;
}
}
}
}
static byte[] GetAsRevertDigitArray(int value)
{
byte n = 1;
int tens = 10;
while ((value / tens) > 0)
{
n++;
tens *= 10;
}
var result = new byte[n];
for (int i = n - 1; i >= 0; i--)
{
tens /= 10;
result[i] = (byte)(value / tens);
value -= result[i] * tens;
}
return result;
}
static void Main(String[] args)
{
int n = Convert.ToInt32(Console.ReadLine());
var digit = new BigNumber(1);
for (int i = 2; i <= n; i++)
{
digit.Multiply(i);
}
Console.Write(digit.Print());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment