Calculate the join point of two sequences recursively in Java

09 Jun, 2022 Java 7

We consider the sequence of numbers in which a number is followed by the same number plus the sum of these digits.

For example 34 is followed by 41 (41 = 34 + (3+4)).

41 is itself followed by 46 (46 = 41 + (4+1)).

Two sequences with different starting points can end up joining. For example, the sequence that starts at 471 and the sequence that starts at 480 share the number 519 (the join point). Obviously after the join point, the sequences are identical.

The program below calculates the join point of two starting points given as parameters in a recursive way.

public class JoinPointExample {

    private static int MAX = 10000000;

    /**
     * Sum the digits of n
     * @param n number
     * @return the sum of digits
     */
    private static int sumDigits(int n) {
        int sum = 0;
        int num = n;

        while(num > 0) {
            sum = sum + num%10;
            num = num / 10;
        }

        return sum;
    }

    /**
     * Compute the join point of two sequences.
     * @param sequence1 the start point of sequence 1
     * @param sequence2 the start point of sequence 2
     * @return the join point, -1 in case of failure
     */
    public static int computeJoinPoint(int sequence1, int sequence2) {

        // If one of the sequence exceeds the maximum, then return -1
        if(sequence1 >= MAX || sequence2 >= MAX) {
            return -1;
        }

        // if sequence1 equals sequence2, then join point is
        // sequence1 (as well sequence2)
        if(sequence1 == sequence2) {
            return sequence1;
        }

        // next1 is the next point following sequence1
        int next1 = sequence1 + sumDigits(sequence1);

        // next2 is the next point following sequence2
        int next2 = sequence2 + sumDigits(sequence2);

        // if next1 equals sequence2, the join point is next1 (as well sequence2)
        if(next1 == sequence2) {
            return next1;
        }

        // if next2 equals sequence1, the join point is next2 (as well sequence1)
        if(next2 == sequence1) {
            return next2;
        }

        // if next1 equals next2, the join point is next1 (as well next2)
        if(next1 == next2) {
            return next1;
        }

        // If next 1 is strictly less than sequence2, then compute join of next1 and sequence2
        if(next1 < sequence2) {
            return computeJoinPoint(next1, sequence2);
        }

        // If next2 is strictly less than sequence1, then compute join of next2 and sequence1
        if(next2 < sequence1) {
            return computeJoinPoint(next2, sequence1);
        }

        // Otherwise, compute join of next1 and next2
        return computeJoinPoint(next1, next2);

    }

    public static void main(String[] args) {
        int sequence1 = 471;
        int sequence2 = 480;

        System.out.println("The join point of " + sequence1 + " and " + sequence2
                + " is : " + computeJoinPoint(sequence1, sequence2));
    }
}

Output :

The join point of 471 and 480 is : 519

zeroTutorials

Have a Question?

Calculate the join point of two sequences recursively in Java