# TheAlgorithms

Documentation for TheAlgorithms.

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{T}) - Create difference array for array 'original'
- calculate_arr(diff_arr::Array{T}) - Create a original array from the given difference array
- add_to_arr(diff_arr::Array{T}, l::Int, r::Int, x::Number) - 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.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],
,
[1, 2, 5],
,
[1, 5]
]
TheAlgorithms.Graph.bfs(graph, 4)

# output

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],
,
[1, 2, 5],
,
[1, 5]
]
dfs(graph, 6)

# output

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.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() # 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.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  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  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  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  mode([3, 4, 5, 3, 4, 2, 5, 2, 2, 4, 4, 2, 2, 2]) # returns  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.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://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.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.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.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.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+=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