Palindromic number in C

Question

So lets say we have this program in C that checks if a number is palindromic or not, WITHOUT the use of any array at all(so dont respond with any answer that uses an array)

#include <stdio.h>
#include <math.h>

int NumOfDigits(long long x) {
    int sum = 1;
    while (x / 10 != 0) {
        sum ++;
        x = x / 10;
    }
    return sum;
}

int isPal(long long x) {
    int f, c, front, back, sum;
    sum = NumOfDigits(x);
    
    c = round(pow(10,(sum-2)));
    front = x / round(pow(10,(sum - 1)));
    back = x % 10;
    f = 1; 

    while (x != 0 && f == 1 && c != 0) {
        if (front == back) {
           x = (x / 10) % c;
           c /= 100;
           sum -=2;
           front = x / round(pow(10,(sum-1)));
           back = x % 10;
        } else {
           f = 0;
        }
    }
    if (f) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    int f;
    long long x;
    scanf("%lld", &x);
    f = isPal(x);
    if (f) {
        printf("yes");
    } else {
        printf("no");
    }
    printf("\n");
}

So basically this algorithm checks the first and the last digit each time and then reduces the NumOfDigits by 2, so if we have 345543, first it's 345543 then 4554, 55 etc. The point with this program is that, for example given the number 900075181570009 it says its NOT palindromic, but it is because the computer erases the 0s form the left side of the number. So when it goes to 0007518157000 its basically 7518157000 which is not a palindromic number. So, how can we modify the algorithm, again without the use of an array, to achieve the expected result?

Answer 1

In testing out the code I did notice that the result of 900075181570009 being designated as not a palindrome was an issue with the variable being an integer, and thus being too small in some cases to contain the proper power of 10. When I designated that as a "long long" variable, the number 900075181570009 was designated as a palindrome.

In regard to testing numbers that had leading zeros (and trailing zeros) what appeared to be a necessary function to repeatedly divide the number by 10 until all trailing zeros were expunged, and then perform the palindrome test. With that following is the refactored code. First off is the additional function to remove trailing zeros from a candidate number.

#include <stdio.h>
#include <math.h>

long long lagging(long long z)
{
    long long work = z;

    while (1)
    {
        if ((work % 10) != 0)
            break;

        work /= 10;
    }

    return work;
}

Next, is the refactored palindrome test function where the variable "c" has been enlarged, along with the initial scrubbing of a test value.

    int isPal(long long x) {
    int f,front, back, sum;
    long long c;

    x = lagging(x);  /* One off call to additional scrubbing if needed */

    sum = NumOfDigits(x);

In testing out various numbers noted in your example, following was the test output at the terminal.

craig@Vera:~/C_Programs/Console/PalInteger/bin/Release$ ./PalInteger 
Enter a number: 900075181570009
yes
craig@Vera:~/C_Programs/Console/PalInteger/bin/Release$ ./PalInteger 
Enter a number: 0007518157000
yes
craig@Vera:~/C_Programs/Console/PalInteger/bin/Release$ ./PalInteger 
Enter a number: 345543
yes
craig@Vera:~/C_Programs/Console/PalInteger/bin/Release$ ./PalInteger 
Enter a number: 7518157000
yes

One for train of thought for your evaluation.

Answer 2

In your code the c value is wrongly declared as an int.

#include <stdio.h>
#include <math.h>
int main()
{
    int c ;
    c = round(pow(10,13));
    printf("%ld",c);

    return 0;
}

When we run the above program, we get an overflow warning:

main.c: In function ‘main’:
main.c:14:9: warning: overflow in conversion from ‘double’ to ‘int’ changes value from ‘1.0e+13’ to ‘2147483647’ [-Woverflow]
   14 |     c = round(pow(10,13));
      |         ^~~~~
2147483647

So, just by changing int c to unsigned long int c resolves the issue and it works perfectly fine.

Answer 3

To begin, the solution does not need <math.h> when dealing with integer values.

NumOfDigits() is off on false start. The implication is that the values being compared will be treated as if they are arrays (that have individual elements).

Below is a solution. isPal() prints the base10 representation of two values being checked as verification the function is working with integers, not arrays.

Arrays are used in the collection of test pairs in main() (external to isPal()) only to demonstrate how values with leading/trailing zeros might be expressed in test cases. (Note: strings of digits converted with atoi() circumvent the C compiler's interpretation of leading zero heralds an octal or hexadecimal value in source code.)

#include <stdio.h>

char *isPal( uint32_t a, uint32_t b) {
    uint32_t rev = 0;

    printf( "isPal( %u, %u ) - ", a, b );
    for( ; b; b /= 10 )
        rev = rev * 10 + b % 10;

    for( ; rev <= a; rev *= 10 )
        if( rev == a )
            return "yes";

    return "no";
}

int main( void ) {
    char *vals[][2] = {
        {   "123", "321"   },
        {   "121", "321"   },
        {  "00070", "07000"  },
        { "50060", "06005" },
        { 0 } // terminate
    };

    for( size_t i = 0; vals[i][0]; i++ )
        printf( "%s & %s - %s\n", vals[i][0], vals[i][1],
            isPal( atoi( vals[i][0]), atoi( vals[i][1] ) ) );

    return 0;
}

Result:

isPal( 123, 321 ) - 123 & 321 - yes
isPal( 121, 321 ) - 121 & 321 - no
isPal( 70, 7000 ) - 00070 & 07000 - yes
isPal( 50060, 6005 ) - 50060 & 06005 - yes

It's not healthy to believe others when when they say something is impossible...

Caveat: In the simpler realm of unsigned char, the value 128 can be represented (in one byte), its reversal 821 cannot... Detecting and avoiding numeric overflow is left as an exercise for the OP.
(Hint: if( value >= UtypeMAX / 10 ) /* do not attempt to multiply by 10 */)

---

EDIT:
Having shown proof of concept, here is a less stilted version that deals with one number and its own palidrome:

#include <stdio.h>

char *isPal( uint32_t a ) {
    uint32_t b = a, rev = 0;

    printf( "isPal( %u ) - ", a );
    for( ; b; b /= 10 )
        rev = rev * 10 + b % 10;

    for( ; rev <= a; rev *= 10 )
        if( rev == a )
            return "yes";

    return "no";
}

int main( void ) {
    char *vals[] = {
        "12321",
        "12345",
        "00000700",
        "031300",
        "50050",
        0 // terminate
    };

    for( size_t i = 0; vals[i]; i++ )
        printf( "%s - %s\n", vals[i], isPal( atoi( vals[i] ) ) );

    return 0;
}

Result:

isPal( 12321 ) - 12321 - yes
isPal( 12345 ) - 12345 - no
isPal( 700 ) - 00000700 - yes
isPal( 31300 ) - 031300 - yes
isPal( 50050 ) - 50050 - yes

Answer 4

OP's first problem is not due to leading zeros, but due to c = round(pow(10,(sum-2))); failing as c is an int and not long long.

If code wants to handle leading zeros, consider using "%n" to record the offset of the scan.

int n1, n2;
if (scanf(" %n%lld%n", &n1, &x, &n2) != 1) {
  Handle_BadInput();  // TBD code
}
int digit_count = n2 - n1;

This still get fooled with input like "-123" or with values outside the long long range.

---

Consider using unsigned long long to handle all 19 digit and some 20 digit values.

---

[Edit 2023/11/18]

One of the problem of trying to fully reverse a number is that the reversed number may be out of the number range. This readily occurs with large values whose least significant digit is more than the most significant digit.

A solution is to only reverse the most significant half of the digits while forming the reversed least significant half. Then compare values. That way, overflow does not occur. It also does fewer computations.

Sample code and test harness. Test code uses arrays to form the reversed value, yet that is for testing. isPal_without_array() is array free (once the debug printf() is removed.)

#include <stdio.h>

int isPal_without_array(unsigned long long x) {
  unsigned long long forward = x;
  unsigned long long reverse = 0;
  unsigned long long tens = 10;

  while (forward >= tens) {
    printf("f:%20llu r:%20llu\n", forward, reverse);
    unsigned digit = forward % 10;
    forward /= 10;
    reverse = reverse * 10 + digit;
    tens *= 10;
  }
  printf("f:%20llu r:%20llu\n", forward, reverse);

  if (forward >= tens / 10) {
    forward /= 10;
  }

  return forward == reverse;
}

#include <assert.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

/*
 * Test palindrome 2 ways:
 * Return 0 on match, 1 on mis-match.
 */
int isPal_test(unsigned long long x) {
  char forward[50];
  char reverse[50];
  int len = sprintf(forward, "%llu", x);
  for (int i = 0; i < len; i++) {
    reverse[i] = forward[len - 1 - i];
  }
  reverse[len] = '\0';
  int cmp0 = (strcmp(forward, reverse) == 0);
  int cmp1 = isPal_without_array(x);
  if (cmp0 != cmp1) {
    printf("%20llu %20s %d %d FAIL\n", x, reverse, cmp0, cmp1);
    return 1;
  }
  printf("%20llu %20s %d %d\n\n", x, reverse, cmp0, cmp1);
  return 0;
}

#include <limits.h>

int main() {
  isPal_test(18446744073709551615u); // ULLONG_MAX
  isPal_test(18446740733704764481u);
  return 0;
  isPal_test(67899876);
  isPal_test(3443);
  isPal_test(121);
  for (unsigned i = 0; i <= 1000; i++) {
    isPal_test(i);
  }
  for (unsigned long long i =0; i < 10000000; i++) {
    isPal_test(ULLONG_MAX - i);
  }
  puts("Done");
}

Output with a near `

f:18446744073709551615 r:                   0
f: 1844674407370955161 r:                   5
f:  184467440737095516 r:                  51
f:   18446744073709551 r:                 516
f:    1844674407370955 r:                5161
f:     184467440737095 r:               51615
f:      18446744073709 r:              516155
f:       1844674407370 r:             5161559
f:        184467440737 r:            51615590
f:         18446744073 r:           516155907
f:          1844674407 r:          5161559073
18446744073709551615 51615590737044764481 0 0

f:18446740733704764481 r:                   0
f: 1844674073370476448 r:                   1
f:  184467407337047644 r:                  18
f:   18446740733704764 r:                 184
f:    1844674073370476 r:                1844
f:     184467407337047 r:               18446
f:      18446740733704 r:              184467
f:       1844674073370 r:             1844674
f:        184467407337 r:            18446740
f:         18446740733 r:           184467407
f:          1844674073 r:          1844674073
18446740733704764481 18446740733704764481 1 1

Answer 5

The function isPal is wrong at least because in this statement due to the integer division

x = (x / 10) % c;

leading zeroes can be lost.

You should not change x suzh a way. Also it is unsafe and redundant to use the function pow that returns a double value.

Also using a string as it is suggested breaks the rule that does not allow ro use arrays because strings are actually contained in character arrays.

I can suggest the following solution.

#include <stdio.h>

unsigned long long max_divisor( unsigned long long x )
{
    const unsigned long long int Base = 10;

    unsigned long long divisor = 1;

    while (!( x / divisor < Base ))
    {
        divisor *= Base;
    }

    return divisor;
}

int is_palindrome( unsigned long long x )
{
    const unsigned long long Base = 10;
    unsigned long long int left_divisor = max_divisor( x );
    unsigned long long int right_divisor = 1;

    int palindrome = 1;

    while (palindrome && right_divisor < left_divisor)
    {
        unsigned long long int left_digit = x / left_divisor % Base;
        unsigned long long int right_digit = x % ( Base * right_divisor ) / right_divisor;

        if (( palindrome = left_digit == right_digit ))
        {
            left_divisor  /= Base;
            right_divisor *= Base;
        }
    }

    return palindrome;
}

int main( void )
{
    printf( "is_palindrome( 1 ) is %s\n", is_palindrome( 1 ) ? "true" : "false" );
    printf( "is_palindrome( 11 ) is %s\n", is_palindrome( 11 ) ? "true" : "false" );
    printf( "is_palindrome( 12 ) is %s\n", is_palindrome( 12 ) ? "true" : "false" );
    printf( "is_palindrome( 121 ) is %s\n", is_palindrome( 121 ) ? "true" : "false" );
    printf( "is_palindrome( 1221 ) is %s\n", is_palindrome( 1221 ) ? "true" : "false" );
    printf( "is_palindrome( 12321 ) is %s\n", is_palindrome( 12321 ) ? "true" : "false" );
    printf( "is_palindrome( 900075181570009 ) is %s\n", is_palindrome( 900075181570009 ) ? "true" : "false" );
}

The program output is

is_palindrome( 1 ) is true
is_palindrome( 11 ) is true
is_palindrome( 12 ) is false
is_palindrome( 121 ) is true
is_palindrome( 1221 ) is true
is_palindrome( 12321 ) is true
is_palindrome( 900075181570009 ) is true

Answer 6

You can just reverse the digits and then compare it with the original value. Works for 0 <= xinit < 10^19.

int isPal(uint64_t xinit) {
  uint64_t x = xinit;
  uint64_t xrev = 0;
  while(x) {
    xrev = 10*xrev + (x % 10);
    x /= 10;
  }
  return (xrev == xinit);
}