Kaprekar Number between given range

Question

I'm trying to print all Kaprekar Numbers between Given Range

As input the range is between --> 1 to 99999 <--

The Expected Output :

1 9 45 55 99 297 703 999 2223 2728 4950 5050 7272 7777 9999 17344 22222 77778 82656 95121 99999

but I got this output :

1 9 45 55 99 297 703 999 2223 2728 4950 5050 7272 7777 9999 17344 22222

I stay miss 3 output any idea I'm using C++.

My code :

#include <bits/stdc++.h>
#include <cmath>

using std::cout;
using std::cin;
using std::endl;
using std::pow;

int b = 0, a = 0;

int main(int argc, char** argv) {
    
    int lower, upper, count = 0;
    cin >> lower >> upper;
    
    for (int i = lower; i <= upper; i++) {
        
        int n = i, digits = 0;
        while (n != 0) {
            digits++;
            n /= 10;
        }
        n = pow(i, 2);
        digits = pow(10, digits);
        b = n % digits;
        a = (n - b) / digits;
        if (a + b == i) {
            cout << i << " ";
            count++;
        }
        digits = 0;
        a = 0;
        b = 0;
    }
    
    if (count == 0) cout << "INVALID RANGE";
    return 0; 
}

[Why should I not #include ](https://stackoverflow.com/questions/31816095/) — DevSolar, Oct 01 '22 at 19:02
`pow(i, 2)` doesn't fit into an `int` for `i == 77778` (in fact, for any value greater than `46340`). Your program exhibits undefined behavior by way of integer overflow. — Igor Tandetnik, Oct 01 '22 at 22:24

score 0 · Accepted Answer · answered Oct 02 '22 at 00:53

All the variables used in the posted snippet are of type int, which is probably¹ not enough big to store the squares of all the possible input values, so that, as note by Igor Tandetnik in their comment

Your program exhibits undefined behavior by way of integer overflow.

Using a wider type, like long long² or int64_t should fix the program.

I'd also avoid the use of std::pow, which returns a double, when exact integer arithmetic is needed³.

The followig snippet implements a slightly different algorithm⁴.

#include <iostream>

int main()
{
  long long int lower{ 1 };
  long long int upper{ 99'999 };

  int base{ 10 };
  
  for (auto i = lower; i <= upper; ++i)
  {
    auto n{ i * i };
    // https://en.wikipedia.org/wiki/Kaprekar_number
    /* "a natural number in a given number base is a p-Kaprekar number if the
        representation of its square in that base can be split into two parts,
        where the second part has p digits, that add up to the original number."
    */
    auto b{ n % base };        // So, let's calculate those two parts directly.
    auto a{ n / base };
    auto power{ 1ll };
    
    while ( a >= i ) { 
      power *= base;
      b += (a % base) * power;    // Add one digit to b.
      a /= base;                  // Remove one digit from a.
    }

    if (a + b == i) {
      std::cout << i << ' '; 
    }
  }
  std::cout << '\n';
}

^{1) See e.g. What does the C++ standard state the size of int, long type to be?}

^{2) note that a long may be as wide as an int in certain environments.}

^{3) See e.g. Why pow(10,5) = 9,999 in C++ and Is there any advantage to using pow(x,2) instead of x*x, with x double?}

^{4) https://godbolt.org/z/1G9of49xb}

Kaprekar Number between given range

1 Answers1