### 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.

Finish the solution so that it returns the sum of all the multiples of 3 or 5 below the number passed in. Additionally, if the number is negative, return 0 (for languages that do have them).

Note: If the number is a multiple of both 3 and 5, only count it once.

```
public int solution(int number) {
if(number < 0){
return 0;
}
int sum = 0;
for (int i = 1; i < number; i++) {
if(i % 3 == 0 || i % 5 == 0) {
sum = sum + i;
}
}
return sum;
}
```

```
public int solution(int number) {
return IntStream.range(0, number)
.filter(n -> (n % 3 == 0) || (n % 5 == 0))
.sum();
}
```

### Take a Ten Minutes Walk

You live in the city of Cartesia where all roads are laid out in a perfect grid. You arrived ten minutes too early to an appointment, so you decided to take the opportunity to go for a short walk. The city provides its citizens with a Walk Generating App on their phones — everytime you press the button it sends you an array of one-letter strings representing directions to walk (eg. [‘n’, ‘s’, ‘w’, ‘e’]). You always walk only a single block for each letter (direction) and you know it takes you one minute to traverse one city block, so create a function that will return true if the walk the app gives you will take you exactly ten minutes (you don’t want to be early or late!) and will, of course, return you to your starting point. Return false otherwise.

Note: you will always receive a valid array containing a random assortment of direction letters (‘n’, ‘s’, ‘e’, or ‘w’ only). It will never give you an empty array (that’s not a walk, that’s standing still!).

```
public static boolean isValid(char[] walk) {
if (walk.length < 10 || walk.length > 10) {
return false;
}
int nscount = 0;
int ewcount = 0;
for (int i = 0; i < 10; i++) {
if(walk[i] == 'n')
nscount += 1;
if(walk[i] == 's')
nscount -= 1;
if(walk[i] == 'e')
ewcount += 1;
if(walk[i] == 'w')
ewcount -= 1;
}
return nscount == 0 && ewcount == 0;
}
```

### Find The Parity Outlier

You are given an array (which will have a length of at least 3, but could be very large) containing integers. The array is either entirely comprised of odd integers or entirely comprised of even integers except for a single integer N. Write a method that takes the array as an argument and returns this “outlier” N.

```
static int find(int[] integers){
// initialize the results variable
int result = 0;
// initialize variable to keep the even/odd count and hold the last even/odd values
int j = 0, k = 0, lastEven = 0, lastOdd = 0;
for (int i = 0; i < integers.length; i++) {
if (integers[i] % 2 == 0) {
j++;
lastEven = integers[i];
}
else {
k++;
lastOdd = integers[i];
}
}
// compare the even/odd count to determine the result
if(j > k)
result = lastOdd;
else
result = lastEven;
return result;
}
```

### Complementary DNA

Deoxyribonucleic acid (DNA) is a chemical found in the nucleus of cells and carries the “instructions” for the development and functioning of living organisms.

If you want to know more: http://en.wikipedia.org/wiki/DNA

In DNA strings, symbols “A” and “T” are complements of each other, as “C” and “G”. Your function receives one side of the DNA (string, except for Haskell); you need to return the other complementary side. DNA strand is never empty or there is no DNA at all (again, except for Haskell).

More similar exercise are found here: http://rosalind.info/problems/list-view/ (source)

```
public static String makeComplement(String dna) {
String complement = "";
char[] ch = dna.toCharArray();
for (char c : ch) {
if(c == 'A')
complement += "T";
if(c == 'T')
complement += "A";
if(c == 'C')
complement += "G";
if(c == 'G')
complement += "C";
}
return complement;
}
```

#### Gap in Primes

The prime numbers are not regularly spaced. For example from 2 to 3 the gap is 1. From 3 to 5 the gap is 2. From 7 to 11 it is 4. Between 2 and 50 we have the following pairs of 2-gaps primes: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43

A prime gap of length n is a run of n-1 consecutive composite numbers between two successive primes (see: http://mathworld.wolfram.com/PrimeGaps.html).

We will write a function gap with parameters:

g (integer >= 2) which indicates the gap we are looking for

m (integer > 2) which gives the start of the search (m inclusive)

n (integer >= m) which gives the end of the search (n inclusive)

In the example above gap(2, 3, 50) will return [3, 5] or (3, 5) or {3, 5} which is the first pair between 3 and 50 with a 2-gap.

So this function should return the first pair of two prime numbers spaced with a gap of g between the limits m, n if these numbers exist otherwise `nil or null or None or Nothing (or … depending on the language).

```
class GapInPrimes {
public static long[] gap(int g, long m, long n) {
long[] result = new long[2];
boolean found = false;
Long[] primes = findPrimes(m, n);
long first = 0;
long second = 0;
for(int i = 0; i < primes.length - 1 ; i++){
first = primes[i];
second = primes[i+1];
if((second - first) == g){
result[0] = first;
result[1] = second;
System.out.println("Final result: " + first + ", " + second);
found = true;
break;
}
}
return found ? result : null;
}
static Long[] findPrimes(long m, long n) {
List<Long> primes = new ArrayList<Long>();
for(long num = m; num <=n; num++) {
if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num % 7 == 0) {
// do nothing
} else {
if(isPrimeOptimized(num)){
primes.add(num);
}
}
}
Long[] array = primes.toArray(new Long[0]);
return array;
}
static boolean isPrimeOptimized(long n) {
if(n < 2) return false;
if(n == 2 || n == 3) return true;
if(n % 2 == 0 || n % 3 == 0) return false;
// Actually, when we test all possible divisors up to n/2, we will discover some factors twice.
// To observe this, rewrite the list of divisors as a list of products, each equal to 100:
// 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2
// Notice that products past 10 × 10 merely repeat numbers which appeared in earlier products.
// For example, 5 × 20 and 20 × 5 consist of the same numbers.
// This holds true for all n: all unique divisors of n are numbers less than or equal to √n,
// so we need not search past that.[1] (In this example, √n = √100 = 10.)
long sqrtN = (long) Math.sqrt(n) + 1;
for(long i = 6L; i <= sqrtN; i += 6) {
if(n % (i - 1) == 0 || n % (i + 1) == 0)
return false;
}
return true;
}
static boolean isPrime(long num) {
if(num<=1) {
return false;
}
for(int i = 2; i < (num / 2); i++) {
if((num % i) == 0)
return false;
}
return true;
}
}
```

```
public static long[] gap(long g, long m, long n) {
return LongStream.iterate(m % 2 == 0 ? m + 1 : m, l -> l + 2).limit((n - m) / 2).filter(l -> BigInteger.valueOf(l).isProbablePrime(5) && BigInteger.valueOf(l + g).isProbablePrime(5)).filter(l -> {
return LongStream.iterate(l + 2, c -> c + 2).limit((g - 2) / 2).parallel().filter(c -> BigInteger.valueOf(c).isProbablePrime(5)).mapToObj(c -> false).findAny().orElse(true);
}).mapToObj(l -> new long[]{l, l + g}).findFirst().orElse(null);
}
```

#### Find the unique number

There is an array with some numbers. All numbers are equal except for one. Try to find it!

It’s guaranteed that array contains at least 3 numbers.

Samples:

new double[]{ 1, 1, 1, 2, 1, 1 }; // => 2

new double[]{ 0, 0, 0.55, 0, 0 }; // => 0.55

```
public static double findUniq(double[] arr) {
Arrays.sort(arr);
return arr[0] == arr[1] ? arr[arr.length - 1] : arr[0];
}
```

#### Number of trailing zeros of N!

Write a program that will calculate the number of trailing zeros in a factorial of a given number.

N! = 1 * 2 * 3 * … * N

Be careful 1000! has 2568 digits…

For more info, see: http://mathworld.wolfram.com/Factorial.html

Approach:

A simple method is to first calculate factorial of n, then count trailing 0s in the result (We can count trailing 0s by repeatedly dividing the factorial by 10 till the remainder is 0).

The above method can cause overflow for slightly bigger numbers as the factorial of a number is a big number (See factorial of 20 given in above examples). The idea is to consider prime factors of a factorial n. A trailing zero is always produced by prime factors 2 and 5. If we can count the number of 5s and 2s, our task is done. Consider the following examples.

n = 5: There is one 5 and 3 2s in prime factors of 5! (2 * 2 * 2 * 3 * 5). So a count of trailing 0s is 1.

n = 11: There are two 5s and eight 2s in prime factors of 11! (2 8 * 34 * 52 * 7). So the count of trailing 0s is 2.

We can easily observe that the number of 2s in prime factors is always more than or equal to the number of 5s. So if we count 5s in prime factors, we are done. How to count the total number of 5s in prime factors of n!? A simple way is to calculate floor(n/5). For example, 7! has one 5, 10! has two 5s. It is not done yet, there is one more thing to consider. Numbers like 25, 125, etc have more than one 5. For example, if we consider 28! we get one extra 5 and the number of 0s becomes 6. Handling this is simple, first, divide n by 5 and remove all single 5s, then divide by 25 to remove extra 5s, and so on. Following is the summarized formula for counting trailing 0s.

Trailing 0s in n! = Count of 5s in prime factors of n!

= floor(n/5) + floor(n/25) + floor(n/125) + ….

```
public static int zeros(int n) {
if(n < 0) //Negative Number Edge Case
return -1;
// Initialize result
int count = 0;
// Keep dividing n by powers of 5 and update count
for (int i = 5; Math.floor(n / i) >= 1; i *= 5)
count += Math.floor(n / i);
return count;
}
```

```
public static int zeros(int n) {
if(n/5 == 0)
return 0;
return n/5 + zeros(n/5);
}
```

Note: This page will be updated periodically. Bookmark this page to make sure that you don’t miss out any updates.