100 - The 3n + 1 problem

[mf]

Do not use files. You are supposed to read from standard input (java's System.in) and write to standard output.

[Eather]

please read the problem again. check some test case. You didnt follow this statement>>{ All integers will be less than 1,000,000 and greater than 0.}
so
999999 999999
Hope you will get AC now. Try to solve now.

[lkyip]

import java.lang.*;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
int n = scan.nextInt();
int max = Math.max(m, n);
int min = Math.min(m, n);
int maxCycle = 0;

for(int x=min; x<=max; x++)
{

int temp = x;
int count=1;
while(x!=1)
{
if(x%2 == 1)
{
x=3*x+1;
}else
{
x=x/2;
}
count++;
}
x = temp;
maxCycle = Math.max(maxCycle, count);
}
System.out.println(m+" "+n+" "+maxCycle);
}


}

[mustak0715]

WHY TIME LIMIT EXCEEDED!!!!!
PLEASE HELP!
#include<iostream>
#include<stdio.h>
int counter;
using namespace std;
int retcounter(long n)
{

counter=1;
while(n!=1)
{
counter++;
if(n%2==0)
n=n/2;
else
n=3*n+1;
}
return counter;
}
int main()
{
unsigned long start,end,n,temp;
int max=1;
while(cin>>start>>end)
{
max=1;


cout<<start<<" "<<end;

if(start>end)
{temp=end;
end=start;
start=temp;}
while(start<=end){
counter=retcounter(start);
if(max<counter)
max=counter;

start++;
}
printf(" %d\n",max);
}
return 0;
}

[anjaneyanjan7]

Code: Select all

#include <iostream>


using namespace std;

int main()
{
	long long a,c,b,*arr,i,max=0,n,num;
	
	while(cin >> a >> b){
		arr = new long long[b-a];
		
	
		if(a>b){
		  c = a;
		  a = b;
		  b = c;
		}
		
		max = 0;
		for(i=0;i<b-a+1;i++){
			arr[i] = a+i;
		}

		for(i=0;i<b-a+1;i++){
			n = arr[i];
			num=1;
		
			while(n!=1){
				num++;
				if(n<=b && n>=a)
				       arr[n-a] = 1;	
				if(n%2 == 0){
					n = n/2;
				}
					
				else
					n = 3*n + 1;
			}
			if(max < num)
				max=num;
		}
		
		cout << a << " " << b << " " << max<<endl;		

	}
		return 0;
}

kindly let me knw why I am getting runtime error message

Hi,

This is an automated response from UVa Online Judge.

Your submission with number 8368446 for the problem 100 - The 3n + 1 problem has failed with verdict Runtime error.

This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0.

Best regards,

The UVa Online Judge team

[zobayer]

You are not going to get help if you post like this.
At least include the problem number and name, and search the forum before opening a new thread.
When you paste a code, paste that between code tags like:

Code: Select all

 < your code > 

.
When you get TLE, it means, your program is not fast enough to complete the task in allotted time.

[kema]

I have tested this many times with numerous cases, but I still seem to be getting WA. Can someone please assist me in this matter? Thanks in advance guys!!!

Code: Select all

import java.io.*;
import java.util.*;

public class Main
{

    static int longestChain = 0;

    public static void main (String[] args) throws FileNotFoundException
    {
        //long time = System.currentTimeMillis();
        Scanner sc = new Scanner (new FileReader ("DATA1.txt"));
        while (sc.hasNext ())
        {
            longestChain = 0; //      Reset
            int i = sc.nextInt ();
            int j = sc.nextInt ();
            int min = Math.min (i, j);
            int max = Math.max (i, j);

            for (int a = min ; a <= max ; a++)
            {
                sequence (a, 1);
            }
            System.out.println (i + " " + j + " " + longestChain);
        }
        sc.close ();
        //long time2 = System.currentTimeMillis();
        //System.out.println ("time: "+ (time2-time));
    }


    public static void sequence (int n, int counter)
    {
        if (n == 1)
        {
            longestChain = Math.max (counter, longestChain);
            return;
        }

        else if (n % 2 == 0)
        {
            sequence (n / 2, counter + 1);
        }
        else
        {
            sequence (3 * n + 1, counter + 1);
        }
    }
}

[ihat]

i don't see what the problem is

Code: Select all

#include <iostream>
#include <fstream>

using namespace std;

//Functions
int createCycle(int startPt, int endPt);


int main()
{
	ifstream in_stream;
	int startNum, endNum;

	in_stream.open("input.txt");
	in_stream >> startNum;

	while(!in_stream.eof())
	{
		in_stream >> endNum;

		cout << startNum << " " 
			 << endNum << "  "
			 << createCycle(startNum, endNum) << endl;

		in_stream >> startNum;
	}
	//system("PAUSE");
	return 0;
}

int createCycle(int startPt, int endPt)
{
	int count = 0;
	int maxCount = 0;
	
	while(startPt <= endPt)
	{
		int num = startPt;
		while(num > 1)
		{
			if((num % 2) == 0)
				num /= 2;
			else
				num = num*3+1;
			count++;
		}
		startPt++;

		if (count > maxCount)
			maxCount = count + 1;
		count = 0;
	}
	
	return maxCount;
}

[Michael.Shu]

use printStream and printf instead of system.out.println..... that helped me solve the problem o_o

Code: Select all

deleted after AC.

[mps]

greetings..
can anyone please help me with the below piece of code? am getting runtime error

Code: Select all

#include <iostream>
using namespace std;
unsigned int arr[1000001];
unsigned int comp(unsigned int z)
{
    unsigned int y;
    if (arr[z]==0)
    {  
       if (z%2==0)
         y=z/2;
       else
         y=(3*z)+1;
       arr[z] = comp(y)+1;
    }
   return arr[z];
}

int main()
{
    unsigned int a, b, i, j, x, cnt, maxcnt;
    arr[1]=1;
    while( cin >> a >> b )
     {
           i=a;
           j=b;
           if (i>j)
              swap( i, j);
           maxcnt=0;
           cnt =0;
             for (x=i;x<=j;x++)
             {
                cnt = comp(x);
                maxcnt=maxcnt<cnt?cnt:maxcnt;
             }
            cout<<a<<" "<<b<<" "<<maxcnt<<"\n";
     }
return 0;
}

[mps]

Greetings..

Can someone please help me point out whats causing the Runtime error in the below code?

Code: Select all

#include <iostream>
using namespace std;
unsigned int arr[1000001];
unsigned int comp(unsigned int z)
{
    unsigned int y;
    if (arr[z]==0)
    {  
       if (z%2==0)
         y=z/2;
       else
         y=(3*z)+1;
       arr[z] = comp(y)+1;
    }
   return arr[z];
}

int main()
{
    unsigned int a, b, i, j, x, cnt, maxcnt;
    arr[1]=1;
    while( cin >> a >> b )
     {
           i=a;
           j=b;
           if (i>j)
              swap( i, j);
           maxcnt=0;
           cnt =0;
             for (x=i;x<=j;x++)
             {
                cnt = comp(x);
                maxcnt=maxcnt<cnt?cnt:maxcnt;
             }
            cout<<a<<" "<<b<<" "<<maxcnt<<"\n";
     }
return 0;
}

Thanks in advance

[mps]

found the bug.. i was trying to access arr where i was more than 1000001 (max size defined). Put a check to see if i is less than the arr size and then try to access it.

Code: Select all

unsigned int comp(unsigned int z)
{
    if(z<=1000001)
    {
    if (arr[z]==0)
    {  
       if (z%2==0)
         arr[z] = comp(z/2)+1;
       else
         arr[z] = comp((3*z)+1)+1;
    }
    return arr[z];
    }
    else
    { 
       if (z%2==0)
         return (comp(z/2)+1);
       else
         return (comp((3*z)+1)+1);
    }
}

solution accepted with runtime of 0.044. yippiee..

[mps]

found the bug.. i was trying to access arr where i was more than 1000001 (max size defined). Put a check to see if i is less than the arr size and then try to access it.

Code: Select all

unsigned int comp(unsigned int z)
{
    if(z<=1000001)
    {
    if (arr[z]==0)
    {  
       if (z%2==0)
         arr[z] = comp(z/2)+1;
       else
         arr[z] = comp((3*z)+1)+1;
    }
    return arr[z];
    }
    else
    { 
       if (z%2==0)
         return (comp(z/2)+1);
       else
         return (comp((3*z)+1)+1);
    }
}

solution accepted with runtime of 0.044. yippiee..

[niemic]

The max number of elements is greater than your array.

Example:

input value of 3 -> 3 10 5 16 8 4 2 1 , so there will be 8 elements

[xavi]

I cannot figure out what is wrong with my code. It only works for "small numbers", for "big numbers" (n > 950, aprox) the program exits (segmentation fault). I believe that the code fails when uses resize(), but I cannot see what is the problem exactly. Can anyone help, please?

Code: Select all

#include <iostream>
#include <vector>
using namespace std;

int coll(vector<int>& v, long long int a) {
	if(a >= v.size()) {
		v.resize(a+2);
	}
	
	if(v[a] != 0) {
		return v[a];
	
	}
	else {
		if(a%2 == 0) {
			v[a] = coll(v, a/2) + 1;
			return v[a];
		}
		else {
			v[a] = coll(v, 3*a + 1) + 1;
			return v[a];
		}
	}
}

int main() {
	vector<int> p(3);
	p[0] = 0;
	p[1] = 1;
	p[2] = 2;

	int n1, n2;
	while(cin >> n1 >> n2) {
		int current;
		int max = 0;
		if(n1 >= n2) {
			swap(n1, n2);	
		}
		for(int i = n1; i <= n2; ++i) {	
			current = coll(p, i);
			if(current > max) {
				max = current;
			}								
		}
		cout << n1 << " " << n2 << " " << max << endl;	
	}
}

Input:
1 10
100 200
201 210
900 1000

Output:
1 10 20
100 200 125
201 210 89
Segmentation fault

Thanks