-1
#include<iostream>
#include <vector>
#include <iomanip>
using namespace std;

int print(int n, int t) {

    for (unsigned long long i = pow(10, n - 1); i < pow(10, n); i++) {
        if (i % t == 0)
            return i;
    }
    
    return -1;
}

int main() {

    int n, t;

    cin >> n >> t;

    cout << print(n ,t);
}

Hi, I have a method where it finds a whole number that is n digits long and divisible by t. It works correctly for almost all cases, except when n is large. One problematic example is when n = 18 and t = 8.

I printed out pow(10, n - 1) with set precision(18) and the number is 10^17. However, the answer I get back is 1569325056, which is only 10 digits.

I don't understand how I get a number less than 10^18, which should be the smallest number. Shouldn't an unsigned long long int be enough to hold the 10^18?

silverfox
  • 1,568
  • 10
  • 27
Benjamin Chen
  • 69
  • 4
  • 3
    But you're returning an `int`? – silverfox Nov 22 '21 at 05:42
  • You should not be using `pow`, a floating point function, for integer-based problems. Usage of such function makes the code broken. Either have a table of integer-based powers of 10, or write an integer-based function that does the powers. Also, you are repeatedly calling `pow` in the `for` part of the loop, which is inefficient. – PaulMcKenzie Nov 22 '21 at 06:06
  • using `pow` to get powers of integers is a bad idea: [Why does pow(5,2) become 24?](https://stackoverflow.com/q/22264236/995714), [Why the result of pow(10,2) 99 instead of 100?](https://stackoverflow.com/q/54057687/995714), [Why pow(10,5) = 9,999](https://stackoverflow.com/q/9704195/995714) – phuclv Nov 22 '21 at 06:15
  • https://stackoverflow.com/questions/1505675/power-of-an-integer-in-c – Swift - Friday Pie Nov 22 '21 at 06:19
  • You can also add [this link](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os) showing the vulnerability of using `pow`. – PaulMcKenzie Nov 22 '21 at 06:31
  • 1
    *"Shouldn't an `unsigned long long int` be enough to hold the `10^18`?"* -- this question is irrelevant since you are not printing an `unsigned long long int`. – JaMiT Nov 22 '21 at 06:37
  • (1) `pow()` is for `double`s, i.e. irrelevant for this case; don’t use it. (2) Don’t use an `int`. Its range is only –2³¹ to 2³¹ – 1. (3) `uint64_t` won’t solve the problem fully either; it only goes from `0` to 2⁶⁴ – 1. If you want *unlimited* integers, use [GNU MP](https://gmplib.org/manual/C_002b_002b-Class-Interface). (4) Your algorithm is as hugely inefficient as it gets. If you just want *any* n-digit number divisible by `t`, why not take the maximum n-digit number (n 9s), divide it by `t` and multiply it by `t`? If it’s still n-digit, you have your result. No reason to iterate. – Andrej Podzimek Nov 22 '21 at 06:51
  • I’ve added [an answer](https://stackoverflow.com/a/70061957/8584929) showing both GNU MP and a reasonable algorithm for the number search. If the goal was to find the *smallest* n-digit number divisible by `t` (rather than *any* or the *biggest*), the algorithm can be trivially modified: Do the (integer) division and multiplication for n – 1 digits, then add the divisor once, check if you got exactly n digits → there you go. – Andrej Podzimek Nov 22 '21 at 07:16

3 Answers3

1

You return i which is unsigned long long, but your return type is int.

unsigned long long print(int n, int t) {

    for (unsigned long long i = pow(10, n - 1); i < pow(10, n); i++) {
        if (i % t == 0)
            return i;
    }
    return -1ULL;
}

But it is extremely inefficient this way, when t gets large and/or is a big prime, as the loop may have to loop about t times. Using the remainder, you can calculated much faster (be warned, this is a piece of untested C++ code, just to get the general idea out):

unsigned long long solve(int n, int t)
{
    //assuming n <= 18 and t is within `int` range
    unsigned long long smallest = pow(10, n-1), largest = pow(10, n);
    if (smallest % t == 0) {return smallest;}

    unsigned long long leftOver = smallest - smallest % t; leftOver += t;
    if (leftOver <= largest) {return leftOver;} else {return -1ULL;}
}
silverfox
  • 1,568
  • 10
  • 27
0

Use GNU MP for unlimited integers. In the example below, you can use an arbitrary number of digits. Obtaining and checking of user inputs is (intentionally) left out for the sake of brevity.

#include <gmpxx.h>
#include <iostream>
#include <string>

int main() {
  const size_t n_digits{22};
  const mpz_class divisor{77777777777777777777_mpz};

  const mpz_class digits{mpz_class{std::string(n_digits, '9')}
                         / divisor
                         * divisor};
  const std::string output{digits.get_str()};

  if (output.size() == n_digits) {
    std::cout << "An example " << n_digits
              << "-digit number divisible by " << divisor
              << " is " << output;
  } else {
    std::cout << "There is no " << n_digits
              << "-digit number divisible by " << divisor;
  }
  std::cout << ".\n";
}

Link with -lgmp -lgmpxx.

An example 22-digit number divisible by 77777777777777777777 is 9955555555555555555456.
Andrej Podzimek
  • 2,409
  • 9
  • 12
-1

Your print function returns an int, so when you return i;, i get casted back into an int.

Change your code to:

unsigned long long print(int n, int t) {

    for (unsigned long long i = pow(10, n - 1); i < pow(10, n); i++) {
        if (i % t == 0)
            return i;
    }
    
    return -1ULL;
}
justANewb stands with Ukraine
  • 4,535
  • 3
  • 14
  • 39