C++ Code running for even "147573952589676412928" test case but giving TLE on submission!


#1

I used the normal brute force approach but used the vector of digits instead of strings as appending in string in c++ takes O(n) whereas appending in vector takes O(1) time!
But still, It’s showing TLE on submission!

Here’s the code: Is there any other approach which is more optimized?

vector<int> divide(const vector<int> &number, const int &digit);
bool isOne(vector<int> &A_digits){
    return (A_digits.size() == 1 && A_digits[0] == 1);
}

bool isEven(vector<int> &A_digits){
    return (A_digits[A_digits.size() - 1] % 2 == 0);
}
int Solution::power(string A){
    
    const int digit = 2;
    
    if(A == "1" || A == "0" || A == "")
        return 0;
    
    vector<int> A_digits;
    for(int i = 0; i < A.length(); i++)
        A_digits.push_back(A[i] - 48);
    
    while(!isOne(A_digits) && isEven(A_digits)){ //not one and even then need to process
        A_digits = divide(A_digits, digit);      ///  A = A / 2; when A is even
    }
    
    //as A == "1" 
    if (isOne(A_digits)) return 1;
    
    return 0;
}


vector<int> divide(const vector<int> &number, const int &digit){
    
    vector<int> quotient;
    
    string divisor = "";
    int i = 0;
    if(number[i] == 1){
        divisor += to_string(number[i]);
        i++;
    }
    
    while(i < number.size()){
        
        divisor += to_string(number[i]);
        
        quotient.push_back( (stoi(divisor) / digit) ); 
        
        if(stoi(divisor) % digit != 0)
            divisor = to_string(stoi(divisor) % digit);
        else
            divisor = "";
            
        i++;
    }
            return quotient;
}

#2

This problem is extremely tight with regards to time, so I suggest not to transform the strings into vectors. When you divide the numbers (strings) try to make it as light as possible. Also, you can make a few tricks to test a number is odd or even (check the last bit in the last digit). That’s it.


#3

I had a similar error. I changed str += to_string(some_char) which works in O(n) to str.push_back(some_char) which does it in O(1). You can use some conversion of single digit int to char like push_back(some_int + ‘0’)
Even though i was appending just one character it gave a TLE that way and idk why but it worked with push_back