I'm doing a Codewars Challenge. I must square every digit of a number and concatenate them. So, if we run 9119 through the function, 811181 will come out, because 9² is 81 and 1² is 1.

My code is below:

#include <math.h>

unsigned long long square_digits (unsigned n)
{
  // Count for digits
  int digits = log10(n)   1, i = 0;
  
  // Array to store the split number
  int numDivided[digits];
  
  // Store concatenated numbers
  unsigned long long result = 0;
  
  if (n == 0)
  {
    return result;
  }
  
  // Split number and store their square
  while (n > 0) 
  {
    numDivided[i] = pow(n % 10, 2);
    n /= 10;
    i  ;
  }
  
  // Concatenated square of numbers
  for (i = digits - 1;i >= 0;i--)
  {
    if (numDivided[i] == 0)
    {
      result *= 10; 
    }
    else
    {
      // Count digits of the current number
      digits = log10(numDivided[i])   1;
    
      // Multiply current result for 10^(digits)
      result *= pow(10, digits);
      
      // Add the current number to result
      result  = numDivided[i];
    }
  }
  
    return result;
}

The test cases are below:

Test(test_suite, sample_tests)
{
    do_test(      3212u,                9414ull);
    do_test(      2112u,                4114ull);
    do_test(         0u,                   0ull);
    do_test(       999u,              818181ull);
    do_test(     10001u,               10001ull);
    do_test(3210987654u,    9410816449362516ull);
    do_test(3999999999u, 9818181818181818181ull); // :p
    do_test(   UINT_MAX,  164811681364948125ull);
}

The code works until the two last tests, so:

for n = 3999999999, expected 9818181818181818181, but got 9818181818181818449

I was think that the test case was wrong and check if the number was greater that ULLONG_MAX but it's less, so, all right.

What is my mistake at this point?

CodePudding user response：

What problems could i have with pow function? There is any alternative?

pow() typically returns, at best, a 53 significant bit result yet we have at least a 64-bit problem. powl() does not certianly help either as it may be as limiting as pow(). Do not use floating point functions for an integer problem. Using a floating point funtion for an integer problem is the wrong approach.

digits = log10(n) 1 are numDivided[i] = pow(n % 10, 2) are not specified to get the desired value (due to imprecision) and certainly fail when n == 0.

Simple extract the least significant decimal digit with . Scale by an integer type power-of-10.

unsigned long long square_digits(unsigned n) {
  unsigned long long nn = 0;
  unsigned long long pow10 = 1;

  while (n) {
    unsigned digit = n % 10;
    unsigned square = digit * digit;  // 0 to 81
    nn  = square * pow10;
    if (square < 10) {
      pow10 *= 10;
    } else {
      pow10 *= 100;
    }
    n /= 10;
  }
  return nn;
}

CodePudding user response：

The main culprit is this line:

result *= pow(10, digits);

Given that result is an unsigned long long while the return value of pow is a double, result is first converted to a double, then multiplied by the power and finally the result is converted back to an unsigned long long.

The problem is that while a double type has a much greater range than an unsigned long long, its precision is limited and not all the possible integral values can be represented (stored) exactly.

In particular, you can check the result of the following line:

printf("%.0lf\n", 981818181818181ull * 100.0);  // It won't print 98181818181818100

See @chux's answer for further details and a proper implementation of the solution.

CodePudding user response：

I found two mistakes in your code.

• log() is not defined for 0. So, you cannot run your code against Test case 3.
• Use powl() instead of pow().

PS: One change you can do to pass test case 3 is check if N == 0 in the beginning of the function itself. The next script should calculate the number of digits in N.