# Thread: Can you find the error?

1. ## Can you find the error?

This is the Problem Statement:
The 3n + 1 Problem
Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If
n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value
of n, terminating when n = 1. For example, the following sequence of numbers will be generated for
n = 22:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n.
Still, the conjecture holds for all integers up to at least 1; 000; 000.
For an input n, the cycle-length of n is the number of numbers generated up to and including the
1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to
determine the maximum cycle length over all numbers between i and j, including both endpoints.
Input
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.
Output
For each pair of input integers i and j, output i, j in the same order in which they appeared in
the input and then the maximum cycle length for integers between and including i and j. These three
numbers should be separated by one space, with all three numbers on one line and with one line of
output for each line of input.
Sample Input
1 10
100 200
201 210
900 1000
Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174

I had written the following C++ code for it:
Code:
```//110101 The 3n + 1 Problem
# include <iostream>
using namespace std;
int main()
{
int i,j,k,x,n1,n,m=909,mmax; /*m= a random number that i expect will never appear in the program. just so that the program keeps repeating and exits only on <ctr+c> */

do
{
cin>> i>>j;
n=j-i;int  counter[n+1];//n is the size for this counter array
if ((i<1000000) && (i>0) && (j<1000000) && (j>0))
{
for (x=0;x<=n;x++)
counter[x]=1;
x=0;
for (k=i;k<=j;k++)
{
n1=k;
while (n1!=1)
{if ((n1%2)==0)
{n1= n1/2; counter[x]=counter[x]+1;}
else
{n1= n1*3; n1++;  counter[x]=counter[x]+1;}
}
x++;
}
mmax=counter[0];
for (x=1;x<=n;x++)
if (counter[x]>mmax)
mmax=counter[x];
cout <<i<<" "<<j<<" "<<mmax<<"\n";
}
else cout<<"invalid input!";
} while (m==909);
}```

I submit this code on the website which had asked for it, but it says "Wrong Answer". I am not able to find any mistake in this. Can anyone please check and let me know what my mistake is? It is not a presentation error. Thanks a lot. Would be of great help.

2. I can't find any thing wrong (thought your indentation,variable naming and organization doesn't exactly help looking). If its a website with an automatic checker it may no be expecting an infinite loop and outputs wrong answer cause as far as it is concerned the program failed to terminate.

3. Note that variable length arrays are not part of standard C++, so if the compiler for the automatic checker does not allow for such a language extension, your code will not even compile.

4. @laserlight
The site provides for a separate section/ count for compilation errors. There are 0 compilation errors.

@killme
Yes I am sorry I haven't presented a neat code here. And regarding the infinite loop, yes that could be a possible reason. But in that case, what do you suggest I should do? The i/p and o/p format provided in the question is not flexible enough to let me ask the user if he wants to have another round of this play. In that case, how can I improve the code?

5. Well, I'm assuming whoever runs the website wrote a small script that automaticly calls all answers submitted several times in order to test (that is usually the case). So you can just remove the loop and make the program a "one-off", the website itself will run it as often as it was designed for.

You are trying to increase flexibility which is great for human users... automated ones are usually "less impressed".

6. Thanks, but I already tried the single-run program. Didn't work

7. Does your test output using the given sample input match the sample output exactly? Sometimes tiny formatting differences can cause problems for automated checkers.

8. Yes it does. And there is a separate section/ count for "presentation errors" on their site, which is 0.

There probably is some input for which I may not be getting the right output, just maybe..

9. Okay, post your current program. Use a common indent style and have each statement on its own line.

10. Here it is:
Code:
```//110101 The 3n + 1 Problem
# include <iostream>
using namespace std;
int main()
{
int i,j,k,x,n1,n,m=909,maxcount; //x=index of counter, n=no fo elements in counter, maxcount is the max element from the counter
cin>> i>>j;
n=j-i;
int  counter[n+1];
if ((i<1000000) && (i>0) && (j<1000000) && (j>0))
{
for (x=0;x<=n;x++)
counter[x]=1;
x=0;
for (k=i;k<=j;k++)
{
n1=k;
while (n1!=1)
{
if ((n1%2)==0)
{
n1= n1/2;
counter[x]=counter[x]+1;
}
else
{
n1= n1*3; n1++;
counter[x]=counter[x]+1;
}
}
x++;
}
maxcount=counter[0];
for (x=1;x<=n;x++)
if (counter[x]>maxcount)
maxcount=counter[x];
cout <<i<<" "<<j<<" "<<maxcount<<"\n";
}
else cout<<"invalid input!";
return (0);
}```

11. The above program is only for 1 set of input.

The catch is here... "The input will consist of a series of pairs of integers i and j, one pair of integers per line."
But now how do I know when to stop accepting inputs?

12. When the EOF condition has been reached.

13. I made some modifications and wrote this now:

Code:
```//110101 The 3n + 1 Problem
# include <iostream>
# include <fstream>
using namespace std;
int main()
{
int i,j,k,x,n1,n,maxcount,temp=0; /*x=index of counter, n=no fo elements in counter, maxcount is the max element from the counter*/
while (cin>> i>>j)
{
if ((i<1000000) && (i>0) && (j<1000000) && (j>0))
{
if(i > j)
{temp=i;i=j;j=temp;}
n=j-i;
int  counter[n+1];
for (x=0;x<=n;x++)
counter[x]=1;
x=0;
for (k=i;k<=j;k++)
{
n1=k;
while (n1!=1)
{
if ((n1%2)==0)
{
n1= n1/2;
counter[x]=counter[x]+1;
//x++;
}
else
{
n1= n1*3; n1++;
counter[x]=counter[x]+1;
//x++;
}
}
x++;
}
maxcount=counter[0];
for (x=1;x<=n;x++)
if (counter[x]>maxcount)
maxcount=counter[x];
cout <<i<<" "<<j<<" "<<maxcount<<"\n";
}
else cout<<"invalid input!";
}
return (0);
}```
But it still shows "Wrong answer". However, I have got my hands on a program (that I found online) that gives the correct result.

Code:
```#include <iostream>
using namespace std;
int length(int n)
{
int i = 1;
while(n != 1)
{
if(n % 2 == 0)
{
n /= 2;
}
else
{
n *= 3;
n += 1;
}
i++;
}
return i;
}
int main()
{
int a, b, low, high;
while(cin>>a>>b)
{
if(a < b)
{
low = a;
high = b;
}
else
{
low = b;
high = a;
}
int max = length(low);
for(int i = low + 1; i <= high; i++) {
int l = length(i);
if(l > max) {
max = l;
}
}
cout<<a<<" "<<b<<" "<<max<<endl;
}
return 0;
}```
But I still cannot find the mistake in my program

14. I haven't managed to compile any of your codes posted here (but the one you looked up online) nor do I understand why they should work.

-Arrays must have a constant size. You may not change it throughout your program.

>int counter[n+1]
This is wrong.

I'd say use vectors instead of arrays.

Also, the usage of magic numbers isn't healthy programming. You should avoid them, even though I see you fixed it on your latest version.

As for the problem itself I don't really undertand why are there 2 inputs. Shouldn't it be just 1 so it would give the cycle length from that number until 1?

15. Originally Posted by Khabz
As for the problem itself I don't really undertand why are there 2 inputs. Shouldn't it be just 1 so it would give the cycle length from that number until 1?
Based on the good posted solution the answer is to be the largest run of values between the two numbers (including the starting and ending numbers).

Note: I do NOT know of any C++ Compiler that supports Variable Length Arrays (VLA)[Part of recent C Standards]; but, if one exists the code might compile with it.
[I am a C programmer, so I use few C++ Compilers.]

To OP: I would write a function that does the same as "int length(int n)" does in the good solution.
Then, write a second function that calls that function using the logic you are trying to use to solve the problem.
This is a case where functions make the problem much easier to solve and understand the solution.

Tim S.

Popular pages Recent additions