UVA Problem 100 – The 3n + 1 problem Solution

UVA Problem 100 – The 3n + 1 problem Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem is not for beginners. Due to a simple logical error I failed and failed again.

Before proceeding to understand my solution please check Memoization, Lookup Table, Recursion, Dynamic Programming, Bitwise Operations. Also you may check Algorithmist Solution and Collatz Conjecture. Learned this solution technique is from here.

For this problem we are given two numbers. We need cycle from and including the smaller number to and including the bigger number.

Basically we are to cycle through the given range and find the maximum cycle length among all numbers in the given range.

Here i have used a lookup table to store already calculated cycle lengths. This dramatically decreases running time. Without lookup table my first solution took 0.552 s but when i applied memoization ( this solution ) took only 0.035 s.

0.552 > 0.035 /* See the speed difference */

Another thing is when the number is ODD we need to calculate 3*n+1. But when we calculate 3*n+1 for any ODD number the ODD number becomes EVEN. Now we can divide by 2 in same step since it becomes EVEN. So here i performed 2 steps in the ODD checking code.


 

n = 3, 3*n+1 = 10 /* So calculating 3n+1 for odd number is always even */
n = 7, 3*n+1 = 22 /* Since it becomes even we can perform n/2 in same step */

 

Also another thing to note is that i used,

n >> 1 /* Which does the same thing as n/2 but Faster */

 

So here I calculate the cycle length and store them in table. If the table already contains the definition it returns the cycle length to main(). There I check if the returned cycle length is bigger then existing max cycle length.

Last thing set the first index of table to 1 since I haven’t used any condition to check if the number becomes 1. Also it is much faster than checking every time since the number is bound to converge in 1. So 1 is stored in look table when it is found its immediately returned.

table[1] = 1;

Rest i explained code comments. Hopefully it is easier to understand :).

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

1 10
100 200
201 210
900 1000

Output:

1 10 20
100 200 125
201 210 89
900 1000 174

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 100 ( 3n + 1 )
 */
#include<stdio.h>

#define SIZE 1000002

/* Lookup table for storing previously calculated values */
static unsigned table[SIZE];

/* Returns cycle length for given number */
unsigned cycleLength(register unsigned n){
    /* If the value already exists in the lookup table then return its cycle length */
    if (n < SIZE && table[n])
        return table[n];

    /* Check if number is odd */
    if (n&1){
        if (n < SIZE){
            /* Since 3n+1 becomes an even number, we perform the next step which is divided by two since its even, also +2 since we perform two operations */
            table[n] = 2 + cycleLength((3 * n + 1) >> 1);
            return table[n];
        }else
            /* The value is bigger than table so we calculate and return */
            return 2 + cycleLength((3 * n + 1) >> 1);
    }else{
        if (n < SIZE){
            /* The number is even so we perform number divided two, or bit shift left once */
            table[n] = 1 + cycleLength(n >> 1);
            return table[n];
        }else
            return 1 + cycleLength(n >> 1);
    }
}

int main(){
    unsigned a, b, count;
    register unsigned n;
    /* This is necessary since i don't check for 1 in cycleLength, Also 1st index is always 1 */
    table[1] = 1;

    while (scanf("%u%u", &a, &b) == 2){
        unsigned maxCycle = 0;
        /* The input may contain bigger number first then smaller number */
        if (a < b){
            for (n = a; n <= b; ++n){
                /* Cycle every value between a to b */
                count = cycleLength(n);
                /* We need to find max cycle, so if a cycle count is greater than maxCycle then replace maxCycle */
                if (maxCycle < count)
                    maxCycle = count;
            }
        }else{
            for (n = b; n <= a; ++n){
                count = cycleLength(n);
                if (maxCycle < count)
                    maxCycle = count;
            }
        }
        printf("%u %u %u\n", a, b, maxCycle);
    }
    return 0;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s