Grade 12 · 9 algorithmsCitește în română

Big numbersNumere mari

Every big numbers algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

9algorithms
6chapters
1grade

Big numbers

Numere mari · 9 algorithms

Adding two big numbersAdunarea a două numere mariWe add as on paper, from the units to the left. At position i we compute s = a[i] + b[i] + carry; the result digit is s % 10, and the new carry is s…O(n)
Reading and printing a big numberCitirea și afișarea unui număr mareA number with tens or hundreds of digits does not fit in long long, so we read it as a string and keep its digits in an array, starting with the…O(n)
Comparing two big numbersCompararea a două numere mariWithout leading zeros, the number with more digits is larger. If they have the same number of digits, we compare them from the most significant…O(n)
Factorial as a big numberFactorialul unui număr mareAlready 21! exceeds long long, but n! = 1 * 2 * ... * n can be built by repeatedly multiplying a big number by a small one. We start from the array…Exponential
The n-th Fibonacci term (big number)Termenul n din șirul lui Fibonacci (număr mare)The sequence is F(1) = F(2) = 1 and F(i) = F(i - 1) + F(i - 2). The terms grow exponentially (F(93) no longer fits in long long), so we keep them as…O(n²)
Dividing a big number by a small numberÎmpărțirea unui număr mare la un număr micUnlike addition, division starts from the most significant digit, exactly like long division on paper. We keep the remainder r; for every digit we…O(n)
Multiplying two big numbersÎnmulțirea a două numere mariThe digit a[i] (rank 10^i) multiplied by the digit b[j] (rank 10^j) contributes to rank 10^(i+j). We first add all the products into c[i + j],…O(n)
Multiplying a big number by a small numberÎnmulțirea unui număr mare cu un număr micThe small number k (at most 10^9) fits in an int, so it does not need to be split into digits. For every digit a[i], from the units, we compute t =…O(n)
Subtracting two big numbersScăderea a două numere mariWe compute A - B. If A < B, we compute B - A and put a minus sign in front. We subtract from the units: d = a[i] - b[i] - borrow; if d comes out…O(n)