# TheAlgorithms

Documentation for TheAlgorithms.

TheAlgorithms.Basic.prefix_sumMethod
prefix_sum(arr::Vector{<:Number})

Brief

Given an input array of numbers, return an array of the sum of each "prefix" of the input array i.e. the 1st element, 1st + 2nd element, 1st + 2nd + 3rd, etc.

This functionality is available in base Julia as cumsum.

Arguments

• arr: an array of numbers

Examples

julia> prefix_sum([1, 2, 3])
3-element Vector{Int64}:
1
3
6

julia> prefix_sum([0.0, 10.0, π])
3-element Vector{Float64}:
0.0
10.0
13.141592653589793
source
TheAlgorithms.Basic.DifferenceArrayModule
Difference array

Brief:

For any array A with N numbers, we can create difference array D with N numbers also.
Every k-th element of D is equal to difference between A[k] and A[k-1]
D[k] = A[k-1] - A[k]

Complexity of some operations

- add some value x to the m consecutive elements of array - O(1)
- print array after any numbers of changes                - O(N)

Functions

- create_diff_arr(original::Array{<:Number})
* Create difference array for array 'original'
- calculate_arr(diff_arr::Array{<:Number})
* Recreate the original array from the given difference array
* Add x to all elements with index from [l, r]

Contributed by: Nikola Mircic

source
TheAlgorithms.Cipher.affineMethod
affine(text, alphabet, nMultiply, nAdd)

Program to implement affine cipher for the given input. A full description of it can be found on wikipedia.

Arguments:

• text : text to be encoded/decoded
• alphabet : the alphaebt the text uses
• nMultiply : the number to the multiply by (a)
• nAdd : the number to add (b)

Examples/Tests


julia> affine("abcdefghijklmnopqrstuvwxyz", "abcdefghijklmnopqrstuvwxyz", 3, 1)

julia> affine("whyhellothere", "abcdefghijklmnopqrstuvwxyz", 17, 82)
"otwtujjiptuhu"

julia> affine("1234", "0123456789", 5, 2)
"9630"


Algorithm:

As usual, julia's 1 based indexing doesn't play nicely with the affine cipher, but all that is required is -1 from the initial index of the letter and +1 after the mod.

An affine cipher uses a simple function: f(x) = ax + b.

Notes:

• nMultiply and length(alphabet) must be coprime so that the two plaintext letters are not substituted for the same cipehrtext letter.
• This doesn't check that the all of the characters in text actually are in alphabet, but that does need to be the case!

join([
alphabet[((findfirst(isequal(letter), alphabet) - 1) * nMultiply + nAdd) % length(alphabet) + 1]
for letter in text
])


References:

https://www.dcode.fr/affine-cipher https://github.com/Squalm/Cipher-Tools

Contributed by: Chirp (Squalm)

source
TheAlgorithms.Cipher.atbash_encodeMethod

encode(input)

Program to implement atbash cipher for the given sentence.A full description of the algorithm can be found on wikipedia

Arguments:

• input : The sentence needed to rotate

Examples/Tests

julia> atbash_encode("test")
gvhg

julia> atbash_encode("abcdefghijklmnopqrstuvwxyz")
zyxwvutsrqponmlkjihgfedcba

julia> atbash_encode("hello")
svool


Algorithm:


for r in input
part *= xform(r)
if length(part) >= 5
push!(parts, part)
part = ""
end
end
if part != ""
push!(parts, part)
end
return join(parts, " ")


References:

https://en.wikipedia.org/wiki/Atbash



Contributed by:- Ihjass Thasbekha

source
TheAlgorithms.Cipher.caesarMethod
caesar(rot, s)

Program to implement rotational cipher for the given sentence. A full description of the algorithm can be found on wikipedia

Arguments:

• rot: The number of rotations needed.
• s : The sentence needed to rotate

Examples/Tests

julia> caesar(13,"abcdefghijklmnopqrstuvwxyz")
nopqrstuvwxyzabcdefghijklm

julia> caesar(5,"omg")
trl

julia> caesar(0,"hello")
hello


Algorithm:


if r >= 'a' && r <= 'z'
v = ((r - 'a') + rot) % 26
return v + 'a'
end
if r >= 'A' && r <= 'Z'
v = ((r - 'A') + rot) % 26
return v + 'A'
end
return r


References:

https://en.wikipedia.org/wiki/Caesar_cipher



Contributed by:- Ihjass Thasbekha

source
TheAlgorithms.Cipher.decrypt_vigenereMethod
decrypt_vigenere(text, key)

Decrypts a plaintext message using the Vigenere cipher.

Arguments

• text: the ciphertext message to decrypt
• key: the keyword used for decryption

Examples

julia> decrypt_vigenere("Rijvs, Uyvjn!", "key")
Hello, World!
source
TheAlgorithms.Cipher.encrypt_vigenereMethod
encrypt_vigenere(text, key)

Encrypts a plaintext message using the Vigenere cipher.

Arguments

• text: the plaintext message to encrypt
• key: the keyword used for encryption

Examples

julia> encrypt_vigenere("Hello, World!", "key")
Rijvs, Uyvjn!
source
TheAlgorithms.Conversions.celsius_to_fahrenheitFunction

celsiustofahrenheit(celsius, ndigits::Int = 2)

Converts celsius to fahrenheit and round to 2 decimal places

Example

celsius_to_fahrenheit(273.354, 3) == 524.037  # returns true
celsius_to_fahrenheit(273.354, 0) == 524.0    # returns true
celsius_to_fahrenheit(-40.0) == -40.0         # returns true
celsius_to_fahrenheit(-20.0) == -4.0          # returns true
celsius_to_fahrenheit(0) == 32.0              # returns true
celsius_to_fahrenheit(20) == 68.0             # returns true
source
TheAlgorithms.Conversions.celsius_to_kelvinFunction

function celsiustokelvin(celsius, ndigits::Int = 2)

Converts celsius to kelvin and round to 2 decimal places

Example

celsius_to_kelvin(273.354, 3) == 546.504    # returns true
celsius_to_kelvin(273.354, 0) == 547.0      # returns true
celsius_to_kelvin(0.0) == 273.15            # returns true
celsius_to_kelvin(20.0) == 293.15           # returns true
source
TheAlgorithms.Conversions.fahrenheit_to_celsiusFunction

fahrenheittocelsius(fahrenheit, ndigits::Int = 2)

Converts fahrenheit to celsius and round to 2 decimal places

Example

fahrenheit_to_celsius(273.354, 3) == 134.086 # returns true
fahrenheit_to_celsius(273.354, 0) == 134.0   # returns true
fahrenheit_to_celsius(0.0) == -17.78         # returns true
fahrenheit_to_celsius(20.0) == -6.67         # returns true
fahrenheit_to_celsius(40.0) == 4.44          # returns true
fahrenheit_to_celsius(60.0) == 15.56         # returns true
fahrenheit_to_celsius(80.0) == 26.67         # returns true
source
TheAlgorithms.Conversions.fahrenheit_to_kelvinFunction

fahrenheittokelvin(fahrenheit, ndigits::Int = 2)

Converts fahrenheit to kelvin and round to 2 decimal places

Example

fahrenheit_to_kelvin(273.354, 3) == 407.236 # returns true
fahrenheit_to_kelvin(273.354, 0) == 407.0   # returns true
fahrenheit_to_kelvin(0) == 255.37           # returns true
fahrenheit_to_kelvin(20.0) == 266.48        # returns true
fahrenheit_to_kelvin(40.0) == 277.59        # returns true
fahrenheit_to_kelvin(60.0) == 288.71        # returns true
fahrenheit_to_kelvin(80.0) == 299.82        # returns true
source
TheAlgorithms.Conversions.kelvin_to_celsiusFunction

function kelvintocelsius(kelvin, ndigits::Int = 2)

Converts kelvin to celsius and round to 2 decimal places

Example

kelvin_to_celsius(273.354, 3) == 0.204   # returns true
kelvin_to_celsius(273.354, 0) == 0.0     # returns true
kelvin_to_celsius(273.15) == 0.0         # returns true
kelvin_to_celsius(300) == 26.85          # returns true
source
TheAlgorithms.Conversions.kelvin_to_fahrenheitFunction

function kelvintofahrenheit(kelvin, ndigits::Int = 2)

Converts kelvin to fahrenheit and round to 2 decimal places

Example

kelvin_to_fahrenheit(273.354, 3) == 32.367  # returns true
kelvin_to_fahrenheit(273.354, 0) == 32.0    # returns true
kelvin_to_fahrenheit(273.15) == 32.0        # returns true
kelvin_to_fahrenheit(300) == 80.33          # returns true
source
TheAlgorithms.DataStructure.BinaryHeapType
BinaryHeap{T,HT}

A heap data structures implemented as a binary tree. It can be instantiated either as a MinHeap or MaxHeap. In a MinHeap each element in the tree is smaller than its children, and similarly, in a MaxHeap each element is greater than its children, this is called "Heap Property".

One of the most common usage of the Heaps is as a Priority Queue. Note that the element with highest priority will always be at the root of the tree.

In this implementation, the tree is store in a Vector where the first element (index = 1) is the root and for all elements, it's children will be at index * 2 and index * 2 + 1. The methods are implemented just once for both min and max heap, and it relies on the multiple dispatch of the isbefore function that will depend on the heap type.

Functions:

• MinHeap{T}/MaxHeap{T}: constructors
• push!(heap, elements...): push elements into the heap
• top(heap): get the top element (smaller in a MinHeap, greater in a MaxHeap)
• pop!(heap): get top element and remove it from the heap
• isempty(heap): wheter theres no elemets in the heap
• length(heap): how many elements are in the heap

Example

heap = MinHeap{Int}()
push!(heap, 4, 2, 3, 1, 5)
while !isempty(heap)
println(pop!(heap))
end

# output

1
2
3
4
5

Complexities:

• Space: O(n)
• Get top element: O(1)
• Push a element: O(log n)
• Pop a element: O(log n)
• Get number of elements: O(1)

Contributed By: Gabriel Soares

source
TheAlgorithms.DataStructure.LinkedListModule

Brief:

A linked list is a data structure where each element is connected to the next one.

Complexity of some operations

- insert            - O(N)
- insert to front   - O(1)
- delete            - O(N)
- delete first      - O(1)
- get element       - O(N)

Functions

- create_node(val, next=missing) - Create node with value 'val' and the pointer to the next node ( missing by default )
- create_list(n::Int=0, val=missing) - Create root node of the list with n elements with value set to 'val'
- insert(list::Node, new_node::Node, index::Int=1) - Add a new node to the list at the specified index
- insert(list::Node, val, index::Int=1) - Create a new node with value 'val' in the list at the specified index
- push_back(list::Node, node::Node) - Add a new node to the end of the list
- push_back(list::Node, val) - Add a new node with value 'val' to the end of the list
- return_as_array(list::Node) - Return the array representation of the list
- clear(list::Node) - Remove all elements from the list
- remove(list::Node, index::Int) - Remove an element at the specified index
- remove_all(list::Node, val) Remove all elements with the value 'val'
- remove_first(list::Node, val) - Remove the first element in the list with value 'val'
- get_node(list::Node, index::Int) - Get a node at the specified index
- get(list::Node, index::Int) - Get a value from the node at the specified index
- indexOf(list::Node, val) - Return the index of the first element with a value 'val'
- is_empty(list) - Return true if list is empty, false if it has elements

Contributed by: Nikola Mircic

source
TheAlgorithms.DataStructure.FenwickTree.changeMethod

This function changes the tree to correspond to an array after adding k to the element at index x

Arguments

- tree::Array{T} - A Fenwick tree for an array
- x::Integer - Index of the changed element
- k::Integer - An integer added to the element arr[x]
source
TheAlgorithms.DynamicProgramming.coin_changeMethod
coin_change(coins::Vector{Int}, amount::Int)

Given a vector coins of coin values, calculates the minimum number of coins that sums to amount. It's considered that a unlimited number of coins for each value is available.

Arguments:

• coins: the coins values available
• amount: the total amount that need to be summed to

Examples

julia> n_coins, coins = coin_change([1, 3, 4, 7], 13);

julia> n_coins
3

julia> coins
3-element Vector{Int64}:
3
3
7

julia> n_coins, coins = coin_change([2, 4, 6], 23)
(-1, Int64[])

julia> n_coins
-1

julia> coins
Int64[]

Contributors:

source
TheAlgorithms.Graph.bellman_fordFunction
bellman_ford(graph::Vector{Tuple{Int, Int, Int}}, source::Int)

The Bellman-Ford algorithm is an algorithm which computes the shortest paths from a single source vertex to all other vertices in a weighted graph. It is slower than Dijkstra's algorithm, which solves the same problem, but it is capable of handling graphs with negative edge weights. Instead of greedily performing the relaxation on the vertices, Bellman-Ford simply relaxes all edges, and does this |V|-1 times.

Arguments:

• graph: a directed, weighted graph
• source: the source vertex from which to begin the traversal

Example

graph = [
(1, 2, 4), (1, 3, 2),
(2, 3, 3), (2, 4, 2), (2, 5, 3),
(3, 2, 1), (3, 4, 4), (3, 5, 5),
(5, 4, -5)
]
bellman_ford(graph, 1)

# output

5-element Vector{Int64}:
0
3
2
1
6

Contributed by: Yannick Brenning

source
TheAlgorithms.Graph.bfsFunction
bfs(graph:Vector{Vector{Int}}, source::Int = 1)

Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at a given vertex and explores all vertices at the present depth before moving to the next "level". This implementation is for educational purposes only, so it simply prints out the vertices in the order that they were traversed.

Arguments:

• graph: a directed, unweighted graph
• source: the source vertex from which to begin the traversal

Example

graph = [
[2, 3, 6],
[3, 4],
[4],
[1, 2, 5],
[2],
[1, 5]
]
TheAlgorithms.Graph.bfs(graph, 4)

# output

6-element Vector{Int64}:
4
1
2
5
3
6

Contributed by: Yannick Brenning

source
TheAlgorithms.Graph.dfsFunction
dfs(graph::Vector{Vector{Int}}, source::Int)

Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at a given vertex and explores as far as possible along each branch before backtracking. This implementation is for educational purposes only, so it simply prints out the vertices in the order that they were traversed.

Arguments:

• graph: a directed, unweighted graph
• source: the source vertex from which to begin the traversal

Example

graph = [
[2, 3, 6],
[3, 4],
[4],
[1, 2, 5],
[2],
[1, 5]
]
dfs(graph, 6)

# output

6-element Vector{Int64}:
6
5
2
4
3
1

Contributed by: Yannick Brenning

source
TheAlgorithms.Graph.dijkstraMethod
dijkstra(graph::Vector{Vector{Tuple{Int,Int}}}, source::Int)

Given a directed graph with weights on the arcs and a source vertex, the dijkstra algorithm calculates the distance from the source to all other vertices, and the solution tree associated with those distances. The solution tree is given by a vector prev which stores the source of the arc that arrives at each vertex. By definition: distance[source] = prev[source] = 0. If a vertex v is not reachable from the source, then distance[v] = prev[v] = -1.

Arguments:

• graph: a directed graph with weights on the arcs
• source: the source vertex from which the distances will be calculated

Example

graph = [
[(2, 8), (3, 6), (4, 4)],
[(3, 1), (5, 5)],
[(5, 4)],
[(2, 3), (5, 9)],
[(1, 2), (3, 2), (4, 5)],
[(1, 1), (4, 3)],
]
distances, prev = dijkstra(graph, 1)

println("v | dist | path")
for v in eachindex(graph)
distance = distances[v] == -1 ? "  NR" : lpad(distances[v], 4) # NR: Non Reachable
path = join(get_dijkstra_path(prev, v), " -> ")
println("$v |$distance | $path") end # output v | dist | path 1 | 0 | 1 2 | 7 | 1 -> 4 -> 2 3 | 6 | 1 -> 3 4 | 4 | 1 -> 4 5 | 10 | 1 -> 3 -> 5 6 | NR |  Contributed By: Gabriel Soares source TheAlgorithms.KnapSack.complete_pack!Method This does complete/infinite (each item can be chosen infinite times) knapsack : pack capacity = capacity weight of each item = weights value of each item = values dp array is what the function works on It returns the ans (dp[capacity]) julia> dp=zeros(Int,30) julia> complete_pack!(20,[1,2,9],[1,3,20],dp) 43 source TheAlgorithms.KnapSack.complete_pack!Method This does complete/infinite (each item can be chosen infinite times) knapsack : pack capacity = capacity weight of each item = weights value of each item = values Each loop the function will find the highest value in the array and check if the capacity is enough to store it, if enough then the value will be added into the totalmaxvalue until the capacity cannot hold the weight of the highest current value. After that the highest current value will be deleted. julia> complete_pack!(20,[1,2,9],[1,3,20]) 43 source TheAlgorithms.KnapSack.zero_one_pack!Method zero_one_pack!(capacity::N, weights::V, values::V, dp::V) where {N <: Number,V <: AbstractVector} This does 0-1 (each item can be chosen only once) knapsack : pack capacity = capacity weight of each item = weights value of each item = values dp array is what the function works on It returns the ans (dp[capacity]) julia> dp=zeros(Int,30) julia> zero_one_pack!(20,[1,3,11],[2,5,30],dp) 37 source TheAlgorithms.KnapSack.zero_one_pack!Method For greedy algorithm, it will take the element based on the optimal value in the array at each loop in the function This does 0-1 (each item can be chosen only once) knapsack : pack capacity = capacity weight of each item = weights value of each item = values Each loop the function will find the highest value in the array and check if the capacity is enough to store it, if enough then the value will be added into the totalmaxvalue. After that the highest current value will be deleted. julia> zero_one_pack!(20,[1,3,11],[2,5,30]) 37 source TheAlgorithms.Math.abs_valMethod abs_val(num) Program to find the absolute value of a number Example abs_val(-100) # returns 100 abs_val(0) # returns 0 abs(123.1) # returns 123.1 -1000 == abs_val(-1000) #returns false 1000 == abs_val(1000) #returns true Contributed By:- Ashwani Rathee and Rratic source TheAlgorithms.Math.aliquot_sumMethod aliquot_sum(n::Int) The aliquot sum of a positive integer n is the sum of all the proper divisors of n, i.e, all divisors of n other than n itself. Input parameters: • n : The number to find the aliquot sum of. Examples/Tests: aliquot_sum(6) # returns 6 aliquot_sum(10) # returns 8 aliquot_sum(1345) # returns 275 aliquot_sum(-1) # throws DomainError Reference • https://en.wikipedia.org/wiki/Aliquot_sum Contributed by: Praneeth Jain source TheAlgorithms.Math.amicable_pairsMethod amicable_pairs(n::Int) Two unique natural numbers are said to form an amicable pair when them sum of proper divisors of each is equal to the other number. Input parameters: • n : Finds amicable pairs below n. Examples/Tests: amicable_pairs(10) # returns [] amicable_pairs(400) # returns [220 => 284] amicable_pairs(2000) # returns [220 => 284, 1184 => 1210] amicable_pairs(-1) # throws DomainError Reference • https://mathworld.wolfram.com/AmicablePair.html Contributed by Praneeth Jain source TheAlgorithms.Math.area_circleMethod area_circle(radius) Finds area of the circle Example area_circle(20) # returns 1256.6370614359173 area_circle(-1) # returns DomainError source TheAlgorithms.Math.area_ellipseMethod area_ellipse(radius_x, radius_y) Finds area of the ellipse Example area_ellipse(10, 10) # returns 314.1592653589793 area_ellipse(10, 20) # returns 628.3185307179587 area_ellipse(1, -2) # returns DomainError area_ellipse(-1, 2) # returns DomainError area_ellipse(-1, -2) # returns DomainError source TheAlgorithms.Math.area_heron_triangleMethod area_heron_triangle(side1, side2, side3) Finds area of a triangle using heron's formula Example area_heron_triangle(5,12,13) # returns 30.0 area_heron_triangle(-1,-2,1) # returns DomainError area_heron_triangle(1,-2,1) # returns DomainError area_heron_triangle(-1,2,1) # returns DomainError source TheAlgorithms.Math.area_parallelogramMethod area_parallelogram(base, height) Finds area of the parallelogram Example area_parallelogram(10,20) # returns 200 area_parallelogram(-1,-2) # returns DomainError area_parallelogram(1,-2) # returns DomainError area_parallelogram(-1,2) # returns DomainError source TheAlgorithms.Math.area_polygonMethod area_polygon(V) Finds area of any Polygon given by continuous sequence of vertex coordinates Arguments: • coords: x,y co-ordinates of the vertices [Vector of Tuples / Matrix with 2 rows or 2 columns] Example area_polygon([(0, 0), (100, 0), (0, 100)]) # returns 5000.0 area_polygon([0 0;100 0;100 100;0 100]) # returns 10000.0 area_polygon([(6, 4.5), (5, 4.5), (4.5, 5.5), (5, 6.5)]) # returns 1.5 area_polygon([0 0;100 0]) # returns DomainError area_polygon([(6, 4.63), (5, 4.63)]) # returns DomainError source TheAlgorithms.Math.area_rectangleMethod area_rectangle(length, width) Finds area of the rectangle Example area_rectangle(10,20) # returns 200 area_rectangle(-1,-2) # returns DomainError area_rectangle(1,-2) # returns DomainError area_rectangle(-1,2) # returns DomainError source TheAlgorithms.Math.area_regular_polygonMethod area_regular_polygon(sides, side_len) Finds area of any regular Polygon Example area_regular_polygon(1, 5) # returns DomainError area_regular_polygon(3, 5) # returns 10.825317547305486 area_regular_polygon(7, 15) # returns 817.6302999003576 area_regular_polygon(-1, 4) # returns DomainError area_regular_polygon(4, -3) # returns DomainError area_regular_polygon(-12, -4) # returns DomainError source TheAlgorithms.Math.area_rhombusMethod area_rhombus(diagonal_1, diagonal_2) Finds area of the rhombus Example area_rhombus(10, 20) # returns 100.0 area_rhombus(-1,-2) # returns DomainError area_rhombus(1,-2) # returns DomainError area_rhombus(-1,2) # returns DomainError source TheAlgorithms.Math.area_trapeziumMethod area_trapezium(base1,base2,height) Finds area of the traπzium Example area_trapezium(10, 20, 30) # returns 450.0 area_trapezium(-1, -2, -3) # returns DomainError area_trapezium(-1, 2, 3) # returns DomainError area_trapezium(1, -2, 3) # returns DomainError area_trapezium(1, 2, -3) # returns DomainError area_trapezium(-1, -2, 3) # returns DomainError area_trapezium(1, -2, -3) # returns DomainError area_trapezium(-1, 2, -3) # returns DomainError source TheAlgorithms.Math.area_triangleMethod area_triangle(base, height) Finds area of the right angled triangle with base height Example area_triangle(10,10) # returns 50.0 area_triangle(-1,-2) # returns DomainError area_triangle(1,-2) # returns DomainError area_triangle(-1,2) # returns DomainError source TheAlgorithms.Math.average_absolute_deviationMethod average_absolute_deviation(numbers) The average absolute deviation of a data set is the average of the absolute deviations from the mean. It is a measure of statistical dispersion or variability. Input parameters: • numbers : The numbers to find the average absolute deviation of. Examples/Tests: average_absolute_deviation([1, 2, 3, 4, 5]) # returns 1.2 average_absolute_deviation([0]) # returns 0.0 average_absolute_deviation([5.5, 64.3, 100.4]) # returns 34.16 Reference • https://mathworld.wolfram.com/AverageAbsoluteDeviation.html Contributed by Praneeth Jain source TheAlgorithms.Math.bab_sqrtMethod bab_sqrt(S::Real; tolerance = 1e-6, guess = nothing) The Babylonian Method of calculating a square root is a simple iterative method to determine square roots. A full description of the algorithm can be found on Wikipedia Arguments: • S: The number to calculate the square root for. Positional Arguments • tolerance: How close the square of the square root needs to be from the input value. abs(S - xn^2) < tolerance • guess: The initial value to use for xn Examples/Tests julia> bab_sqrt(100) 10.000000000107445 julia> bab_sqrt(100, guess = 15) 10.000000000131072 julia> bab_sqrt(π, guess = 1) 1.7724538555800293 julia> bab_sqrt(π, guess = 1, tolerance = 2) 2.0707963267948966 Algorithm: while tolerance <= abs(xn^2 - S) xn = (1 / 2) * (xn + S / xn) end References: Methods of computing square roots  Contributed by:- Anson Biggs source TheAlgorithms.Math.bin_lengthMethod bin_length(binNum) Returns the length of binNum's binary representation. Input parameters: • binNum : The number to find the binary length of. Examples/Tests: bin_length(1) # returns 1 bin_length(2) # returns 2 bin_length(3) # returns 2 bin_length(4) # returns 3 bin_length(5) # returns 3 bin_length(12) # returns 4 bin_length(256) # returns 9 bin_length(1024) # returns 11 bin_length(-1) # throws DomainError Contributed by: Praneeth Jain source TheAlgorithms.Math.bin_length_longMethod This algorithm features use of the OEIS entry A070939 - length of Binary Representation of n. It finds the length of any binary number and returns said length. https://oeis.org/A070939 This function, as believed, is O(n) The idea follows that the sequence is dependent on a repeating pattern of 2. Short for sequence, seq is the number of digits required before an increase in finNum or final number as seen here with the first few iterations - i on the left, final number on the right: 1 : 1 2 : 2 3 : 2 4 : 3 5 : 3 6 : 3 7 : 3 8 : 4 cont. As you can see, for every version of i, there is an appropriate modified number that only repeats for the sequence of the last doubled amount. #Contributions: Contributed by F35H: https://github.com/F35H source TheAlgorithms.Math.bin_length_shortMethod This algorithm features use of the OEIS entry A070939 - length of Binary Representation of n. It finds the length of any binary number and returns said length. https://oeis.org/A070939 This function, as believed, is O(log(n)) The idea follows that the sequence is dependent on a repeating pattern of 2. The final number being finNum increases on every doubling of i. 1 : 1 2 : 2 3 : 2 4 : 3 5 : 3 6 : 3 7 : 3 8 : 4 cont. As you can see, for every version of i, there is an appropriate final number that iterates on every doubling of i. Contributors: source TheAlgorithms.Math.catalanMethod catalan(n::Int) In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. Input parameters: • n : index of the catalan number. Examples/Tests: catalan(0) # returns 1 catalan(3) # returns 5 catalan(8) # returns 1430 catalan(-1) # throws DomainError Reference • https://mathworld.wolfram.com/CatalanNumber.html Contributed by: Praneeth Jain source TheAlgorithms.Math.ceilMethod ceil(x) Finds the ceiling of x as an functionInteger Example ceil(1.3) # 2.0 ceil(2.0) # returns 2.0 ceil(-1.5) #returns -1.0 Reference • https://en.wikipedia.org/wiki/Floorandceiling_functions Contributed By:- Ashwani Rathee source TheAlgorithms.Math.divisorsMethod divisors(n::Int) Returns the divisors of n as a vector. Input parameters: • n : The number to find the factors of. Examples/Tests: divisors(6) # returns [1, 2, 3, 6] divisors(10) # returns [1, 2, 5, 10] divisors(1345) # returns [1, 5, 269, 1345] divisors(-1) # throws DomainError Reference • https://mathworld.wolfram.com/Divisor.html Contributed by: Praneeth Jain source TheAlgorithms.Math.factorial_iterativeMethod factorial_iterative(n) Finds factorial of a number using Iterative method Example factorial_iterative(5) # returns 120 factorial_iterative(-1) # returns error Reference • factorial of a positive integer – https://en.wikipedia.org/wiki/Factorial Contributed By:- Ashwani Rathee and Rratic source TheAlgorithms.Math.fib_iterativeMethod fib_iterative(n::Int) Finds the first n fibonacci number using iterative method. Arguments: • n : Number of fibonacci numbers required Examples/Tests fib_iterative(1) # returns [0] fib_iterative(2) # returns [0, 1] fib_iterative(6) # returns [0, 1, 1, 2, 3, 5] fib_iterative(10) # returns [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] fib_iterative(-1) # throws DomainError Reference • https://mathworld.wolfram.com/FibonacciNumber.html Contributed by Praneeth Jain source TheAlgorithms.Math.fib_recursiveMethod fib_recursive(n::Int) Finds the first n fibonacci number using recursive method. Arguments: • n : Number of fibonacci numbers required Examples/Tests fib_recursive(1) # returns [0] fib_recursive(2) # returns [0, 1] fib_recursive(6) # returns [0, 1, 1, 2, 3, 5] fib_recursive(10) # returns [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] fib_recursive(-1) # throws DomainError Reference • https://mathworld.wolfram.com/FibonacciNumber.html Contributed by Praneeth Jain source TheAlgorithms.Math.fib_recursive_memoMethod fib_recursive_memo(n::Int) Finds the first n fibonacci number using recursive method and memoization. Arguments: • n : Number of fibonacci numbers required Examples/Tests fib_recursive_memo(1) # returns [0] fib_recursive_memo(2) # returns [0, 1] fib_recursive_memo(6) # returns [0, 1, 1, 2, 3, 5] fib_recursive_memo(10) # returns [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] fib_recursive_memo(-1) # throws DomainError Reference • https://mathworld.wolfram.com/FibonacciNumber.html Contributed by Praneeth Jain source TheAlgorithms.Math.floorMethod floor(x) Finds the floor of x as an Integer Example floor(1.3) # 1 floor(2.0) # returns 2.0 floor(-1.7) # returns -2.0 Reference • https://en.wikipedia.org/wiki/Floorandceiling_functions Contributed By:- Ashwani Rathee source TheAlgorithms.Math.get_mersenne_primesMethod get_mersenne_primes(n::Int) A mersenne prime is a prime number that is one less than a power of 2. Returns a list of mersenne primes upto n. Input parameters: • n : The limit upto which mersenne primes are to be generated. Examples/Tests: get_mersenne_primes(100) # returns [3, 7, 31] get_mersenne_primes(1000) # returns [3, 7, 31, 127] get_mersenne_primes(10000) # returns [3, 7, 31, 127, 8191] Reference • https://mathworld.wolfram.com/MersennePrime.html Contributed by Praneeth Jain source TheAlgorithms.Math.is_mersenne_primeMethod is_mersenne_prime(n::Int) A mersenne prime is a prime number that is one less than a power of 2. Checks whether the given integer is a mersenne prime. Input parameters: • n : The number to be checked. Examples/Tests: is_mersenne_prime(3) # returns true is_mersenne_prime(15) # returns false is_mersenne_prime(8191) # returns true Reference • https://mathworld.wolfram.com/MersennePrime.html Contributed by Praneeth Jain source TheAlgorithms.Math.krishnamurthyMethod krishnamurthy(number) Check if a number is a Krishnamurthy number or not Details It is also known as Peterson Number. A Krishnamurthy Number is a number whose sum of the factorial of the digits equals to the original number itself. For example: 145 = 1! + 4! + 5! So, 145 is a Krishnamurthy Number Example krishnamurthy(145) # returns true krishnamurthy(240) # returns false krishnamurthy(1) # returns true  Contributed By:- Ashwani Rathee source TheAlgorithms.Math.line_lengthFunction line_length(f, x_start, x_end, steps=100) Approximates the arc length of a line segment by treating the curve as a sequence of linear lines and summing their lengths. Arguments: • f: function that returns the arc • x_start: starting x value • xend: ending xvalue • steps: steps to take for accurace, more the steps greater the accuracy source TheAlgorithms.Math.meanMethod mean(nums) Find mean of a vector of numbers Example mean([3, 6, 9, 12, 15, 18, 21]) # returns 12.0 mean([5, 10, 15, 20, 25, 30, 35]) # returns 20.0 mean([1, 2, 3, 4, 5, 6, 7, 8]) # returns 4.5 Contributed By:- Ashwani Rathee and Rratic source TheAlgorithms.Math.modeMethod mode(nums) Finds mode of a vector of numbers Example mode([2, 3, 4, 5, 3, 4, 2, 5, 2, 2, 4, 2, 2, 2]) # returns [2] mode([3, 4, 5, 3, 4, 2, 5, 2, 2, 4, 4, 2, 2, 2]) # returns [2] mode([3, 4, 5, 3, 4, 2, 5, 2, 2, 4, 4, 4, 2, 2, 4, 2]) # returns [2, 4] mode(["x", "y", "y", "z"]) # returns ["y"] mode(["x", "x" , "y", "y", "z"]) # returns ["x", "y"] Contributed By:- Ashwani Rathee source TheAlgorithms.Math.monte_carlo_integrationMethod monte_carlo_integration(f::Function, a::Real, b::Real, n::Int) Monte carlo integration is a very easy and scalable way to do multidimentional integrals. However, only single variable integrals are considered. Arguments • f: the function to integrate. (at the momment only single variable is suported) • a: start in the integration limits. • b: endin the integration limits. • N: Number of points to sample. For most simple functions, 1000 to 10,000 should be okay. Examples julia> monte_carlo_integration(x -> 3*x^2, 0, 1, 100000) # integrate a polynomial 1.0000037602209 julia> monte_carlo_integration(x -> sin(x), 0, pi, 1000) # integrate the sin function 2.0018927826323756 References • https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/monte-carlo-integration • https://kingaa.github.io/sbied/pfilter/monteCarlo.html Contributors source TheAlgorithms.Math.num_divisorsMethod num_divisors(n::Int) Efficiently finds the number of divisors of n. Input parameters: • n : The number to find the number of divisors of. Examples/Tests: num_divisors(1) # returns 1 num_divisors(13) # returns 2 num_divisors(420) # returns 24 num_divisors(1345) # returns 4 num_divisors(-1) # throws DomainError Reference • https://cp-algorithms.com/algebra/divisors.html#number-of-divisors Contributed by: Praneeth Jain source TheAlgorithms.Math.partitions_recursiveMethod partitions_recursive(n) Finds partitions of an integer using recursion. A partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. There are 7 partitions of 5: 5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 Partitions of n is equal to the sum of partitions of n with k parts.$P \left ( n \right ) = \sum_{k=1}^{n} P_{k} \left ( n \right )$Partitions of n with k parts is the sum of partitions of n-1 with k-1 parts and, partitions of n-k with k parts.$P_{k}\left ( n \right ) = P_{k-1}\left ( n - 1 \right ) + P_{k}\left ( n - k \right )$Example partitions_recursive(0) # returns 1 partitions_recursive(1) # returns 1 partitions_recursive(10) # returns 42 partitions_recursive(-1) # returns DomainError References • Partitions of a positive integer – https://en.wikipedia.org/wiki/Partitionfunction(number_theory) • Partitions of a positive integer – https://www.whitman.edu/mathematics/cgt_online/book/section03.03.html Contributor source TheAlgorithms.Math.perfect_numberMethod perfect_number(number) Checks if a number is a perfect_number number or not Details perfect_number number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For example : 6 is perfect_number number Divisors of 6 => [1,2,3] Sum of divisors => 1+2+3 = 6 6 == sum(divisors) # which is true Example perfect_number(27) # returns false perfect_number(28) # returns true perfect_number(496) # returns true perfect_number(8128) # returns true perfect_number(123) # returns false Contributed By:- Ashwani Rathee and Rratic source TheAlgorithms.Math.perfect_squareMethod perfect_square(number) Check if a number is a perfect square or not. Example perfect_square(9) # returns True perfect_square(16) # returns True perfect_square(1) # returns True perfect_square(0) # returns True perfect_square(10) # returns False perfect_square(-9) # returns False Contributed By:- Ashwani Rathee and Rratic source TheAlgorithms.Math.prime_checkMethod prime_check(number) Checks to see if a number is a prime or not A number is prime if it has exactly two factors: 1 and itself. Example prime_check(2) # returns true prime_check(3) # returns true prime_check(5) # returns true prime_check(7) # returns true prime_check(11) # returns true prime_check(13) # returns true prime_check(17) # returns true prime_check(19) # returns true prime_check(23) # returns true prime_check(29) # returns true prime_check(30) # returns false Contributed By:- Ashwani Rathee and Rratic source TheAlgorithms.Math.prime_factorsMethod prime_factors(number) Returns prime factors of number as a vector Example prime_factors(50) # returns [2,5,5] prime_factors(0) # returns [] prime_factors(100) # returns [2, 2, 5, 5] prime_factors(2560) # returns [2, 2, 2, 2, 2, 2, 2, 2, 2, 5] Contributed By:- Ashwani Rathee source TheAlgorithms.Math.riemann_integrationFunction riemann_integration(f::Function, a::Real, b::Real, n::Int, approx::Symbol = :midpoint) a Riemann sum is a certain kind of approximation of an integral by a finite sum. The sum is calculated by partitioning the region into shapes (rectangles, trapezoids, parabolas, or cubics) that together form a region that is similar to the region being measured, then calculating the area for each of these shapes, and finally adding all of these small areas together. Because the region filled by the small shapes is usually not exactly the same shape as the region being measured, the Riemann sum will differ from the area being measured. This error can be reduced by dividing up the region more finely, using smaller and smaller shapes. As the shapes get smaller and smaller, the sum approaches the Riemann integral. Arguments • f: the function to integrate. (at the momment only single variable is suported) • a: Start of the integration limit. • b: End of the integration limit. • n: Number of points to sample. (as n increase, error decrease) • approx: Indicate the method of approximation (midpoint, left or right) Examples julia> riemann_integration(x -> x, 1, 3, 1_000, :midpoint) # 4.0 julia> riemann_integration(x -> x, 1, 3, 1_000, :left) # 3.997997997997998 julia> riemann_integration(x -> x, 1, 3, 1_000, :right) # 4.002002002002002 julia> riemann_integration(x -> 3*x^2, 0, 1, 100000) # integrate a polynomial 0.9999999999750021 julia> riemann_integration(x -> sin(x), 0, pi, 1000) # integrate the sin function 2.0000008241146774 Refereces • https://www.khanacademy.org/math/ap-calculus-ab/ab-integration-new/ab-6-2/a/riemann-sums-review • https://math.libretexts.org/Courses/MountRoyalUniversity/MATH2200%3ACalculusforScientistsII/2%3ATechniquesofIntegration/2.5%3ANumericalIntegration-Midpoint%2CTrapezoid%2CSimpson's_rule • https://abel.math.harvard.edu/~knill/teaching/math1a_2011/handouts/40-numerical.pdf • https://en.wikipedia.org/wiki/Riemann_integral Contributed By:- AugustoCL source TheAlgorithms.Math.runge_kutta_integrationMethod runge_kutta_integration(f::Function, x0::Real, y0::Real, h::Real, x_stop::Real) Numerically solve initial value problems of the form$y' = f(x, y)$to find$y(x)$using the Runge-Kutta 4th order integration scheme. Starting with the differential equation$\frac{\mathrm{d}y}{\mathrm{d}x} = y' = f(x, y)$and the initial condition$y(x_0) = y_0, each step calculates 4 approximations of the gradient \begin{align*} k_1 &= f(x_n, y_n),\\ k_2 &= f(x_n + \frac{h}{2}, y_n + k_1\frac{h}{2}),\\ k_3 &= f(x_n + \frac{h}{2}, y_n + k_2\frac{h}{2}),\\ k_4 &= f(x_n + h, y_n + k_3h), \end{align*} and uses the weighted average of them, $$$\bar{k} = \frac{k_1 + 2k_2 + 2k_3 + k_4}{6},$$$ to find the approximate value ofy(x_{n+1})$and update$x$and$yaccordingly \begin{align*} x &\rightarrow x_{n+1} = x_n + h\\ y &\rightarrow y_{n+1} = y_n + h\bar{k}. \end{align*} Arguments: • f: The functiony' = f(x, y)$to solve for$y(x)\$.
• x0: The starting value of x.
• y0: The starting value of y.
• h: The step size, should be >0.
• x_stop: The final value of x to solve to, i.e. integrate over the range [x0, x_stop]

Examples

julia> # If you have a constant slope of y' = 1, the analytic solution is y = x
julia> runge_kutta_integration((x, y)->1, 0, 0, 1, 3)
([0.0, 1.0, 2.0, 3.0], [0.0, 1.0, 2.0, 3.0])

julia> # Consider solving y' = exp(x), which has the analytic solution y = exp(x).
julia> runge_kutta_integration((x, y)->exp(x), 0, 1., 0.1, 0.1)
([0.0, 0.1], [1.0, 1.105170921726329])

julia> exp.([0.0, 0.1])
2-element Vector{Float64}:
1.0
1.1051709180756477


References

Contributors:

source
TheAlgorithms.Math.simpsons_integrationMethod
simpsons_integration(f::Function, a::Real, b::Real, n::Int)

Simpson's rule uses a quadratic polynomial on each subinterval of a partition to approximate the function f(x) and to compute the definite integral. This is an improvement over the trapezoid rule which approximates f(x) by a straight line on each subinterval of a partition. For more details of the method, check the link in the reference.

Arguments

• f: The function to integrate. (ar the moment only single variable is suported)
• a: Start of the integration limit.
• b: End of the integration limit.
• n: Number of points to sample. (as n increase, error decrease)

Examples/Test

# aproximate pi with f(x) = 4 / (1 + x^2)
julia> simpsons_integration(x -> 4 / (1 + x^2), 0, 1, 100_000)
3.1415926535897936
julia> simpsons_integration(x -> 4 / (1 + x^2), 0, 1, 100_000) ≈ pi
true

References:

• https://personal.math.ubc.ca/~pwalls/math-python/integration/simpsons-rule/

Contributed By:- AugustoCL

source
TheAlgorithms.Math.sum_apMethod
sum_ap(first_term, diff, num_terms)

Finds sum of a arithmetic progression series

Input parameters

• first_term : first term of the series
• diff : common difference between consecutive terms
• num_terms : number of terms in the series till which we count sum

Example

sum_ap(1, 1, 10)    # returns 55.0
sum_ap(1, 10, 100)  # returns 49600.0

Contributed By:- Ashwani Rathee

source
TheAlgorithms.Math.sum_divisorsMethod
sum_divisors(n::Int)

Returns the sum of the divisors of n.

Input parameters:

• n : The number to find the sum of divisors of.

Examples/Tests:

sum_divisors(6)     # returns 12
sum_divisors(10)    # returns 18
sum_divisors(1345)  # returns 1620
sum_divisors(-1)    # throws DomainError

Reference

• https://mathworld.wolfram.com/Divisor.html

Contributed by: Praneeth Jain

source
TheAlgorithms.Math.sum_gpMethod
sum_gp(first_term, ratio, num_terms)

Finds sum of n terms in a geometric progression

Input parameters

• first_term : first term of the series
• raio : common ratio between consecutive terms -> a2/a1 or a3/a2 or a4/a3
• num_terms : number of terms in the series till which we count sum

Example

sum_gp(1, 2, 10)    # 1023.0
sum_gp(1, 10, 5)    # 11111.0
sum_gp(0, 2, 10)    # 0.0
sum_gp(1, 0, 10)    # 1.0
sum_gp(1, 2, 0)     # -0.0
sum_gp(-1, 2, 10)   # -1023.0
sum_gp(1, -2, 10)   # -341.0

Contributed By:- Ashwani Rathee

source
TheAlgorithms.Math.surfarea_cubeMethod
surfarea_cube(side)

Finds surface area of a cube

Example

surfarea_cube(1)  # returns 6
surfarea_cube(3)  # returns 54
surfarea_cube(-1) # returns DomainError
source
TheAlgorithms.Math.surfarea_cuboidMethod
surfarea_cuboid(length, width, height)

Finds surface area of a cuboid

Example

surfarea_cuboid(5, 5, 5)  # returns 150
surfarea_cuboid(-5, -5, -5)  # returns DomainError
source
TheAlgorithms.Math.surfarea_sphereMethod
surfarea_sphere(side)

Finds surface area of a sphere

Example

surfarea_sphere(5)  # returns 314.1592653589793
surfarea_sphere(1)  # returns 12.566370614359172
surfarea_sphere(-1) # returns DomainError
source
TheAlgorithms.Math.totientMethod
totient(n::Int)

The totient function phi(n) is defined as the number of positive integers <=n that are relatively prime to n. Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function phi(n) can be simply defined as the number of totatives of n.

Input parameters:

• n : The number to find the totient of.

Examples/Tests:

totient(1) # returns 1
totient(2) # returns 1
totient(3) # returns 2
totient(10) # returns 4
totient(24) # returns 8
totient(50) # returns 20
totient(-1) # throws DomainError

Reference

• https://mathworld.wolfram.com/TotientFunction.html

Contributed by Praneeth Jain

source
TheAlgorithms.Math.trapazoidal_areaMethod
trapazoidal_area(f, x_start, x_end, steps)

Approximates the area under the curve using the trapezoidal rule Arguments:

• f: function for the
• x_start: starting value for x
• x_end: ending value for x
• steps: steps taken while integrating.
source
TheAlgorithms.Math.trapezoid_integrationMethod
trapezoid_integration(f::Function, a::Real, b::Real, n::Int)

The trapezoidal rule works by approximating the region under the graph of the function f(x) as a trapezoid and calculating its area.

Arguments

• f: the function to integrate. (at the momment only single variable is suported)
• a: Start of the integration limit.
• b: End of the integration limit.
• n: Number of points to sample. (as n increase, error decrease)

Examples/Test

julia> trapezoid_integration(x -> 4 / (1 + x^2), 0, 1, 100_000)
3.1415926535731526
julia> trapezoid_integration(x -> 4 / (1 + x^2), 0, 1, 100_000) ≈ pi
true

References:

-https://personal.math.ubc.ca/~pwalls/math-python/integration/trapezoid-rule/ -https://en.wikipedia.org/wiki/Trapezoidal_rule

Contributed By:- AugustoCL

source
TheAlgorithms.Math.verlet_integrationFunction

Verlet integration is an integration method used to integrate newtons - law of motion. It is frequently used to find trajectories in molecular dynamics simulation. The function takes four inputs viz,

• f : the differential equation
• x0 : the initial condition. This is a Vector with the first element as initial value for position (x0) and the second initial condition for velocity (v0)
• tspan: is the time span for integration. It is a tuple (initial time, final time)

This functionr returns a tuple (x,t):

• x is the solution
• t is the array containing the time points

Reference:

• https://www.algorithm-archive.org/contents/verletintegration/verletintegration.html

Contributed by: Ved Mahajan

source
TheAlgorithms.Math.vol_circular_cylinderMethod
vol_circular_cylinder(area_of_, height)

Compute the Volume of a Circular Cylinder.

Examples

julia-repl julia> volcircularcylinder(1, 1) 3.141592653589793 julia> volcircularcylinder(4, 3) 150.79644737231007

source
TheAlgorithms.Math.vol_coneMethod
vol_cone(area_of_base, height)

Compute the Volume of a Cone

Examples

julia> vol_cone(10, 3)
10.0
julia> vol_cone(1, 1)
0.3333333333333333
source
TheAlgorithms.Math.vol_cubeMethod
vol_cube()

Compute the volume of a cube.

Examples

julia> vol_cube(1)
1
julia> vol_cube(3)
27
julia> vol_cube(-1)
DomainError
source
TheAlgorithms.Math.vol_cuboidMethod
vol_cuboid(width, height, length)

Compute the volume of a vol_cuboid

Examples

julia> vol_cuboid(1, 1, 1)
1
julia> vol_cuboid(1, 2, 3)
6
source
TheAlgorithms.Math.vol_prismMethod
vol_prism(area_of_base, height)

Compute the Volume of a Prism.

Examples

julia> vol_prism(10, 2)
20.0
julia> vol_prism(11, 1)
11.0
source
TheAlgorithms.Math.vol_pyramidMethod
vol_pyramid(area_of_base, height)

Compute the volume of a Pyramid.

Examples

julia> vol_pyramid(10, 3)
10.0
julia> vol_pyramid(1.5, 3)
1.5
source
TheAlgorithms.Math.vol_sphereMethod
vol_sphere(radius)

Compute the volume of a sphere.

Examples

vol_sphere(5)  # returns 523.5987755982989
vol_sphere(1)  # returns 4.1887902047863905
vol_sphere(-1) # returns DomainError
source
TheAlgorithms.MatrixAlgo.determinantMethod
determinant(mat)

Given a non singluar matrix, calculate its determinant using LU decomposition.

L and U are lower triangular and upper triangular matrices respectively such that

A = L*U

If we want to find the determinant, then

det(A) = det(LU) = det(L)*det(U)

Determinant of triangualar matrices is the product of their diagonal entries. Hence, makes finding the determinant easy.

source
TheAlgorithms.MatrixAlgo.gauss_jordanMethod
gauss_jordan(A::AbstractMatrix{T}) where T<:Number

Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix. https://en.wikipedia.org/wiki/Gaussian_elimination

Examples/Tests

julia> M1 = [1 2 3; 4 5 6];
julia> M2 = [1 2 3; 4 8 12];

julia> @test gauss_jordan(M1) == [1 0 -1; 0 1 2]        # Test Passed
julia> @test_throws AssertionError gauss_jordan(M2)     # Test Passed - Thrown: AssertionError

Contributed By:- AugustoCL

source
TheAlgorithms.MatrixAlgo.rotation_matrixMethod

A 2D Rotation matrix is a mtrix that rotates a vector in a 2D real space by an angle theta. For more info: https://en.wikipedia.org/wiki/Rotation_matrix

This function takes the angle theta in radians as input and returns a 2D Matrix which will rotate the vector by angle theta.

source
TheAlgorithms.ProjectEuler.aliquot_sumMethod
aliquot_sum(n::Int)

The aliquot sum of a positive integer n is the sum of all the proper divisors of n, i.e, all divisors of n other than n itself.

Input parameters:

• n : The number to find the aliquot sum of.

Examples/Tests:

aliquot_sum(6)      # returns 6
aliquot_sum(10)     # returns 8
aliquot_sum(1345)   # returns 275
aliquot_sum(-1)     # throws DomainError

Reference

• https://en.wikipedia.org/wiki/Aliquot_sum

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.divisorsMethod
divisors(n::Int)

Returns the divisors of n as a vector.

Input parameters:

• n : The number to find the factors of.

Examples/Tests:

divisors(6)     # returns [1, 2, 3, 6]
divisors(10)    # returns [1, 2, 5, 10]
divisors(1345)  # returns [1, 5, 269, 1345]
divisors(-1)    # throws DomainError

Reference

• https://mathworld.wolfram.com/Divisor.html

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.num_divisorsMethod
num_divisors(n::Int)

Efficiently finds the number of divisors of n.

Input parameters:

• n : The number to find the number of divisors of.

Examples/Tests:

num_divisors(1)       # returns 1
num_divisors(13)      # returns 2
num_divisors(420)     # returns 24
num_divisors(1345)    # returns 4
num_divisors(-1)      # throws DomainError

Reference

• https://cp-algorithms.com/algebra/divisors.html#number-of-divisors

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_001Method
Multiples of 3 or 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Input parameters:

• limit : Upper limit for the numbers.

Examples/Tests:

problem_001(10)     # returns 23
problem_001(1000)   # returns 233168
problem_001(-1)     # throws DomainError

Reference

• https://projecteuler.net/problem=1

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_002Method
Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Input parameters:

• limit : Upper limit for the numbers.

Examples/Tests:

problem_002(10)         # returns 10
problem_002(4_000_000)  # returns 4613732
problem_002(-1)         # throws DomainError

Reference

• https://projecteuler.net/problem=2

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_003Method
Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Input parameters:

• number : Number to find the largest prime factor of.

Examples/Tests:

problem_003(17)             # returns 17
problem_003(13195)          # returns 29
problem_003(600851475143)   # returns 6857
problem_003(-1)             # throws DomainError

Reference

• https://projecteuler.net/problem=3

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_004Method
Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Examples/Tests:

problem_004()   # returns 906609

Reference

• https://projecteuler.net/problem=4

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_005Method
Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Input parameters:

• limit: Limit upto which to find the smallest multiple.

Examples/Tests:

problem_005(10) # returns 2520
problem_005(20) # returns 232792560
problem_005(-1) # throws DomainError

Reference

• https://projecteuler.net/problem=5

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_006Method
Sum square difference

The sum of the squares of the first ten natural numbers is, 1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Input parameters:

• n : limit upto which to find the sum square difference.

Examples/Tests:

problem_006(10)     # returns 2640
problem_006(100)    # returns 25164150
problem_006(-1)     # throws DomainError

Reference

• https://projecteuler.net/problem=6

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_007Method
10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Input parameters:

• n : Will find the nth prime.

Examples/Tests:

problem_007(1)      # returns 2
problem_007(6)      # returns 13
problem_007(10001)  # returns 104743
problem_007(-1)     # throws DomainError

Reference

• https://projecteuler.net/problem=7

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_008Method
Largest product in a series

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Input parameters:

• num_str : The number to find the greatest product in, in string form.
• n : Number of consecutive numbers to find the product of.

Examples/Tests:

num_str = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
problem_008("1234", 2)      # returns 12
problem_008(num_str, 4)     # returns 5832
problem_008(num_str, 13)    # returns 23514624000
problem_008("12345", 6)     # throws DomainError

Reference

• https://projecteuler.net/problem=8

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_009Method
Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

Examples/Tests:

problem_009()   # returns 31875000

Reference

• https://projecteuler.net/problem=9
• https://en.wikipedia.org/wiki/Pythagoreantriple#Generatinga_triple

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_010Method
Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Input parameters:

• n : Upper limit of primes.

Examples/Tests:

problem_010(1)          # returns 0
problem_010(10)         # returns 17
problem_010(2000000)    # returns 142913828922
problem_010(-1)         # throws DomainError

Reference

• https://projecteuler.net/problem=10

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_012Method
Highly Divisible Triangular Number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1+2+3+4+5+6+7 = 28. The first ten terms would be 1,3,6,10,15,21,28,36,45,55,... What is the value of the first triangle number to have over 500 divisors?

Input parameters:

• n : the triangle number must have over n divisors.

Examples/Tests:

problem_012(5)          # returns 28
problem_012(333)        # returns 17907120
problem_012(500)        # returns 76576500
problem_012(-1)         # throws DomainError

Reference

• https://projecteuler.net/problem=12

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_014Method
Longest Collatz Sequence

The following iterative sequence is defined for the set of positive integers: n -> n/2 (n is even) n -> 3n+1 (n is odd) Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain?

Input parameters:

• n : upper bound on the starting number

Examples/Tests:

problem_014(10)         # returns 9
problem_014(250)        # returns 231
problem_014(1000000)    # returns 837799
problem_014(-1)         # throws DomainError

Reference

• https://projecteuler.net/problem=14

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_015Method
Lattice Paths

Starting in the top left corner of a grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20 x 20 grid? grid?

Input parameters:

• n : number of rows in the grid
• m : number of columns in the grid

Examples/Tests:

problem_015(2, 2)       # returns 6
problem_015(5, 3)       # returns 56
problem_015(20, 20)     # returns 137846528820
problem_015(0, 5)       # throws DomainError
problem_015(-3, 0)      # throws DomainError

Reference

• https://projecteuler.net/problem=15

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_016Method
Power Digit Sum

2^15 = 32768 and the sum of its digits is 3+2+7+6+8=26. What is the sum of the digits of the number 2^1000? grid?

Input parameters:

• a : base
• n : exponent

Examples/Tests:

problem_016(1, 1)       # returns 1
problem_016(2, 15)      # returns 26
problem_016(2, 1000)    # returns 1366
problem_016(2, -4)      # throws DomainError

Reference

• https://projecteuler.net/problem=16

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_017Method
Number Letter Counts

If the numbers 1 to 5 are written out in words, then there are 3+3+5+4+4=19 letters used in total. If all the numbers from 1 to 1000 inclusive were written out in words, how many letters would be used?

Examples/Tests:

problem_017()       # returns 21124

Reference

• https://projecteuler.net/problem=17

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_018Method
Maximum Path Sum I

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

    3
7 4
2 4 6
8 5 9 3

Find the maximum total from top to bottom of the triangle below.

Examples/Tests:

problem_018()       # returns 1074

Reference

• https://projecteuler.net/problem=18

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_019Method
Counting Sundays

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Input parameters:

• start_year : start from 1st January of start_year
• end_year : check till 31st December of end_year

Examples/Tests:

problem_019(1901, 2000)     # returns 171
problem_019(1901, 2200)     # returns 515
problem_019(2020, 2023)     # returns 6
problem_019(-1, 2023)       # throws DomainError

Reference

• https://projecteuler.net/problem=19

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.problem_020Method
Factorial Digit Sum

Find the sum of the digits in the number 100!.

Input parameters:

• n : number to find sum of digits of factorial of

Examples/Tests:

problem_020(10)     # returns 27
problem_020(37)     # returns 153
problem_020(100)    # returns 648
problem_020(-1)     # throws DomainError

Reference

• https://projecteuler.net/problem=20

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.sum_divisorsMethod
sum_divisors(n::Int)

Returns the sum of the divisors of n.

Input parameters:

• n : The number to find the sum of divisors of.

Examples/Tests:

sum_divisors(6)     # returns 12
sum_divisors(10)    # returns 18
sum_divisors(1345)  # returns 1620
sum_divisors(-1)    # throws DomainError

Reference

• https://mathworld.wolfram.com/Divisor.html

Contributed by: Praneeth Jain

source
TheAlgorithms.ProjectEuler.zeller_congruenceMethod
Zeller's Congruence

Given a date, returns the day of the week

0 => Sunday 1 => Monday, 2 => Tuesday, ... , 6 => Saturday

Input parameters:

• day : day of the month
• month : month of the year (1 indexed)
• year : year

Reference

• https://en.wikipedia.org/wiki/Zeller%27s_congruence
source
TheAlgorithms.Scheduling.fcfsMethod
fcfs(n, process_id, burst_time)

Implementation of first come first served scheduling algorithm

Output

Tuple of vectors (processid, bursttime, waitingtime, turnaroundtime, avgwaitingtime, avgturnaroundtime)

Example

n = 3 # number of processes
process_id = Any[1, 2, 3] # process ids
burst_times = Any[3, 4, 5] # burst times
fcfs(n, process_id, burst_times)

Reference

https://en.wikipedia.org/wiki/Scheduling(computing)#Firstcome,firstserved

Contributed By:- Ashwani Rathee

source
TheAlgorithms.Searches.binary_searchMethod
binary_search(list, query; rev=false, lt=<, by=identity)

Implement a binary search algorithm. Searching a sorted collection is a common task. A dictionary is a sorted list of word definitions. Given a word, one can find its definition. A telephone book is a sorted list of people's names, addresses, and telephone numbers. Knowing someone's name allows one to quickly find their telephone number and address.

If the list to be searched contains more than a few items (a dozen, say) a binary search will require far fewer comparisons than a linear search, but it imposes the requirement that the list be sorted.

In computer science, a binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value.

In each step, the algorithm compares the search key value with the key value of the middle element of the array.

If the keys match, then a matching element has been found and the range of indices that equal the search key value are returned.

Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right.

If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned. Search methods in Julia typically return an empty range located at the insertion point in this case.

A binary search halves the number of items to check with each iteration, so locating an item (or determining its absence) takes logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.

Bonus task: Implement keyword arguments by, lt and rev so that by specifies a transformation applied to all elements of the list, lt specifies a comparison and rev specifies if the list is ordered in reverse.

Contributed By:- Soc Virnyl Estela

source
TheAlgorithms.Searches.binary_searchMethod
binary_search(arr::AbstractArray{T,1}, l::T, r::T, x::T) where {T<:Real}

The implementation of this binary Search is recursive and requires O(Log n) space. With iterative Binary Search, we need only O(1) space. Useful for the implementation of exponential_search.

Contributed By:- Ash

source
TheAlgorithms.Searches.exponential_searchMethod
 exponential_search(arr::AbstractArray{T,1}, x::T) where {T <: Real}

Exponential Search in 1-D array Time Complexity: O(Log n)

Exponential Search

It works in O(Log n) time Exponential search involves two steps:

• Find range where element is present
• Do Binary Search in above found range.

Time Complexity :

O(Log n) Applications of Exponential Search: Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite. Please refer Unbounded Binary Search for an example. It works better than Binary Search for bounded arrays, and also when the element to be searched is closer to the first element.

Contributed By:- Ash

source
TheAlgorithms.Searches.jump_searchMethod
jump_search(arr::AbstractArray{T,1}, x::T, jump::T = Int(ceil(sqrt(n)))) where {T <: Real}

Jump Search in 1-D array Time Complexity : O(√ n) Time complexity of Jump Search is between Linear Search ( ( O(n) ) and Binary Search ( O (Log n) )

source
TheAlgorithms.Sorts.counting_sort!Method

Counting Sort

OVERVIEW: Counting Sort is a sorting algorithm that sort elements within a specific range. The sorting technique is to count the existing element and stored its occurrence time in a new list, then only print it out.

STEPS: Assume the input as –> x=[-3, 1, -5, 0, -3] minimum = -5

• STEP 1: Create a list size within the range, in this case is -5 –> 1 which have range of 7 (-5, -4, -3, -2, -1, 0, 1), so list with size 7 and assign all to 0 is created

• STEP 2: Count the occurances of element in the list First number = -3 it is the third number in the range, so count[3]+=1 Final view: index : ( 1, 2, 3, 4, 5, 6, 7) range : (-5, -4, -3, -2, -1, 0, 1) count : [ 1, 0, 2, 0, 0, 1, 1] <– the list will store this occurrence

• STEP 3: Make the count list accumulate the occurances The final count is (1, 1, 3, 3, 3, 4, 5)

• STEP 4: Assign the elements in x into correct possition by creating a new list (will call 'output' in this sample) the 1st element in 'x' is -3, it is third in range, so it will call the index of 3 in 'count', which is 3 and assign the -3 in to 3rd position in 'output', then the third element in range will deduct by 1, so the next repeated element will get the correct position, new 'count' –> [1, 1, 2, 3, 3, 4, 5]

    the 2nd element in 'x' is  1, it is last  in range, so it will call the index of 7 in 'count', which is 5 and assign the  1 in to 5th position in 'output',
new 'count' --> [1, 1, 2, 3, 3, 4, 4]
......
......
*If you want the order of original array to have the same order as the output array use can change this to decremental for loop
• STEP 5: Assign the 'output' list back to 'x'

FINAL RESULT –> [-5, -3, -3, 0, 1]

source
TheAlgorithms.Sorts.heap_sort!Method
heap_sort!(arr::Vector{T}, gt = >, N::Int = length(arr)) where {T}

Sort the given vector (in-place) using the Heapsort algorithm.

Heapsort consists of two stages:

1. Building a (max) heap of the array
2. Repeatedly extracting the largest element and inserting it at the front of the sorted part of the array

After the largest element has been extracted, the tree is updated to maintain the heap property via a "sifting" operation.

Storing a heap in an array is pretty straightforward - for every node with index n, its children are stored at indices 2n + 1 and 2n + 2 (for 0-based indices). Index 0 contains the root node. Since Julia's indices are 1-based, we need to change this a little bit. We're using a trivial helper function idx_for to convert from 0-based to 1-based.

See https://en.wikipedia.org/wiki/Heapsort for a complete explanation of Heapsort.

Contributed By:- Frank Schmitt

source
TheAlgorithms.StatAlgo.varianceMethod
variance(a)

Find the variance from a set of data.

Arguments:

• a: holds the set of data

Reference

- According to Ronald E. Walpole, variance is used to measure the variability of a set of data. -- Introduction to Statistics by Ronald E. Walpole

Contributors:

source
TheAlgorithms.StringAlgo.detect_anagramsMethod
detect_anagrams(subject, candidates)

A function that checks if a list of words is an Anagram or not of a subject word.

is the original word = subject is list of words to be compared if they are an anagram of subject = candidates

julia> subject = "listen"
julia> candidates = ["inlets", "enlists", "google", "banana"]
julia> detect_anagrams(subject, candidates)
1-element Vector{String}:
"inlets"

Contributed By:- Soc V. E. Based on my exercism's Julia track problem solution on Anagrams.

Instructions:

An anagram is a rearrangement of letters to form a new word. Given a word and a list of candidates, select the sublist of anagrams of the given word. Given "listen" and a list of candidates like "enlists" "google" "inlets" "banana" the program should return a list containing "inlets".

Inspired by the Extreme Startup game

source
TheAlgorithms.StringAlgo.ispangramMethod

ispangram(input)

Program to determine the sentence is pangram or not.The program will return true if it is pangram and false if it is not.A full description of the algorithm can be found on exercism

Arguments:

• input: The sentence to find if its pangram or not.

Examples/Tests

julia> ispangram(Pack my box with five dozen liquor jugs)
true

julia> ispangram(The quick brown fox jumps over the lazy dog)
true

julia> wordcount(hello world!!!)
false


Algorithm:


for letter in input
if 'A' <= letter <= 'Z'
x &= ~(1<<(letter-'A'))
elseif 'a' <= letter <= 'z'
x &= ~(1<<(letter-'a'))
end
x == 0 && return true
end


References:

(https://exercism.org/tracks/julia/exercises/pangram)



Contributed by:- Ihjass Thasbekha

source
TheAlgorithms.StringAlgo.rabin_karpMethod
rabin_karp(text, pattern)

Brief:

A function that finds all occurrences of a pattern in the given text.
Instead of checking each character ot the pattern with each character block of the text,
for each character block calculate the hash value, and only if that value matches hash value of the pattern,
compare them character by character. These blocks are the same length as the pattern.

Returns:

A list with starting indices where the pattern was found

References:

https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/

Contributed by: Nikola Mircic

source
TheAlgorithms.StringAlgo.word_countMethod

wordcount(sentence)

Program to find word count in the given sentence. The program will return count with the word. A full description of the algorithm can be found on exercism

Arguments:

• sentence: The sentence to find the word count.

Examples/Tests

julia> wordcount(The quick brown fox jumps over the lazy dog)
Dict{Any, Any}("jumps" => 1, "the" => 2, "brown" => 1, "over" => 1, "quick" => 1, "lazy" => 1, "dog" => 1, "fox" => 1)

julia> wordcount(the sky is blue and beautiful)
Dict{Any, Any}("and" => 1, "the" => 1, "sky" => 1, "blue" => 1, "is" => 1, "beautiful" => 1)


Algorithm:


for word in eachmatch(reg_expression, sentence)
counts[word.match] = 1
else
counts[word.match] += 1
end
end


References:

(https://exercism.org/tracks/julia/exercises/word-count)



Contributed by:- Ihjass Thasbekha

source