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