The Euclidean algorithm is a well-known algorithm to find Greatest Common Divisor of two numbers. Below is a possible implementation of the Euclidean algorithm in C++: int gcd(int a, int b) { while (b != 0) { int tmp = a % b; a = b; b = tmp; } return a; } Time complexity […]
https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/practice-problems/algorithm/riyas-birthday-party-1/ Summary of problem statement A sequence $a$ is generated as follows: $a_1 = 1$ $a_2 = 6$ $a_i = (a_{i-1} + a_{i+1})/2 – 2, \forall i \geq 2$. Given $n$ ($1 \leq n \leq 10^{18}$), calculate $a_n \mod (10^9+ 7)$. O(n) solution Using properties of equalities, we convert: $a_i=(a_{i-1} + a_{i+1})/2 – 2$ to: […]
https://leetcode.com/problems/cat-and-mouse/ We can present every state of the game with a tuple (m, c, t) where m is the current position of the mouse, c is the current position of the cat, turn is 0 if it is the mouse’s turn and 1 if it is the cat’s turn to move. All states of the […]
Divided Apples is an interesting problem. If you find the editorial difficult to understand, have a look at my explanation below: Transform a circle into all zeros Let’s call a[i] the number of apples the ith boy has. First, it is common sense to calculate the average of a and subtract every a[i] to this […]
My company uses a tool similar to pylint to enforce coding standard for our Python codebase. Today it gave the following error when I tried adding comments to a method: Line 33: Docstring summary should be on one line and followed by a blank line. I looked it up and to my surprise, it is […]
Occasionally we want to sort a list of elements or maintain a set of elements with comparator that involves accessing another list. A popular use case is rather than sorting a list of N objects, we create a list of indexes [0, 1, 2, …, N-1] and sort this list instead. Another use case is […]