100 - The 3n + 1 problem

[sampad74]

but problem says...

All integers will be less than 10000 and greater than 0.

[sampad74]

I got AC assuming that i or j might be greater than 10000.But,i am confused about the problem statement.please,help me.
Thank you.
brianfry.

[wangmanxf]

int oddEven(int x);
If x is 113383, oddEven() has a dead loop, 3*x+1 and x/2 will lead to a number out of range of int (2^31)
int oddEven(long long x) will be ok.

113383 is just one of the numbers that will be out of 2^31

[wangmanxf]

I solved the 3n+1 problem with two methods. One is Brute-Force, Time limit exceeded.
The other is set a cache[] array to save the previous computed cycle-length.
A solution in Java (I found it through google), and I rewrite it in C, but the Java solution AC, while reimplemented C solution Time limit exceeded. What's wrong with the C solution?

Code: Select all

import java.util.*;
import java.math.*;
import java.io.*;
public class Main {
    // cache for already computed cycle lengths
    public static int[] cache = new int[1000000];
    // a function that returns the
    // next number in the sequence
    public static long next(long n) {
        if (n % 2 == 0)
            return n / 2;       // if n is even
        else
            return 3 * n + 1;   // if n is odd
    }
    public static int cycleLength(long n) {
        // our base case
        // 1 has a cycle length of 1
        if (n == 1)
            return 1;
        // check if we've already cached the
        // cycle length of the current number
        if (n < 1000000 && cache[(int)n] != 0)
            return cache[(int)n];
        // the cycle length of the current number is 1 greater
        // than the cycle length of the next number
        int length = 1 + cycleLength(next(n));
        // we cache the result if the
        // current number is not too big
        if (n < 1000000)
            cache[(int)n] = length;
        return length;
    }
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out, true);
 
        // while there is some input to read
        while (in.hasNextInt()) {
            int i = in.nextInt(),
                j = in.nextInt(),
                from = Math.min(i, j),
                to = Math.max(i, j),
                max = 0;
            // loop through all the numbers
            // and find the biggest cycle
            for (int n = from; n <= to; n++) {
                max = Math.max(max, cycleLength(n));
            }
            out.printf("%d %d %d\n", i, j, max);
        }
    }
}

###############################################################

Code: Select all

#include <stdio.h>
#define MAX 1000000
static int cache[MAX] = {0};
 
long long next(long long n){
    if(n & 1)
        return n + (n << 1)+1;
    else
        return (n >> 1);
}
 
int cl(long long n){
    int l;
 
    if(n == 1)
        return 1;
    if(n < MAX && cache[(int)n] != 0)
        return cache[(int)n];
    l = cl(next(n))+1;
    if(n < MAX)
        cache[(int)n] = l;
    return l;   
}
 
int main(){
    int start,end,i,r,max,tmp,s,e;
 
    printf("Input start&end:\n");
    while(scanf("%d%d",&start,&end)){
        s = start;
        e = end;
        if(start > end){
            tmp = start;
            start = end;
            end = tmp;
        }
        max = 0;    /*critical*/
        for(i = start; i <= end; ++i){
            r = cl(i);
            if(max < r)
                max = r;
        }
        printf("%d %d %d\n",s,e,max);
    }
}

[lighted]

Don't open new thread. Search for existing thread about this problem first.
On every boards Volume header said
If there is a thread about your problem, please use it.

Try to use existing threads and continue it.

Change line

Code: Select all

while(scanf("%d%d",&start,&end)){

to

Code: Select all

while(scanf("%d%d",&start,&end)==2){

[brianfry713]

From the problem statement: "All integers will be less than 1,000,000 and greater than 0. "

[Zargi]

Hey guys,

I think my Problems differs from the others. I've already solved a few other problems but I can't found the solution for this.
Actually I know how to solve the problem and I could also write this one in another language but I want to know WHY this always gives me a Runtime Error.
I tried following:

- Change: public class Main -> class Main
- ReadLn()-Method given from the UVA Java Submission specification instead of Scanner

Any ideas?

Here is my code:

Code: Select all

//Runtime Error
import java.util.Scanner;

public class Main {
	
	private static int counts=0;
	private static Scanner sc;

	private static void calcProb(long i){
		counts++;
		if(i == 1){return;}
		if(i%2 == 1){calcProb(3*i + 1);}
		else{calcProb(i/2);}
	}
	
	public static void main(String[] args){
		sc = new Scanner(System.in);
		while(true){
			long i = sc.nextLong();
			long j = sc.nextLong();
			long max=0;
			long z = i, x = j;
			if(i > j){
				long d = i; i = j; j = d;
			}
			for(long k = i;k<=j;k++){
				calcProb(k);
				if(max < counts) max = counts;
				counts = 0;
			}
			System.out.println(z + " " + x + " " + max);
			if(!sc.hasNextLine()){return;}
		}
	}
}

Greetings

[lighted]

I don't know Java very good.
This way it works

Code: Select all

while(sc.hasNext()){
    ..
    ..
    System.out.println(z + " " + x + " " + max);
}

[Zargi]

Accepted.

Weird, I could swear that I tried something smiliar. But I still don't know why this should cause a Runtime Error.
Anyway, thanks for your help!

Greetings

[brianfry713]

See: http://ideone.com/zk3lf6
Don't forget that there will be a newline char at the end of the last line in the input.

[bafi.farid]

Why this code creating infinite loop?????????????
*************************

Code: Select all

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a,b;
    int max=0,count=0;

        cin>>a>>b;
       if(a>b) swap(b,a);
        for(int i=a;i<=b;i++)
        {
          
            while (i!=1)
            {
                 if(i%2==0)
                    i=i/2;

                 else
                    i=3*i+1;

                count++;
                }
            }
            if(max<count)
            {
                max=count;
            }

            cout <<a <<" "<<b<<" "<< max;

    }

[brianfry713]

Don't modify i if you are using it as a loop iterator. Read this thread.

[efagerho]

Just registered to this site for some interview prep... anyway, tried the first problem as a trivial warmup and I'm getting a "runtime error" with no explanation of what's going wrong. The code is the following:

http://ideone.com/oA5HDc

EDIT: Nevermind... it seems like the fact that I was lazy and didn't bother to add the "return 0;" statement to the main() function caused the error. Although, now it's claiming wrong answer...

[brianfry713]

Input:

Code: Select all

9 1

AC output:

Code: Select all

9 1 20

[dopeorder]

Can someone please tell me what is wrong with my code? I have submitted this more than 3 times and I still get an error!

Code: Select all

#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

int find_cycle_length(int b)
{
	// Finds the max cycle of b
	int max_cycle = 1;
	while (b != 1)
	{
		if (b % 2 != 0)
		{
			b = (3 * b) + 1;
			++max_cycle;
		}
		else if (b % 2 == 0)
		{
			b /= 2;
			++max_cycle;
		}
	}
	return max_cycle;
}
int find_max_cycle(vector <int>& b)
{
	vector <int> temp;
	for (int i = 0; i < b.size(); ++i)
	{
		int buffer = b[i];
		temp.push_back(find_cycle_length(buffer));
	}
	int max_cycle = *max_element(temp.begin(), temp.end());

	return max_cycle;
}

int main()
{
	
		int i = 0; // First number
		int j = 0; // Second number
		int size = 0; // Determines the size of the vector buffer
		int counter = 0; // Used to fill buffer
		cin >> i >> j;
		

		if (j > i) {
			size = (j - i) + 1;
			counter = i;
		}
		else if (i > j) {
			size = (i - j) + 1;
			counter = j;
		}
		else if (i == j)
		{
			size = 1;
			counter = i;
		}

		vector<int> buffer(size); // Used to store all numbers i to j	
		for (int x = 0; x < buffer.size(); ++x) // fill buffer
		{
			buffer[x] = counter;
			++counter;
		}

		cout << i << " " << j << " " << find_max_cycle(buffer) << endl;

}