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

New poster
Posts: 29
Joined: Wed Jun 18, 2014 3:57 pm

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

but problem says...
All integers will be less than 10000 and greater than 0.

New poster
Posts: 29
Joined: Wed Jun 18, 2014 3:57 pm

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

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
New poster
Posts: 2
Joined: Thu Jul 03, 2014 3:26 pm

Re: 3n+ 1 : y u always go WA/RUNTIME!?

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
New poster
Posts: 2
Joined: Thu Jul 03, 2014 3:26 pm

100 3n+1 problem

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;
// 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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 100 3n+1 problem

On every boards Volume header said

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){
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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!

From the problem statement: "All integers will be less than 1,000,000 and greater than 0. "
Check input and AC output for thousands of problems on uDebug!

Zargi
New poster
Posts: 3
Joined: Tue Nov 12, 2013 6:15 pm

100 - Runtime Error

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 100 - Runtime Error

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

Code: Select all

while(sc.hasNext()){
..
..
System.out.println(z + " " + x + " " + max);
}
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Zargi
New poster
Posts: 3
Joined: Tue Nov 12, 2013 6:15 pm

Re: 100 - Runtime Error

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 100 - Runtime Error

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.
Check input and AC output for thousands of problems on uDebug!

bafi.farid
New poster
Posts: 1
Joined: Wed Oct 15, 2014 12:07 am

Re: 100 - The 3n + 1 problem

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;

}
Last edited by brianfry713 on Thu Oct 16, 2014 7:15 pm, edited 1 time in total.
Reason: Added code blocks

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

Re: 100 - The 3n + 1 problem

Don't modify i if you are using it as a loop iterator. Read this thread.
Check input and AC output for thousands of problems on uDebug!

efagerho
New poster
Posts: 2
Joined: Tue Dec 16, 2014 2:38 am

Re: 100 - The 3n + 1 problem

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 100

brianfry713 wrote:Input:

Code: Select all

9 1
AC output:

Code: Select all

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

dopeorder
New poster
Posts: 1
Joined: Thu Jan 15, 2015 2:53 am

Re: 100 - The 3n + 1 problem

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;

}