Find the number of factors of 5 in natural number n

factors.java

public static int factorsOfFiveIn(int n) {
    int factorsOfFive = 0;
    while (n > 1) {
        if (n % 5 == 0) factorsOfFive++;
        n /= 5;
    }
    return factorsOfFive;
}

Hahaha! This code is wrong. I will fix it soon.

Never mind! I need recursion to make this work at all.

        public static int factorsOfFiveIn(int n) {
            if (n % 5 == 0) return 1 + factorsOfFiveIn(n / 5);
            else return 0;
        }

Here is the Kotlin version of a recursive solution:

fun factorsOfFiveIn(n: Int): Int {
    fun doWork(acc: Int, num: Int): Int =
            if (num <= 1)
            	acc
            else if (num % 5 == 0)
            	doWork(acc + 1, num / 5)
            else
            	doWork(acc, num / 5)
    
    return doWork(0, n)
}

Actually the above solution was based off of your original code (both get 2 when passed 100) so the logic may be a bit off but the idea should still be sound.

You need a helper function inside the actual function that keeps track of the state on the call stack.

Here is a link to the online Try Kotlin version:

https://try.kotlinlang.org/#/UserProjects/mlol4jnc8ordrhqn0dalshiq25/n75mbuk95hvnfji943h6nk5ito

Am I imagining or does my recursive version (the one that actually works) express the intent more directly? "If there's a factor of 5, count it, then pull it out and count the rest." Can we refactor from yours (@mikegehard) to mine? Should we?

I came up with a Swift version similar to @mikegehard's Kotlin. But now that you have one that works… and is expressive…

@jbrains I do feel like your solution is more expressive. Mine was a translation of your original code because I wasn't sure how it was supposed to work...no tests. :-)

The one down side is that the more expressive may not be tail recursive (I always have issues figuring that out) so could blow the stack for large values of n. Try it out to confirm.

@mikegehard If you're translating the original code above, that's wrong. :)

Thanks to everyone for trying. I appreciate any additional comments, especially if you find out that I got something wrong.

I guess you want to obtain the number of numbers divisible by 5 in n.

In C# I would write this function like this

public static int factorsOfFiveIn(int n)
{
return Enumerable.Range(1,n)
.Where(x=>x%5==0)
.Count();
}

It's based on data transformations. Transform the input "n" in a subset of "N" integers, filter those who are divisible by 5. At the end get the cardinal of the subset and it's done.
No loop, no recurssion, it's just data transformation and purely declarative.

PS : mathematicaly speaking the factors of 5 are only (1,5) and (-1, -5). I hope it helps.

Your short recursive version is very expressive imho. It is not tail recusive but that doesn't matter in java as java can't optimize tail recursions anyway...
So for very high n, you will get an Overflow Exception.
This seems to be one of the many things that makes it hard to do functional stuff in plain java.

Found that it seems you can use iterate(...) :

public static long factorsOfFiveIn(int n) {
        IntPredicate while_n_modulo_five_is_zero = x-> x % 5 == 0;
        IntUnaryOperator divide_n_with_five = x -> x/5;
        return IntStream.iterate(n, while_n_modulo_five_is_zero , divide_n_with_five).count();
}  

or more compact, but less readable:

public static long factorsOfFiveIn(int n) {
        return IntStream.iterate(n, x-> x % 5 == 0, x -> x/5).count();
}

@EffectiveLabs Not quite. 25 has the factor 5 twice, so 25! adds 2 zeroes to the end compared to 24!.

I tried to write what you describe with Vavr (Java FP library) and somehow I got it wrong, which led me in the direction I went in the end. I had tried to map n to n%5==0 and then count all the true values. I still don't know how I got that wrong.

@jonsweimarck Thank you for this! I really like the version with the anonymous functions. I didn't know about iterate(), and Vavr's version also has it. This gives me a direction in which to refactor.

Using Vavr's implementations: divide n by 5 as long as n is a multiple of 5, then count the number of times you successfully divided n by 5.

    public static int factorsOfFiveIn(int n) {
        return Stream.iterate(n, divideBy(5))
                .map(isAMultipleOf(5))
                .takeWhile(isTrue())
                .length();
    }

As a post script, I found an alternative implementation of the larger exercise, which makes factorsOfFiveIn() obsolete. :) I'll publish the whole thing somewhere quite soon.