UVa100 - 3n + 1 problem

PROBELEM UVa100 link                                                                                                                            SUBMIT

DIFFICULTY - Beginner

PREREQUISITE - loops and basic maths

GOTCHA -

• Integer data type could be enough for this problem.
  But the interim process might not go well with integers.
  For instance, 827370449 is an Integer and odd number.
  3 * 827370449 + 1 = 2482111348 won’t fit into an integer.


• first number i can be greater than j


• Preserve the input sequence in output.

EXPLANATION-

This is basic simulation algorithm , so try first yourself  and submit ,

C/C++ code

#include <stdio.h>
#include <iostream>
#define long long LL
using namespace std;

void swap(int &a, int &b){
    int temp=a;
    a=b;
    b=temp;
}
int main ()
{
    int i, j;
    while ( scanf ("%d %d", &i, &j) != EOF ) {//while file not ends, at the end we have EOF(end of file, which is MACRO defined in stdio.h
        int temp_i = i;
        int temp_j = j;

        if ( i > j ) swap (i, j);
        //making i<j if not

        int max_cycle_length = 0;
        int cycle_length;

        while ( i <= j ) {//from i to j
            unsigned int n = i;
            /*
            here we are using n as temporary variable , because in while loop we are changing n, if
            we would have used i directly then we have changed its value which may give unexpected result
            */
            cycle_length = 1;

            while ( n != 1 ) {//go for each n, which is i
                if ( n % 2 == 1 ) n = 3 * n + 1;
                else n /= 2;
                cycle_length++;
            }

            if ( cycle_length > max_cycle_length )
                max_cycle_length = cycle_length;

            i++;
        }

        printf ("%d %d %d\n", temp_i, temp_j, max_cycle_length);
    }

    return 0;
}

#happy_coding #codebrace