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 its index, or position, is 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.
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.
An Armstrong number is a number that is the sum of its own digits each raised to the power of the number of digits.
For example:
9 is an Armstrong number, because 9 = 9^1 = 9 10 is not an Armstrong number, because 10 != 1^2 + 0^2 = 2 153 is an Armstrong number, because: 153 = 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153 154 is not an Armstrong number, because: 154 != 1^3 + 5^3 + 4^3 = 1 + 125 + 64 = 190 Write some code to determine whether a number is an Armstrong number.
Compute the prime factors of a given natural number.
A prime number is only evenly divisible by itself and 1.
Note that 1 is not a prime number.
Create an implementation of the rotational cipher, also sometimes called the Caesar cipher.
The Caesar cipher is a simple shift cipher that relies on transposing all the letters in the alphabet using an integer key between 0 and 26. Using a key of 0 or 26 will always yield the same output due to modular arithmetic. The letter is shifted for as many values as the value of the key.
The general notation for rotational ciphers is ROT +
A ROT13 on the Latin alphabet would be as follows:
Plain: abcdefghijklmnopqrstuvwxyz Cipher: nopqrstuvwxyzabcdefghijklm It is stronger than the Atbash cipher because it has 27 possible keys, and 25 usable keys.
Ciphertext is written out in the same formatting as the input including spaces and punctuation.
Examples: ROT5 omg gives trl ROT0 c gives c ROT26 Cool gives Cool ROT13 The quick brown fox jumps over the lazy dog. gives Gur dhvpx oebja sbk whzcf bire gur ynml qbt. ROT13 Gur dhvpx oebja sbk whzcf bire gur ynml qbt. gives The quick brown fox jumps over the lazy dog.
Given a number n, determine what the nth prime is.
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
If your language provides methods in the standard library to deal with prime numbers, pretend they don't exist and implement them yourself.
Create an implementation of the atbash cipher, an ancient encryption system created in the Middle East.
The Atbash cipher is a simple substitution cipher that relies on transposing all the letters in the alphabet such that the resulting alphabet is backwards. The first letter is replaced with the last letter, the second with the second-last, and so on.
An Atbash cipher for the Latin alphabet would be as follows:
Plain: abcdefghijklmnopqrstuvwxyz Cipher: zyxwvutsrqponmlkjihgfedcba It is a very weak cipher because it only has one possible key, and it is a simple monoalphabetic substitution cipher. However, this may not have been an issue in the cipher's time.
Ciphertext is written out in groups of fixed length, the traditional group size being 5 letters, and punctuation is excluded. This is to make it harder to guess things based on word boundaries.
Examples Encoding test gives gvhg Decoding gvhg gives test Decoding gsvjf rxpyi ldmul cqfnk hlevi gsvoz abwlt gives thequickbrownfoxjumpsoverthelazydog
The ISBN-10 verification process is used to validate book identification numbers. These normally contain dashes and look like: 3-598-21508-8
ISBN The ISBN-10 format is 9 digits (0 to 9) plus one check character (either a digit or an X only). In the case the check character is an X, this represents the value '10'. These may be communicated with or without hyphens, and can be checked for their validity by the following formula:
(x1 10 + x2 9 + x3 8 + x4 7 + x5 6 + x6 5 + x7 4 + x8 3 + x9 2 + x10 1) mod 11 == 0 If the result is 0, then it is a valid ISBN-10, otherwise it is invalid.
Example Let's take the ISBN-10 3-598-21508-8. We plug it in to the formula, and get:
(3 10 + 5 9 + 9 8 + 8 7 + 2 6 + 1 5 + 5 4 + 0 3 + 8 2 + 8 1) mod 11 == 0 Since the result is 0, this proves that our ISBN is valid.
Given a number, find the sum of all the unique multiples of particular numbers up to but not including that number.
If we list all the natural numbers below 20 that are multiples of 3 or 5, we get 3, 5, 6, 9, 10, 12, 15, and 18.
The sum of these multiples is 78.
Given a number determine whether or not it is valid per the Luhn formula.
The Luhn algorithm is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers.
The task is to check if a given string is valid.
Validating a Number Strings of length 1 or less are not valid. Spaces are allowed in the input, but they should be stripped before checking. All other non-digit characters are disallowed.
Example 1: valid credit card number 1 4539 1488 0343 6467 The first step of the Luhn algorithm is to double every second digit, starting from the right. We will be doubling
4_3_ 1_8_ 0_4_ 6_6_ If doubling the number results in a number greater than 9 then subtract 9 from the product. The results of our doubling:
8569 2478 0383 3437 Then sum all of the digits:
8+5+6+9+2+4+7+8+0+3+8+3+3+4+3+7 = 80 If the sum is evenly divisible by 10, then the number is valid. This number is valid!
Example 2: invalid credit card number 1 8273 1232 7352 0569 Double the second digits, starting from the right
7253 2262 5312 0539 Sum the digits
7+2+5+3+2+2+6+2+5+3+1+2+0+5+3+9 = 57 57 is not evenly divisible by 10, so this number is not valid.