Skip to content

Instantly share code, notes, and snippets.

@jbrains
Created July 22, 2018 23:49
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jbrains/dbadc637ea9e088d49220acce830a1be to your computer and use it in GitHub Desktop.
Find the number of factors of 5 in natural number n
public static int factorsOfFiveIn(int n) {
int factorsOfFive = 0;
while (n > 1) {
if (n % 5 == 0) factorsOfFive++;
n /= 5;
}
return factorsOfFive;
}
@jbrains
Copy link
Author

jbrains commented Jul 22, 2018

Pitch me some good functional ways to write this.

@jbrains
Copy link
Author

jbrains commented Jul 22, 2018

I tried something like this loop, but mapping the interim n to a boolean with n % 5 == 0, then counting the booleans, but (1) it felt circuitous and (2) it didn't work. :P

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

Recursion seems like it would work. Something like 1 + factorsOfFiveIn(n / 5)?

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

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

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

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;
        }

@mikegehard
Copy link

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)
}

@mikegehard
Copy link

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.

@mikegehard
Copy link

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

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?

@jonreid
Copy link

jonreid commented Jul 23, 2018

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

@mikegehard
Copy link

mikegehard commented Jul 23, 2018

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

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

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

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

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

@MoveNextFr
Copy link

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.

@jonsweimarck
Copy link

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.

@jonsweimarck
Copy link

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();
}

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

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

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

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

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

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();
    }

@jbrains
Copy link
Author

jbrains commented Jul 23, 2018

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment