1 / 7
Jul 2013

I have been trying to approach this problem by storing the numbers as strings (as they are too long) and checking if the left half of the number is greater than right hand of the number (digit by digit by using offsets) and forming the answer by reversing these strings. The answers I get are correct but as mentioned I am getting SIGABRT error.
As this is one of my initial submissions, I would be very glad if you help me out with this.
I am still using iostream as it is not giving the 'time taken too long' or any such error. My code(edited as suggested by leppy):
[bbone=text,592]#include

include

include

using namespace std;

string incrementDigitByOne(int position, string number){
if(number[position] != '9'){
number[position] = number[position] + 1;
return number;
}else{
if(position == 0){
number.replace(0, 1, "0");
number = "1" + number;
return number;
}else{
number.replace(position, 1, "0");
number = incrementDigitByOne(position-1, number);
return number;
}
}
}
bool checkPalindromeForEven(string input_number, int offset){
int string_size = input_number.size();
if(input_number.at(string_size/2-1-offset) == input_number.at(string_size/2+offset)){
if(offset == string_size/2-1){
return true;
}else{
return checkPalindromeForEven(input_number, offset+1);
}
}else{
return false;
}
}
bool checkPalindromeForOdd(string input_number, int offset){
return false;
}
string checkIfAlreadyAPalindrome(string input_number){
int string_size = input_number.size();
if(string_size%2 == 0){
if(checkPalindromeForEven(input_number, 0)){
input_number.assign(incrementDigitByOne(string_size/2, input_number));
}
}else{
if(input_number.size() <= 1){
input_number = incrementDigitByOne(0, input_number);
}else{
if(checkPalindromeForOdd(input_number, 0)){
input_number = incrementDigitByOne(string_size/2, input_number);
}
}
}
return input_number;
}
bool needsIncrementForEven(string input_number, int offset){
int string_size = input_number.size();
if(input_number.at(string_size/2-1-offset) < input_number.at(string_size/2+offset)){
return true;
}else if(input_number.at(string_size/2-1-offset) > input_number.at(string_size/2+offset)){
return false;
}else{
return needsIncrementForEven(input_number, offset+1);
}
}
bool needsIncrementForOdd(string input_number, int offset){
int string_size = input_number.size();
if(input_number.at(string_size/2-1-offset) < input_number.at(string_size/2+1+offset)){
return true;
}else if(input_number.at(string_size/2-1-offset) > input_number.at(string_size/2+1+offset)){
return false;
}else if(offset != string_size/2-1){
return needsIncrementForOdd(input_number, offset+1);
}else{
return true;
}
}
bool checkIfAllNines(string input_number, int start_position){
if(input_number.at(start_position) == '9' && start_position != input_number.size()-1){
return checkIfAllNines(input_number, start_position+1);
}else if(input_number.at(start_position) != '9'){
return false;
}else{
return true;
}
}

int main(int argc, char** argv) {
string string_number_of_times;
getline(cin, string_number_of_times);
int number_of_times = atoi(string_number_of_times.c_str());

while(number_of_times > 0){
    string input_number;
    getline(cin, input_number);
    string answer_string;

    if(checkIfAllNines(input_number, 0)){
        input_number = incrementDigitByOne(input_number.size()-1, input_number);
    }
    input_number = checkIfAlreadyAPalindrome(input_number);

    int string_size = input_number.size();
    if(string_size%2 == 0){
        if(needsIncrementForEven(input_number, 0)){
            answer_string = input_number.substr(0, string_size/2);
            answer_string = incrementDigitByOne(answer_string.size()-1, answer_string);
            answer_string += string(answer_string.rbegin(), answer_string.rend());
        }else{
            answer_string = input_number.substr(0, string_size/2);
            answer_string += string(answer_string.rbegin(), answer_string.rend());
        }
    }else{
        if(input_number.size() <= 1){
            answer_string = input_number;
        }else{
            if(needsIncrementForOdd(input_number, 0)){
                answer_string = input_number.substr(0, string_size/2);
                answer_string += input_number.at(string_size/2);
                answer_string = incrementDigitByOne(answer_string.size()-1, answer_string);
                string temp_string = answer_string.substr(0, answer_string.size()-1);
                temp_string = string(temp_string.rbegin(), temp_string.rend());
                answer_string += temp_string;
            }else{
                answer_string = input_number.substr(0, string_size/2);
                string temp_string = string(answer_string.rbegin(), answer_string.rend());
                answer_string += input_number.at(string_size/2);
                answer_string += temp_string;
            }
        }
    }
    cout << answer_string;
    cout << "\n";
    --number_of_times;
}

return 0;

}[/bbone]

  • created

    Jul '13
  • last reply

    Sep '20
  • 6

    replies

  • 771

    views

  • 3

    users

  • 1

    link

Don't try to store all of the strings for output in an array, that will be huge. Just use a single string.

  1. Read number of test cases
  2. Read an input
  3. process the solution
  4. output it
  5. If there are more test cases goto 1

Still stuck..
I corrected it according to Leppy's suggestion..
Please help me out here..

Checkifallnines creates a new copy of the input string at each level of recursion. The input string is over 1000000 digits long. This means that you will be trying to assign 1000000x1000000 characters into memory. This is far too much. This will cause SIGABRT. Eventually, even if the size of the string were not large (or passed by reference) you would run into a stack overflow because of the depth of the recursion being too great.

7 years later

I used string and it works -
Please refer below link for the same