3. Consider the following algorithm

Start with a positive number n

if n is even then divide by 2

if n is odd then multiply by 3 and add 1

continue this until n becomes 1

The Guthrie sequence of a positive number n is defined to be the numbers generated by the above algorithm.

For example, the Guthrie sequence of the number 7 is

7,  22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

It is easy to see that this sequence was generated from the number 7 by the above algorithm. Since 7 is odd multiply by 3 and add 1 to get 22 which is the second number of the sequence. Since 22 is even, divide by 2 to get 11 which is the third number of the sequence. 11 is odd so multiply by 3 and add 1 to get 34 which is the fourth number of the sequence and so on.

Note: the first number of a Guthrie sequence is always the number that generated the sequence and the last number is always 1.

Write a function named isGuthrieSequence which returns 1 if the elements of the array form a Guthrie sequence. Otherwise, it returns 0.

If you are programming in Java or C#, the function signature is

int isGuthrieSequence(int[ ] a)

If you are programming in C++ or C, the function signature is

int isGuthrieSequence(int a[ ], int len) when len is the number of elements in the array.

Solution::

public static int isGuthrieSequence (int[] a){
        int lgh = a.length;
        System.out.println("Array Length : "+ lgh);
        boolean flag = true;
        System.out.println("last : "+ a[lgh -1]);

        if(a[lgh-1] != 1){
         return 0;
         }else{
            for(int i=0; i<lgh-1; i++){
                int first = a[i];
                int laterr = a[i+1];


                if(first % 2 == 0){  //if the number is even
                    int firstTemp = a[i]/2;
                    if(firstTemp == laterr){
                        flag = true;
                    }else{
                        flag = false;
                        break;
                    }
                }else{ //if number is odd
                    int firstTemp = (a[i] * 3)+1;
                    if(firstTemp == laterr){
                        flag = true;
                    }else{
                        flag = false;
                        break;
                    }
                }
            }
        }

        if(flag) return 1;
        else return 0;
}