## 100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: input error in 3n+1 problem

Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Re: RUN TIME ERROR on Problem 100

online judge says its RUN TIME ERROR..........
can anyone please help me to find out the problem.........

import java.io.*;
import java.util.*;
public class Main{
public static void main(String [] args)throws IOException{
PrintWriter z = new PrintWriter(System.out);
int min = 0,max = 0;
while(true)
{
int r = 0;
int n = 0,m = 0;
StringTokenizer s = new StringTokenizer(k.readLine());
while(s.hasMoreTokens())
{
n = Integer.valueOf(s.nextToken());
m = Integer.valueOf(s.nextToken());
}
if(n>m)
{
max = n;
min = m;
}
else
{
max = m;
min = n;
}
while(min<=max)
{
int cycle = 0;
int i = min;
while(i != 1)
{
if(i%2==0)
{
i = i/2;
}
else
{
i = 3*i + 1;
}
cycle++;
}
min++;
if(r<cycle)
{
r = cycle;
}
}
z.println(n+" "+m+" "+(++r));
z.flush();
}
}
}

Pete_Aye
New poster
Posts: 2
Joined: Tue Feb 19, 2013 9:28 am
Location: Jos, Nigeria

### TLE in 3n+1 Problem. Why?

Please can anyone tell me why this code is giving me TLE, and how I can make it Accepted?

Code: Select all

``````#include <iostream>

using namespace std;

int main(){
int start, stop, stopHold;
while(true){
std::cin >> start  >> stop;
if(start > 1000000 || start <= 0 || stop > 1000000 || stop <= 0){
break;
}
stopHold = stop;
int max = 0;
int counter = 1;
int i;
int temp = stop;
do{
i = temp;
counter = 1;
while(i > 1){
counter++;
if(i%2 == 0){
i /= 2;
}else{
i = i * 3 + 1;
}
}
if(max < counter){
max = counter;
}
temp--;
}while(temp > start);
std::cout << start << " " << stopHold << " " << max << std::endl;
}
return 0;
}``````

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### Re: TLE in 3n+1 Problem. Why?

There is a sticky thread in Volume I but one of the problems you have is that you assume start <= stop.

Pete_Aye
New poster
Posts: 2
Joined: Tue Feb 19, 2013 9:28 am
Location: Jos, Nigeria

### Re: TLE in 3n+1 Problem. Why?

Darko wrote:There is a sticky thread in Volume I but one of the problems you have is that you assume start <= stop.
Yes, I noticed that from reading other threads, and I have corrected that error. The issue is that now the code is working, and I tested it with the n =1000000 case and there was no 'TLE'. So why am I gettting that on the judge?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### Re: TLE in 3n+1 Problem. Why?

I am not sure how you think you fixed the start>stop issue but it is not fixed in the code you posted.
Try
999999 1

I am not familiar with C++ that much but I am not sure that is how you determine that you reached the end of file.

There is a link to a C solution (if you click around the site):
http://online-judge.uva.es/problemset/data/p100.c.html

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: WA on Problem 100

After the sample input your code gives this RE:
Exception in thread "main" java.lang.NullPointerException
at java.util.StringTokenizer.<init>(StringTokenizer.java:199)
at java.util.StringTokenizer.<init>(StringTokenizer.java:236)
at Main.main(Main.java:12)

You should check if k.readline() returns NULL before passing it to StringTokenizer.
Check input and AC output for thousands of problems on uDebug!

ferry6
New poster
Posts: 2
Joined: Sat Feb 23, 2013 9:43 am

### Re: Newbie can't get AC

Hi I am new here.

MewCatcher
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

### Re: Newbie can't get AC

Specific problem should be asked in corresponding board.
Best wishes!~

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: Newbie can't get AC

There is a thread discussing about 100 where contains all solutions for different languages. You should check that.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

rabeeea2
New poster
Posts: 1
Joined: Fri Mar 01, 2013 12:46 am

### why WA 3n+1

import java.io.IOException;

class Main {

public static void main(String[] args) throws IOException {
new Main().run();
}

void run() throws IOException {
try {

while (!str[0].equals("")) {

long a = Long.parseLong(str[0]);
long b = Long.parseLong(str[1]);
long max = Math.max(a, b);
long resultt = 0;
long mini = Math.min(a, b);
for (long i = max; i >= mini; i--) {
long solved = 1;
long num = i;
while (num != 1) {

if (num % 2 == 0) {
num = num / 2;
} else {
num = num * 3 + 1;
}
solved = solved + 1;
}
resultt = (solved > resultt ? solved : resultt);
}

if (max != 1) {
System.out.println(a + " " + b + " " + resultt);
} else {
System.out.println(a + " " + b + " " + 0);
}

}
} catch (Exception e) {
}
}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: why WA 3n+1

Input:

Code: Select all

``1 1``
Correct output:

Code: Select all

``1 1 1``
Check input and AC output for thousands of problems on uDebug!

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

### Re: If you get WA in problem 100, read me before post!

Code: Select all

``````#include <stdio.h>
#include <vector>

using namespace std;

vector<vector<int> > intervals;
vector<unsigned int> cycles;

int max(unsigned int a, unsigned int b)
{
return a > b ? a : b;
}

int min(unsigned int a, unsigned int b)
{
return a < b ? a : b;
}

int get_cycle_length(unsigned int n, unsigned int cycle)
{
if (n == 1)
return cycle;

if (n % 2 == 0)
{
n = n / 2;

if (n < 999999 && cycles[n])
return cycles[n] + cycle;

get_cycle_length(n, cycle + 1);
}
else
{
n = 3 * n + 1;

if (n < 999999 && cycles[n])
return cycles[n] + cycle;

get_cycle_length(n, cycle + 1);
}
}

int main()
{
unsigned int a, b;
vector<int> interval(2);

while (scanf("%d %d", &a, &b) != EOF)
{
interval[0] = a;
interval[1] = b;
intervals.push_back(interval);
}

unsigned int i;
for (i = 1; i < 999999; i++)
{
cycles.push_back(0);
}

/* Bottom up - fill all cycle lengths */
for (i = 1; i < 999999; i++)
{
cycles[i] = get_cycle_length(i, 1);
}

/* Go through every interval, and for each one go from smaller
number to bigger number and find out the largest cycle length.

Print 'i' and 'j' on the same order they were given.*/

unsigned int max_so_far, u, start_on, end_on;
for (i = 0; i < (int) intervals.size(); i++)
{
start_on = min(intervals[i][0], intervals[i][1]);
end_on = max(intervals[i][0], intervals[i][1]);
max_so_far = cycles[start_on];

for (u = start_on + 1; u <= end_on; u++)
{
if (u < 999999)
max_so_far = max(max_so_far, cycles[u]);
else
max_so_far = max(max_so_far, get_cycle_length(u, 1));
}

printf("%d %d %d\n", intervals[i][0], intervals[i][1], max_so_far);
}

return 0;
}
``````
I am not assuming that i > j or j > i, my code works for all cases. For this critical input I made:

Code: Select all

``````1 1
1 10
9 11
8 12
100 200
201 210
900 1000
1000 900
999999 999990
1 999999
999999 1``````
I get:

Code: Select all

``````1 1 1
1 10 20
9 11 20
8 12 20
100 200 125
201 210 89
900 1000 174
1000 900 174
999999 999990 259
1 999999 525
999999 1 525
./threenplusone < threenplusone_input.txt  0.18s user 0.01s system 98% cpu 0.199 total
``````
I'm running "time" so you can see it runs in very good time, under a second. However, I get Wrong Answer. Any ideas?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: If you get WA in problem 100, read me before post!

Check the PM I just sent you, cycles only had 999998 elements, but you used cycles[999998].
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

### problem no 100 Time Limit Exceeded

Here is my code:
#include<stdio.h>
int len(int x)
{
int max;
max=1;
while(x>1)
{
max++;
if(x%2==0) x=x/2;
else x=3*x+1;

}
return max;
}
int main()
{
int i,prev,a,b,max,num1,num2;
while(1){
scanf("%d %d",&num1,&num2);
prev=num1;
a=len(prev);
for(i=num1;i<num2;i++)
{

b=len(i+1);
if(a>b)
{
max=a;
}
else
{
max=b;
prev=i+1;
a=b;
}
}
printf("%d %d %d\n",num1,num2,max);
}
}

This program takes less than two seconds to find the longest chain between 1 to 1000000. But after submitting it says time limit exceeded. why?