``````function change (coins, amount) {
const combinations = new Array(amount + 1).fill(0)
combinations[0] = 1

for (let i = 0; i < coins.length; i++) {
const coin = coins[i]

for (let j = coin; j < amount + 1; j++) {
combinations[j] += combinations[j - coin]
}
}
return combinations[amount]
}

function minimumCoins (coins, amount) {
// minimumCoins[i] will store the minimum coins needed for amount i
const minimumCoins = new Array(amount + 1).fill(0)

minimumCoins[0] = 0

for (let i = 1; i < amount + 1; i++) {
minimumCoins[i] = Number.MAX_SAFE_INTEGER
}
for (let i = 1; i < amount + 1; i++) {
for (let j = 0; j < coins.length; j++) {
const coin = coins[j]
if (coin <= i) {
const subRes = minimumCoins[i - coin]
if (subRes !== Number.MAX_SAFE_INTEGER && subRes + 1 < minimumCoins[i]) {
minimumCoins[i] = subRes + 1
}
}
}
}
return minimumCoins[amount]
}

function main () {
const amount = 12
const coins = [2, 4, 5]
console.log('Number of combinations of getting change for ' + amount + ' is: ' + change(coins, amount))
console.log('Minimum number of coins required for amount :' + amount + ' is: ' + minimumCoins(coins, amount))
}

main()
``````
``````#!/usr/bin/env python3

"""
This is pure Python implementation of binary search algorithms

For doctests run following command:
python3 -m doctest -v binary_search.py

For manual testing run:
python3 binary_search.py
"""
import bisect
from typing import List, Optional

def bisect_left(
sorted_collection: List[int], item: int, lo: int = 0, hi: int = -1
) -> int:
"""
Locates the first element in a sorted array that is larger or equal to a given
value.

It has the same interface as
https://docs.python.org/3/library/bisect.html#bisect.bisect_left .

:param sorted_collection: some ascending sorted collection with comparable items
:param item: item to bisect
:param lo: lowest index to consider (as in sorted_collection[lo:hi])
:param hi: past the highest index to consider (as in sorted_collection[lo:hi])
:return: index i such that all values in sorted_collection[lo:i] are < item and all
values in sorted_collection[i:hi] are >= item.

Examples:
>>> bisect_left([0, 5, 7, 10, 15], 0)
0

>>> bisect_left([0, 5, 7, 10, 15], 6)
2

>>> bisect_left([0, 5, 7, 10, 15], 20)
5

>>> bisect_left([0, 5, 7, 10, 15], 15, 1, 3)
3

>>> bisect_left([0, 5, 7, 10, 15], 6, 2)
2
"""
if hi < 0:
hi = len(sorted_collection)

while lo < hi:
mid = (lo + hi) // 2
if sorted_collection[mid] < item:
lo = mid + 1
else:
hi = mid

return lo

def bisect_right(
sorted_collection: List[int], item: int, lo: int = 0, hi: int = -1
) -> int:
"""
Locates the first element in a sorted array that is larger than a given value.

It has the same interface as
https://docs.python.org/3/library/bisect.html#bisect.bisect_right .

:param sorted_collection: some ascending sorted collection with comparable items
:param item: item to bisect
:param lo: lowest index to consider (as in sorted_collection[lo:hi])
:param hi: past the highest index to consider (as in sorted_collection[lo:hi])
:return: index i such that all values in sorted_collection[lo:i] are <= item and
all values in sorted_collection[i:hi] are > item.

Examples:
>>> bisect_right([0, 5, 7, 10, 15], 0)
1

>>> bisect_right([0, 5, 7, 10, 15], 15)
5

>>> bisect_right([0, 5, 7, 10, 15], 6)
2

>>> bisect_right([0, 5, 7, 10, 15], 15, 1, 3)
3

>>> bisect_right([0, 5, 7, 10, 15], 6, 2)
2
"""
if hi < 0:
hi = len(sorted_collection)

while lo < hi:
mid = (lo + hi) // 2
if sorted_collection[mid] <= item:
lo = mid + 1
else:
hi = mid

return lo

def insort_left(
sorted_collection: List[int], item: int, lo: int = 0, hi: int = -1
) -> None:
"""
Inserts a given value into a sorted array before other values with the same value.

It has the same interface as
https://docs.python.org/3/library/bisect.html#bisect.insort_left .

:param sorted_collection: some ascending sorted collection with comparable items
:param item: item to insert
:param lo: lowest index to consider (as in sorted_collection[lo:hi])
:param hi: past the highest index to consider (as in sorted_collection[lo:hi])

Examples:
>>> sorted_collection = [0, 5, 7, 10, 15]
>>> insort_left(sorted_collection, 6)
>>> sorted_collection
[0, 5, 6, 7, 10, 15]

>>> sorted_collection = [(0, 0), (5, 5), (7, 7), (10, 10), (15, 15)]
>>> item = (5, 5)
>>> insort_left(sorted_collection, item)
>>> sorted_collection
[(0, 0), (5, 5), (5, 5), (7, 7), (10, 10), (15, 15)]
>>> item is sorted_collection[1]
True
>>> item is sorted_collection[2]
False

>>> sorted_collection = [0, 5, 7, 10, 15]
>>> insort_left(sorted_collection, 20)
>>> sorted_collection
[0, 5, 7, 10, 15, 20]

>>> sorted_collection = [0, 5, 7, 10, 15]
>>> insort_left(sorted_collection, 15, 1, 3)
>>> sorted_collection
[0, 5, 7, 15, 10, 15]
"""
sorted_collection.insert(bisect_left(sorted_collection, item, lo, hi), item)

def insort_right(
sorted_collection: List[int], item: int, lo: int = 0, hi: int = -1
) -> None:
"""
Inserts a given value into a sorted array after other values with the same value.

It has the same interface as
https://docs.python.org/3/library/bisect.html#bisect.insort_right .

:param sorted_collection: some ascending sorted collection with comparable items
:param item: item to insert
:param lo: lowest index to consider (as in sorted_collection[lo:hi])
:param hi: past the highest index to consider (as in sorted_collection[lo:hi])

Examples:
>>> sorted_collection = [0, 5, 7, 10, 15]
>>> insort_right(sorted_collection, 6)
>>> sorted_collection
[0, 5, 6, 7, 10, 15]

>>> sorted_collection = [(0, 0), (5, 5), (7, 7), (10, 10), (15, 15)]
>>> item = (5, 5)
>>> insort_right(sorted_collection, item)
>>> sorted_collection
[(0, 0), (5, 5), (5, 5), (7, 7), (10, 10), (15, 15)]
>>> item is sorted_collection[1]
False
>>> item is sorted_collection[2]
True

>>> sorted_collection = [0, 5, 7, 10, 15]
>>> insort_right(sorted_collection, 20)
>>> sorted_collection
[0, 5, 7, 10, 15, 20]

>>> sorted_collection = [0, 5, 7, 10, 15]
>>> insort_right(sorted_collection, 15, 1, 3)
>>> sorted_collection
[0, 5, 7, 15, 10, 15]
"""
sorted_collection.insert(bisect_right(sorted_collection, item, lo, hi), item)

def binary_search(sorted_collection: List[int], item: int) -> Optional[int]:
"""Pure implementation of binary search algorithm in Python

Be careful collection must be ascending sorted, otherwise result will be
unpredictable

:param sorted_collection: some ascending sorted collection with comparable items
:param item: item value to search
:return: index of found item or None if item is not found

Examples:
>>> binary_search([0, 5, 7, 10, 15], 0)
0

>>> binary_search([0, 5, 7, 10, 15], 15)
4

>>> binary_search([0, 5, 7, 10, 15], 5)
1

>>> binary_search([0, 5, 7, 10, 15], 6)

"""
left = 0
right = len(sorted_collection) - 1

while left <= right:
midpoint = left + (right - left) // 2
current_item = sorted_collection[midpoint]
if current_item == item:
return midpoint
elif item < current_item:
right = midpoint - 1
else:
left = midpoint + 1
return None

def binary_search_std_lib(sorted_collection: List[int], item: int) -> Optional[int]:
"""Pure implementation of binary search algorithm in Python using stdlib

Be careful collection must be ascending sorted, otherwise result will be
unpredictable

:param sorted_collection: some ascending sorted collection with comparable items
:param item: item value to search
:return: index of found item or None if item is not found

Examples:
>>> binary_search_std_lib([0, 5, 7, 10, 15], 0)
0

>>> binary_search_std_lib([0, 5, 7, 10, 15], 15)
4

>>> binary_search_std_lib([0, 5, 7, 10, 15], 5)
1

>>> binary_search_std_lib([0, 5, 7, 10, 15], 6)

"""
index = bisect.bisect_left(sorted_collection, item)
if index != len(sorted_collection) and sorted_collection[index] == item:
return index
return None

def binary_search_by_recursion(
sorted_collection: List[int], item: int, left: int, right: int
) -> Optional[int]:

"""Pure implementation of binary search algorithm in Python by recursion

Be careful collection must be ascending sorted, otherwise result will be
unpredictable
First recursion should be started with left=0 and right=(len(sorted_collection)-1)

:param sorted_collection: some ascending sorted collection with comparable items
:param item: item value to search
:return: index of found item or None if item is not found

Examples:
>>> binary_search_by_recursion([0, 5, 7, 10, 15], 0, 0, 4)
0

>>> binary_search_by_recursion([0, 5, 7, 10, 15], 15, 0, 4)
4

>>> binary_search_by_recursion([0, 5, 7, 10, 15], 5, 0, 4)
1

>>> binary_search_by_recursion([0, 5, 7, 10, 15], 6, 0, 4)

"""
if right < left:
return None

midpoint = left + (right - left) // 2

if sorted_collection[midpoint] == item:
return midpoint
elif sorted_collection[midpoint] > item:
return binary_search_by_recursion(sorted_collection, item, left, midpoint - 1)
else:
return binary_search_by_recursion(sorted_collection, item, midpoint + 1, right)

if __name__ == "__main__":
user_input = input("Enter numbers separated by comma:
").strip()
collection = sorted(int(item) for item in user_input.split(","))
target = int(input("Enter a single number to be found in the list:
"))
result = binary_search(collection, target)
if result is None:
else:
print(f"{target} was found at position {result} in {collection}.")
``````
``````/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program sha256_64.s   */

/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

.equ LGHASH, 32                  // result length

/*******************************************/
/* Structures                               */
/********************************************/
/* example structure  variables  */
.struct  0
var_a:                     // a
.struct  var_a + 4
var_b:                     // b
.struct  var_b + 4
var_c:                     // c
.struct  var_c + 4
var_d:                     // d
.struct  var_d + 4
var_e:                     // e
.struct  var_e + 4
var_f:                     // f
.struct  var_f + 4
var_g:                     // g
.struct  var_g + 4
var_h:                     // h
.struct  var_h + 4

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessRosetta:        .asciz "Rosetta code"
szMessTest1:           .asciz "abc"
szMessSup64:           .ascii "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
.ascii "abcdefghijklmnopqrstuvwxyz"
.asciz "1234567890AZERTYUIOP"
szMessTest2:           .asciz "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
szMessFinPgm:          .asciz "Program End ok.
"
szMessResult:          .asciz "Rosetta code => "
szCarriageReturn:   .asciz "
"

/* array constantes Hi */
tbConstHi:           .int 0x6A09E667       // H0
.int 0xBB67AE85       // H1
.int 0x3C6EF372       // H2
.int 0xA54FF53A       // H3
.int 0x510E527F       // H4
.int 0x9B05688C       // H5
.int 0x1F83D9AB       // H6
.int 0x5BE0CD19       // H7
/* array  64 constantes Kt */
tbConstKt:
.int 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5
.int 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174
.int 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da
.int 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967
.int 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85
.int 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070
.int 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3
.int 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2

/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
.align 4
qNbBlocs:                    .skip 8
sZoneConv:                   .skip 24
sZoneTrav:                   .skip 1000
.align 8
tbH:                         .skip 4 * 8         // 8 variables H
tbabcdefgh:                  .skip 4 * 8
tbW:                         .skip 4 * 64        // 64 words W
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main
main:                                      // entry of program

bl computeSHA256                       // call routine SHA1

bl affichageMess                       // display message

bl displaySHA1

bl affichageMess                       // display message

100:                                       // standard end of the program
mov x0,0                               // return code
mov x8,EXIT                            // request to exit program
svc 0                                  // perform the system call

/******************************************************************/
/*     compute SHA1                         */
/******************************************************************/
/* x0 contains the address of the message */
computeSHA256:
stp x1,lr,[sp,-16]!      // save  registers
mov x2,#0                // counter length
debCopy:                     // copy string in work area
ldrb w3,[x0,x2]
strb w3,[x1,x2]
cmp x3,#0
csel x2,x4,x2,ne
bne debCopy
lsl x6,x2,#3             // initial message length in bits
mov x3,#0b10000000       // add bit 1 at end of string
strb w3,[x1,x2]
add x2,x2,#1             // length in bytes
lsl x4,x2,#3             // length in bits
mov x3,#0
lsr x5,x2,#6
lsl x5,x5,#6
sub x5,x2,x5
cmp x5,#56
beq storeLength          // yes -> end add
strb w3,[x1,x2]          // add zero at message end
add x2,x2,#1              // increment lenght bytes
add x4,x4,#8             // increment length in bits
storeLength:
rev w6,w6                // inversion bits initials message length
str w6,[x1,x2]           // and store at end

ldr x4,qAdrtbH           // start area H
mov x5,#0
loopConst:                   // init array H with start constantes
ldr w6,[x7,x5,lsl #2]    // load constante
str w6,[x4,x5,lsl #2]    // and store
cmp x5,#8
blt loopConst
// split into block of 64 bytes
lsr x4,x2,#6             // blocks number
str x4,[x0]              // save block maxi
mov x7,#0                // n° de block et x1 contient l adresse zone de travail
loopBlock:                   // begin loop of each block of 64 bytes
mov x0,x7
bl inversion             // inversion each word because little indian
mov x6,#0                // indice t
/* x2  address begin each block */
add x2,x1,x7,lsl #6      //  compute block begin  indice * 4 * 16
//vidregtit avantloop
//mov x0,x2
//vidmemtit  verifBloc x0 10
loopPrep:                    // loop for expand 80 words
cmp x6,#15               //
bgt expand1
ldr w0,[x2,x6,lsl #2]    // load word message
str w0,[x3,x6,lsl #2]    // store in first 16 block
b expandEnd

expand1:
sub x8,x6,#2
ldr w9,[x3,x8,lsl #2]
ror w10,w9,#17           // fonction e1 (256)
ror w11,w9,#19
eor w10,w10,w11
lsr w11,w9,#10
eor w10,w10,w11
sub x8,x6,#7
ldr w9,[x3,x8,lsl #2]
add w9,w9,w10            // + w - 7
sub x8,x6,#15
ldr w10,[x3,x8,lsl #2]
ror w11,w10,#7          // fonction e0 (256)
ror w12,w10,#18
eor w11,w11,w12
lsr w12,w10,#3
eor w10,w11,w12
sub x8,x6,#16
ldr w11,[x3,x8,lsl #2]

str w9,[x3,x6,lsl #2]
expandEnd:
cmp x6,#64                 // 64 words ?
blt loopPrep               // and loop

/* COMPUTING THE MESSAGE DIGEST */
/* x1  area H constantes address */
/* x3  working area W address  */
/* x5  address constantes K   */
/* x6  counter t */
/* x7  block counter */
/* x8  addresse variables a b c d e f g h  */
//vidmemtit  verifW80 x0 20
// init variable a b c d e f g h
mov x1,#0
loopInita:
ldr w9,[x0,x1,lsl #2]
str w9,[x8,x1,lsl #2]
cmp x1,#8
blt loopInita

mov x6,#0
loop64T:                      // begin loop 64 t
ldr w9,[x8,#var_h]
ldr w10,[x8,#var_e]       // calcul T1
ror w11,w10,#6            // fonction sigma 1
ror w12,w10,#11
eor w11,w11,w12
ror w12,w10,#25
eor w11,w11,w12
add w9,w9,w11             // h + sigma1 (e)
ldr w0,[x8,#var_f]        //  fonction ch  x and y xor (non x and z)
ldr w4,[x8,#var_g]
and w11,w10,w0
mvn w12,w10
and w12,w12,w4
eor w11,w11,w12
add w9,w9,w11             // h + sigma1 (e) + ch (e,f,g)
ldr w0,[x5,x6,lsl #2]     // load constantes k0
ldr w0,[x3,x6,lsl #2]     // Wt
// calcul T2
ldr w10,[x8,#var_a]       // fonction sigma 0
ror w11,w10,#2
ror w12,w10,#13
eor w11,w11,w12
ror w12,w10,#22
eor w11,w11,w12
ldr w2,[x8,#var_b]
ldr w4,[x8,#var_c]
// fonction maj x and y xor x and z xor y and z
and w12,w10,w2
and w0,w10,w4
eor w12,w12,w0
and w0,w2,w4
eor w12,w12,w0            //
// compute variables
ldr w4,[x8,#var_g]
str w4,[x8,#var_h]
ldr w4,[x8,#var_f]
str w4,[x8,#var_g]
ldr w4,[x8,#var_e]
str w4,[x8,#var_f]
ldr w4,[x8,#var_d]
str w4,[x8,#var_e]
ldr w4,[x8,#var_c]
str w4,[x8,#var_d]
ldr w4,[x8,#var_b]
str w4,[x8,#var_c]
ldr w4,[x8,#var_a]
str w4,[x8,#var_b]
str w4,[x8,#var_a]

cmp x6,#64
blt loop64T
// End block
ldr x0,qAdrtbH            // start area H
mov x10,#0
loopStoreH:
ldr w9,[x8,x10,lsl #2]
ldr w3,[x0,x10,lsl #2]
str w3,[x0,x10,lsl #2]    // store variables in H0
cmp x10,#8
blt loopStoreH
// other bloc
ldr x4,[x0]               // restaur maxi block
cmp x7,x4                 // maxi ?

blt loopBlock             //  loop other block

mov x0,#0                 // routine OK
100:
ldp x1,lr,[sp],16              // restaur  2 registers
/******************************************************************/
/*     inversion des mots de 32 bits d un bloc                    */
/******************************************************************/
/* x0 contains N° block   */
inversion:
stp x1,lr,[sp,-16]!            // save  registers
stp x2,x3,[sp,-16]!            // save  registers
add x1,x1,x0,lsl #6           // debut du bloc
mov x2,#0
1:                                                  // start loop
ldr w3,[x1,x2,lsl #2]
rev w3,w3
str w3,[x1,x2,lsl #2]
cmp x2,#16
blt 1b
100:
ldp x2,x3,[sp],16              // restaur  2 registers
ldp x1,lr,[sp],16              // restaur  2 registers
/******************************************************************/
/*     display hash  SHA1                         */
/******************************************************************/
/* x0 contains the address of hash  */
displaySHA1:
stp x1,lr,[sp,-16]!            // save  registers
stp x2,x3,[sp,-16]!            // save  registers
mov x3,x0
mov x2,#0
1:
ldr w0,[x3,x2,lsl #2]          // load 4 bytes
//rev x0,x0                    // reverse bytes
bl conversion16_4W             // conversion hexa
bl affichageMess
cmp x2,#LGHASH / 4
blt 1b                         // and loop
bl affichageMess               // display message
100:
ldp x2,x3,[sp],16              // restaur  2 registers
ldp x1,lr,[sp],16              // restaur  2 registers
/******************************************************************/
/*     conversion  hexadecimal register 32 bits                   */
/******************************************************************/
/* x0 contains value and x1 address zone receptrice   */
conversion16_4W:
stp x0,lr,[sp,-48]!        // save  registres
stp x1,x2,[sp,32]          // save  registres
stp x3,x4,[sp,16]          // save  registres
mov x2,#28                 // start bit position
mov x3,x0                  // save entry value
1:                             // start loop
and x0,x3,x4               // value register and mask
lsr x0,x0,x2               // right shift
cmp x0,#10                 // >= 10 ?
bge 2f                     // yes
add x0,x0,#48              // no is digit
b 3f
2:
add x0,x0,#55              // else is a letter A-F
3:
lsr x4,x4,#4               // shift mask 4 bits left
subs x2,x2,#4              // decrement counter 4 bits <= zero  ?
bge 1b                     // no -> loop

100:                           // fin standard de la fonction
ldp x3,x4,[sp,16]          // restaur des  2 registres
ldp x1,x2,[sp,32]          // restaur des  2 registres
ldp x0,lr,[sp],48          // restaur des  2 registres
ret
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
``````

Hello, algorithms!

Welcome to GitHub's largest open-source algorithm library

+11

+13

## Fibonacci Numbers

+8

##### What is an Algorithm?

An algorithm is a set of rules that takes in one or more inputs, then performs inner calculations and data manipulations and returns an output or a set of outputs. In short, algorithms make life easy. From complex data manipulations and hashes, to simple arithmetic, algorithms follow a set of steps to produce a useful result. One example of an algorithm would be a simple function that takes two input values, adds them together, and returns their sum.

We are a group of programmers helping each other build new things, whether it be writing complex encryption programs, or simple ciphers. Our goal is to work together to document and model beautiful, helpful and interesting algorithms using code. We are an open-source community - anyone can contribute. We check each other's work, communicate and collaborate to solve problems. We strive to be welcoming, respectful, yet make sure that our code follows the latest programming guidelines.

## Bogo Sort

+2

##### Programming Languages

We support many programming languages. Each language has its own GitHub repository where all the code for the algorithms is stored. Here is a list of the current programming languages:

##### Contribute
We encourage you to contribute to these repositories. If you have an algorithm that you want to add, a change you want to make, or a bug you want to fix, please do so. But before you do, make sure you have read the contributing guidelines found in CONTRIBUTING.md in the repository. Make sure that you are respectful, helpful, and using the latest version of the language. After reading the contribution guidelines, please fork the repository, work on your changes and then submit them as a pull request. You can also help us translate the website using Weblate. If you have any other languages you want to add, or any strings you want to fix, you're welcome to contribute.
GitHubWeblate
Another way you can support us is to make a donation via Liberapay. Even a small donation is much appreciated. By donating, it means that you appreciate and like our work. If you don't like our work, there's no need to donate. If you donate, top members will be able to contribute further to The Algorithms projects. We appreciate donations from everyone, from everywhere, no matter the amount.
Donate