## 100 - The 3n + 1 problem

Moderator: Board moderators

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

### Re: 100 - The 3n + 1 problem

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

Your code is only processing the first pair of integers. You need to continue to read until EOF.
Change:
cin >> i >> j;
to:
while(cin >> i >> j) {
Check input and AC output for thousands of problems on uDebug!

coder.tanvir
New poster
Posts: 11
Joined: Mon Mar 09, 2015 10:30 am

### Re: 100 - The 3n + 1 problem

how to reduce the run time ?? i get accepted 0.690s

fiamma
New poster
Posts: 1
Joined: Fri Mar 20, 2015 6:50 pm

### Re: 100 - The 3n + 1 problem

i got time exceeded error, anyone know how can i reduce this time?

Code: Select all

``````#include <stdio.h>
void swap( long int* x, long int* y)
{
long int temp;

temp = *x;
*x    = *y;
*y    = temp;
}
int main(){
long int i,j, act_value, aux, count, max;
while (scanf("%d %d" , &i, &j) != EOF){
max=0;
printf("%d %d", i, j);
if (i>j) swap (&i, &j);
for (act_value=i;act_value<=j; act_value++){
aux= act_value;
count=1;
while(aux!=1){
if(aux%2 ==1) aux =(aux*3)+1;
else aux=aux/2;
count++;
}
if (count>= max) max =count;
}
printf(" %d \n",max);
}

return (0);}
``````

coder.tanvir
New poster
Posts: 11
Joined: Mon Mar 09, 2015 10:30 am

### Re: 100 - The 3n + 1 problem

write another function who can calculate the max length , then just call from main . dont know why this way reduce time , its work for me.

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

### Re: 100 - The 3n + 1 problem

fiamma, use %ld for long int. Don't print a space at the end of a line.
Check input and AC output for thousands of problems on uDebug!

dipu008
New poster
Posts: 1
Joined: Sun Jun 28, 2015 10:47 am

### Re: 100 - The 3n + 1 problem

I have posted this code and got wrong answer. What is the problem here? Thanks in advance.
The code is in ANSI C

Code: Select all

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

int f(int i);

int main()
{
int num1, num2, n, i, j, h;
while(scanf("%d %d", &num1, &num2) == 2){
n = 0;
for(i=num1; i<=num2; i++){
j = f(i);
if(n < j) {
n = j;
h = i;
}
}
printf("%d %d %d\n", num1, num2, n+1);
}
return 0;
}

int f(int n)
{
int i;
for(i=0; n!=1;i++){
if(n%2){
n = 3 * n + 1;
}
else if(!(n%2)){
n = n / 2;
}
}

return i;
}``````

apcastelein
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

### Re: 100 - The 3n + 1 problem

Your f function isn't working properly. If 1 is inputted the output should be 1 however in your case the output is 0.

TamceJoe
New poster
Posts: 3
Joined: Wed Sep 16, 2015 4:23 pm

### Re: 100 - The 3n + 1 problem

i got a problem... i test my program on my pc and it works perfectly well but i got Wrong Answer online.
i use random in put on 'www.udebub.com/Uva/100' & there's no difference between my output and the answers.
i use queue and map trying to save time but i dont know how good is it working.
What's wrong with my code? Tks a lot.

Code: Select all

``````#include <cstdio>
#include <queue>
#include <map>

using namespace std;

typedef unsigned long int_t;

map<int_t, int_t> record;

void calc(int_t);

int main()
{
int_t a = 0, b = 0, m = 0;
int_t l = 0, r = 0;
bool first = true;
while(scanf("%ld%ld", &l, &r) == 2)
{
if(l > r) a = r, b = l;
else a = l, b = r;
for(int_t i = a; i <= b; ++i)
calc(i);
m = 0;
for(int_t i = a; i <= b; ++i)
m = m > record[i] ? m : record[i];
if(first) printf("%ld %ld %ld", l, r, m + 1);
else printf("\n%ld %ld %ld", l, r, m + 1);
first = false;
}
return 0;
}

void calc(int_t t)
{
queue<int_t> a;
while(t != 1)
{
if(record[t] != 0) break;
a.push(t);
if(t % 2 == 0)
t /= 2;
else
t = 3 * t + 1;
}
int_t base = record[t];
while(!a.empty())
{
if(record[a.front()] != 0) break;
record[a.front()] = a.size() + base;
a.pop();
}
}``````

TamceJoe
New poster
Posts: 3
Joined: Wed Sep 16, 2015 4:23 pm

### Re: 100 - The 3n + 1 problem

TamceJoe wrote:i got a problem... i test my program on my pc and it works perfectly well but i got Wrong Answer online.
i use random in put on 'www.udebub.com/Uva/100' & there's no difference between my output and the answers.
i use queue and map trying to save time but i dont know how good is it working.
What's wrong with my code? Tks a lot.

Code: Select all

``````#include <cstdio>
#include <queue>
#include <map>

using namespace std;

typedef unsigned long int_t;

map<int_t, int_t> record;

void calc(int_t);

int main()
{
int_t a = 0, b = 0, m = 0;
int_t l = 0, r = 0;
bool first = true;
while(scanf("%ld%ld", &l, &r) == 2)
{
if(l > r) a = r, b = l;
else a = l, b = r;
for(int_t i = a; i <= b; ++i)
calc(i);
m = 0;
for(int_t i = a; i <= b; ++i)
m = m > record[i] ? m : record[i];
if(first) printf("%ld %ld %ld", l, r, m + 1);
else printf("\n%ld %ld %ld", l, r, m + 1);
first = false;
}
return 0;
}

void calc(int_t t)
{
queue<int_t> a;
while(t != 1)
{
if(record[t] != 0) break;
a.push(t);
if(t % 2 == 0)
t /= 2;
else
t = 3 * t + 1;
}
int_t base = record[t];
while(!a.empty())
{
if(record[a.front()] != 0) break;
record[a.front()] = a.size() + base;
a.pop();
}
}``````
oh i got my solution accepted.
i thought there is no new line at the end of the output because the output on udebug does not show a new line

TamceJoe
New poster
Posts: 3
Joined: Wed Sep 16, 2015 4:23 pm

### Re: 100 - The 3n + 1 problem

and use queue & map cost about 0.7s but do the calculate every time only cost 0.2s
xd

UvaPitu
New poster
Posts: 1
Joined: Mon Apr 11, 2016 1:57 am

### Re: 100 - The 3n + 1 problem

I am trying to submit my own version of The 3n+1 problem but i get the same result: Runtime Error. I edited many times my code but i am still getting this error and I don't know the reason. I hope you can help me, what i can do to get an AC.

I write my last edited code in the following lines:

Code: Select all

``````import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

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

long Fef(long x)
{
long cicles = 0;
long  temp = x;
while (temp != 1)
{
if (temp % 2 == 0)
{
temp = temp /2;
cicles++;
}
else
{
temp = 3 * temp + 1;
temp = temp / 2;
cicles = cicles + 2;
}
}
cicles++;
return cicles;
}
long MaxF(long from, long to)
{
long maximum = -1;
for (long i = from; i <= to; i++)
{
long result = Fef(i);
if (result > maximum)
maximum = result;
}
return maximum;
}
private final long MAX = 1000000; // the maximum value accepted

public void run()
{

StringTokenizer idata;
String line = null;
try {
long from_value = 0;
long to_value = 0;

while ( line != null )
{
idata = new StringTokenizer(line);

while(idata.hasMoreTokens())
{
if( from_value <= 0 && idata.hasMoreTokens() )
from_value = Long.parseLong(idata.nextToken());
if( to_value <= 0 && idata.hasMoreTokens() )
to_value = Long.parseLong(idata.nextToken());
if( from_value > 0 && to_value > 0 )
{
long from, to;
if (from_value > to_value)
{
from = to_value;
to = from_value;
}
else
{
from = from_value;
to = to_value;
}
if( from > 0 && to < MAX)
System.out.printf("%d %d %d\n", from_value, to_value, MaxF(from, to));
from_value = -1;
to_value = -1;
}
}
}
} catch (IOException e) {
e.printStackTrace();
}
}

}``````
I will appreciate any comments or guidelines. Thanks!

selection989
New poster
Posts: 1
Joined: Fri May 06, 2016 5:34 pm

### Re: 100 - The 3n + 1 problem

Hi there,

I am having trouble getting it to work in python. I keep getting a time limit exceeded. Any suggestions would be much appreciated. Here is my code:
import sys
from sys import stdin

def main():

for line in stdin:
curr_line=line.split()
if curr_line[0]<=curr_line[1]:
min_num=int(curr_line[0])
max_num=int(curr_line[1])
else:
max_num=int(curr_line[0])
min_num=int(curr_line[1])
maxCycleLength =0
for curr_num in range(min_num,max_num+1):
currCycleLength =1
while curr_num!=1:
currCycleLength +=1
if curr_num%2==0:
curr_num=curr_num/2
else:
curr_num=3*curr_num+1
maxCycleLength=max(currCycleLength,maxCycleLength)
print(curr_line[0],curr_line[1],maxCycleLength,sep=" ")

return
main()
sys.exit()

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 100 - The 3n + 1 problem

Try input:

Code: Select all

``````999999 1
``````
To avoid TLE, you should use memoization to store the results calculated, use it directly instead of calculating it again.
For example, n = 21, the sequences below produced:

Code: Select all

``````21 64 32 16 8 4 2 1
``````
so, when you got the steps of 21, you can calculate the steps of 64 by add 1 step.

pk__modi
New poster
Posts: 1
Joined: Mon Aug 01, 2016 7:52 pm

### Re: 100 - The 3n + 1 problem

someone plz help why am i getting TLE:

#include<iostream>
#include<cstdio>
#include<cstdlib>

#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)

int main()
{
int i,j,min,max,maximum=0;
while(scanf("%d%d",&i,&j))
{ max=max(i,j);
min=min(i,j);
maximum=0;
while(min<=max)
{
int count=1;
int k=min;
while(k>1)
{
k=(k%2)?(3*k+ 1):(k>>1);

count++;
}

min++;
if(count>maximum) maximum=count;

}
printf("%d %d %d\n",i,j,maximum);
}
return 0;
}

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek