CODEWITHSUNDEEP
javaalgorithmjava-8java-streamgreatest-common-divisor
Guo Jingxue
Guo Jingxue

Reputation: 41

Finding the Greatest Common Divisor using Java Stream without recursion while/for loops

Please help me out here. I need to convert the following code to one that uses Java Streams. The method used is the Euclidean Algorithm

public int gcd(int m, int n) {
    if (n == 0) {
        return m;
    } else {
        return gcd(n, m%n);
    }

I have already tried to use streams in the following way, however recursions are not allowed and I am stuck at trying to come up with a way without recursion and loops since I am still new to the declarative approach

return IntStream.of(m, n).reduce(0, (x, y) -> gcd(n, m-n));

Upvotes: 2

Views: 1604

Answers (3)

Olimpiu POP
Olimpiu POP

Reputation: 5067

As you are still learning and mentioning the ability to transform from recursive to iterative, I took the liberty of implementing all three options that come in mind for now. The names of the methods are intuitive enough, but better more information than less:

gcdStream - uses the implementation with streams. With some inspiration from here

gcdRecursive - is the classic algorithm based on recursion, the one used by you as well

gcdIterative - is the transformation of the recursive algorithm into an iterative one (typically you transform them using while loops)

gcdStream - implementation using streams. Imo is the closest transformation of the classic algorithm into one based on streams. Nice that it uses for iteration the modulo operator, so it should have less iterations then going linearly

gcdStreamPair - though each one functional, I feel the gcdStream a bit verbose. So, I looked into various options to make it more readable. Replacing the array with an immutable Pair class makes it a bit more readable. See the implementation in the code sample.

Looking into the methods in this way gcdRecursive -> gcdIterative -> gcdStream the translation should feel natural.

I placed all the methods in an UT, typically you could use it straight away. 

import org.junit.jupiter.api.Test;
import java.util.stream.Stream;
import static org.junit.jupiter.api.Assertions.*;

public class GcdStreams {

   @Test
   public void t() {
       int a = 72, b = 48, expectedGcd = 24;

       assertEquals(expectedGcd, gcdStream(a,b));
   }

   private int gcdRecursive(int a, int b) {
       if (b == 0) {
           return a;
       } else {
           return gcd(b, a % b);
       }
   }

   private int gcdIterative(int a, int b) {
      do {
          int first = a;
          a = b;
          b = first % b;
      } while (b != 0);

      return a;
   }

   private int gcdStream(int a, int b) {
         return Stream.iterate(new int[] {a, b}, n -> new int[]{n[1], n[0] % n[1]})
                      .filter(x -> x[1] == 0)
                      .findFirst()
                      .map(x -> x[0])
                      .get();
   }

   private int gcdStreamPair(int a, int b) {
    return Stream.iterate(new Pair(a, b) , n -> new Pair(n.b, n.a % n.b))
                 .filter(x -> x.b == 0)
                 .findFirst()
                 .map(x -> x.a)
                 .get();
    }

    private class Pair {
        final int a,b;
        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
}

Upvotes: 1

WJS
WJS

Reputation: 40062

Just iterate thru all values from 1 to the smallest of the two. Then find the largest one that divides both. 

int gcd = IntStream.rangeClosed(1,Math.min(Math.abs(a),Math.abs(b)))
         .filter(r->a%r == 0 && b%r == 0)
         .max()
         .getAsInt();

a = 72;
b = 48;

gcd = 24;

Note that since you are ultimately dividing by 1, there will always be an answer so you can safely get the optional value. If the gcd is 1 then the numbers are relatively prime

This is very inefficient. Just stick with the iterative Euclidean approach.

Upvotes: 1

Dmitry Pisklov
Dmitry Pisklov

Reputation: 1206

Almost verbatim implementation of Euclidean algo you have as an example with stream:

int gcd(int m, int n) {
    return Stream.iterate(new int[]{m, n}, vals -> new int[] {vals[1], vals[0] % vals[1]}).filter(v -> v[1] == 0).findFirst().get()[0];
}

It uses what's known in functional programming as accumulator concept.

PS it would be more efficient to swap values in the array to avoid creating a new array every time but even with this new array it's much more efficient algo than the brute force one provided in another answer.

Upvotes: 3

Related Questions