Last active
October 3, 2017 10:48
-
-
Save descorp/4b7c3d7d0d57e55f7e7bc2f7b1fe976b to your computer and use it in GitHub Desktop.
C# BigNumbers on linked lists: calculating Factorial
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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