Yet another number game question-getting "time limit exceeded"

general
1

I submitted the following solution for the problem-Yet another number game.

#include <iostream>

int main()
{
    using namespace std;

    int test;
    int num;
    int k;
    cin >> test;
    int *p = new int[test];

    int b;
    for(int i=0;i<test;i++)
    {
        cin >> num;

        if(num==1){
            p[i] = 1;
        }
        b=0;
        while(num > 1){

            b = b+1;
            if(num%2==0){

                num = num-(num/2);

            }else{

            for(k=3;k<=(num/2);k=k+2)
            {
                if(num%k==0){

                    num = num - (num/k);


                    break;
                }
            }
            if((num%k) != 0){

                num = num-1;
            }

         }

        }
            p[i] = b;


    }
        for(int j=0;j<test;j++)
        {
            if(p[j]%2==0){

                cout << "BOB" << endl;
            }else{

                cout << "ALICE" << endl;
            }

        }

        return 0;
}

But I am getting time limit exceeded .I have tried optimizing my approach but still getting the error.
Please help me fix it.

2

The reason you are getting TLE is because the time complexity of your algorithm is more than what is expected. Any optimizations you do on this algorithm will be useless as n can go upto 10^9.

I would suggest you start again and try to look for a new approach with a better time complexity. Hint : Solve the problem for smaller cases and try to generalize it for all numbers(Induction!!).

1 Like
3

Thanks for your response

4

Hint: try finding a pattern between the input and the output… start by considering small inputs first then generalise it…