PROBLEM LINK:
Practice
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : EASY
PREREQUISITES:
Nill
PROBLEM:
Maths teacher of ABC School given a assignment to his student. Assignment consist of 10 questions. one of his student David was able to do All question except the last one.
The Question is
An iterative function f(x) is defined as:
f(x) = x/2 (if x is even)
f(x) = 3x + 1 (if x is odd)
for example if x = 40, it generate the following Chain:
40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
The above Chain starting at 40 and finishing at 1 contains 9 terms. it is thought that all starting numbers finish at 1.
Find the starting number, longest chain (chain with higher number of terms) for the iterative function with in the specified range [Lower limit, Upper limit]
NOTE : Once the chain starts the terms are allowed to go above The Upper Limit
Your task is to help him to solve the question
QUICK EXPLANATION:
For a value x of the iterative function f(x), we can find the number of terms in the chain by counting the number of times a loop will execute. Inside the loop x (loop variable) is altered according to the function definition & loop will terminate when the value of x will become 1.
EXPLANATION:
First, we should get the required input (ie the range of function [Lower limit, Upper limit]).
Second, for a value x of the iterative function f(x), we can find the number of terms in the chain by using a loop. inside the loop value of x(loop variable) is altered according to the function definition (ie if the value of x is even x will become x/2 if it is odd x will become 3x+1). Loop will execute up to the value of x will become 1. The number of times loop executed will give us the no of terms in the chain.
Third, by repeating the second process for all value in the range [Lower limit, Upper limit] we can find the longest chain
SOLUTIONS:
Setter's Solution
#include
using namespace std;
int main()
{
int T;
cin >> T;
while(T!=0)
{
int startNumber,answer=0,limit;
// startNumber = Lower limit ,limit =, Upper limit
int number,terms,saveTerms=0;
cin>>startNumber>>limit;
while(startNumber < limit+1)
{
terms = 1;
number = startNumber;
while (number > 1)
{
while(number % 2 == 0)
{
number /= 2;
terms++;
}
if(number > 1)
{
number = (number * 3) + 1;
terms++;
}
}
if (terms > saveTerms)
{
saveTerms = terms;
answer = startNumber;
}
startNumber++;
}
cout<<“starting number: “<< answer<<” longest chain: “<<saveTerms<<”\n”;
T–;
}
return 0;
}