Least Common Multiple - Number Theory
Solution to the "Archery" problem from the "Number Theory" section of "Hacker Earth". The task is to determine the least common multiple of a sequence of numbers.
Daniel Gustaw
• 4 min read
In the Hacker Earth platform, you can find many interesting tasks for programmers.
One of them: “Archery” is presented in this post along with a discussion of the solution.
Problem Statement
Problem
N
archers shoot arrows at targets. There is an infinite number of targets numbered from 1. Archer i
shoots at all targets that are multiples of k_i
.
Find the smallest target hit by all archers.
Input
The first line contains an integer T - the total number of test cases.
Below are T test cases. Each test case has the following format:
The first line contains a natural number - N - the number of archers. The second line contains N integers separated by spaces, where each subsequent number indicates the value of k_i
for the archer.
Output
For each test case, print on a new line the smallest target hit by all archers.
Constraints
1 <= T <= 5
1 <= N <= 15
1 <= k_i <= 48
Explanation
The first archer shoots at targets 2, 4, 6, 8, 10, 12, 14, …
The second archer shoots at targets 3, 6, 9, 12, …
The third archer shoots at targets 4, 8, 12, 16, 20, …
The smallest target that all archers shoot at is 12.
Solution
By taking the story of the archers out of the problem, we are left with the task of finding the least common multiple.
Least common multiple - Wikipedia
Key formulas are:
- Fundamental theorem of arithmetic - every positive integer can be expressed as a unique product of its prime factors with appropriate powers
- The least common multiple (lcm) of a pair of numbers will be calculated using this factorization.
There are ways to calculate lcm
without prime factorization, for example through the relationship with the greatest common divisor (gcd) and the Euclidean algorithm, but we will use prime factorization here.
Algorithm for Finding the Least Common Multiple
- We factor the numbers into products of prime factors,
- We select the maximum multiplicities of the prime factors
- We multiply the prime factors, raising them to the number of their occurrences
We see that the first challenge is to factor the number.
Factorization of a Number into Prime Factors
In this topic, a graphical representation of the algorithm is very helpful.
This algorithm is called “Trial division” and is the least efficient but the simplest to understand factorization algorithm. Other ones are listed here:
Before the implementation, let’s establish a way to record the factorization result. We will use an object where the keys are the factors and the values are the quantities of their occurrences. For example, to record the number 12
which is 2 * 2 * 3
, we will create an object.
{
2: 2,
3: 1
}
The code will be used for factorization calculations.
function divideTimes(n, i) {
let counter = 0;
while(n % i === 0) {
counter++;
n = n / i;
}
return counter;
}
function primeFactors(n) {
if(n === 1) return { 1: 1 };
const res = {};
let p = 2
while(n >= p*p) {
if(n % p === 0) {
res[p] = divideTimes(n,p);
n /= Math.pow(p, res[p]);
} else {
p++
}
}
if(n > 1) {
res[n] = 1;
}
return res;
}
Skipping Repeating Factors in Multiplication
function mergeKeysChoosingMaxValue(prev, next) {
for(let key of Object.keys(next)) {
if(prev.hasOwnProperty(key)) {
prev[key] = Math.max(prev[key], next[key]);
} else {
prev[key] = next[key];
}
}
return prev;
}
Evaluation of the value of a number from its factors
Finally, we want to display numbers to the user rather than their factorization, so we will switch from the factored format to the pure numerical value.
function evaluate(object) {
return Object.keys(object).reduce((prev, key) => {
return prev * Math.pow(Number(key), object[key]);
},1)
}
Integration of the solution with the program’s input and output format
We still need to connect the components we wrote to the input and output format required by the task. The first part of the code reads data from the standard stream and runs the main
function on it.
process.stdin.resume();
process.stdin.setEncoding("utf-8");
let stdin_input = "";
process.stdin.on("data", function (input) {
stdin_input += input;
});
process.stdin.on("end", function () {
main(stdin_input);
});
The second part consists of code processing lines of text into arrays of numbers in the main
function and performing the task in the minCommonDiv
function.
function minCommonDiv(k) {
const factorized = k.map(primeFactors);
return evaluate(factorized.reduce(mergeKeysChoosingMaxValue))
}
function main(input) {
const lines = input.split('\n').filter(line => Boolean(line));
const T = Number.parseInt(lines.shift());
const out = [];
for(let i=0; i<T; i++) {
lines.shift();
const k = lines.shift().split(/\s+/).map(n => Number.parseInt(n));
const res = minCommonDiv(k);
out.push(res);
}
process.stdout.write(out.join("\n") + "\n");
}
The program assuming that we will save the input to input.txt
and the program to app.js
, we can check our solution with the command:
cat input.txt | node app.js
Other articles
You can find interesting also.
Scraping WordPress - 4300 court rulings in exchange rate lawsuits without a line of code
It is not often that the execution of a service takes longer than its pricing, but with scraping, this can happen. See how easy it can be to retrieve data, especially from WordPress.
Daniel Gustaw
• 2 min read
Fetch, Promise and Template String on example of To Do List in JavaScript
This simple project is great as an introduction to JavaScript programming. The emphasis is on ES6 elements and the frontend.
Daniel Gustaw
• 13 min read
Login by Metamask - Rest Backend in Fastify (Node, Typescript, Prisma)
We building from scratch rest api in fastify using mongodb connected by prisma as database, jest as test framework and etherjs to verify signatures signed by metamask.
Daniel Gustaw
• 21 min read