N-Divisible Digits small program

Question

Heres the idea Write a program that takes two integers, N and M, and find the largest integer composed of N-digits that is evenly divisible by M. N will always be 1 or greater, with M being 2 or greater. Note that some combinations of N and M will not have a solution. Example: if you are given an N of 3 and M of 2, the largest integer with 3-digits is 999, but the largest 3-digit number that is evenly divisible by 2 is 998, since 998 Modulo 2 is 0. Another example is where N is 2 and M is 101. Since the largest 2-digit integer is 99, and no integers between 1 and 99 are divisible by 101, there is no solution.

I would just like some tips on what to improve

#include <iostream>
#include <stdexcept>
#include <cmath>
using std::cin; using std::cout; using std::endl; using std::runtime_error; 
using std::pow;
unsigned largestNumber(unsigned num1) {
return pow(10, num1) - 1;
}
void validNums(const int num1, const int num2) {
 if (num1 < 1 || num1 > 9 || num2 < 2 || num2 > 999999999)
 throw std::runtime_error("invalid input");
}
int divisbleBy(int num1, int num2) {
 for (; num1 != 0; --num1) {
 if (num1 % num2 == 0)
 return num1;
 }
 return 0;
}
int main()
{
 int num1 = 0, num2 = 0;
 int answer = 0;
 cout << "Enter 2 nums and we'll find biggest number possible with num1 digits and we'll then find closest number that num2 can divide by. Num1 has to be between 1-9 and num2 between 2-999-999-999" << endl;
 cin >> num1 >> num2;
 validNums(num1, num2);
 if (answer = divisbleBy(largestNumber(num1), num2))
 cout << "Largest number possible with " << num1 << " is " << largestNumber(num1) << " and the closest number to " << largestNumber(num1) << " divisible by " << num2 << " is " << answer << endl;
 else
 cout << "Invalid" << endl;
 return 0;
}

Answer 1

You should try to find the O(1) algorithm for this problem, instead of using your current O(M) algorithm.

For example, given the input 9 500000001, your program takes 2.3 seconds (on my laptop) to run through the half-billion integers between 999999999 and 500000001. Whereas, using the relatively obvious O(1) algorithm, it takes 0.007 seconds.

Since this looks like homework and/or a Project Euler–type problem, I won't give the spoiler here.

---

Stylistically,

• Prefer to write out std::cin, std::cout, etc., instead of wasting space at the top of the program with a bunch of using directives. It's shorter, cleaner, and (most importantly) more idiomatic to qualify names at the point of use instead of relying on using directives to pull them into scope.

• Your function validNums uses exceptions for control flow, which is frowned upon in C++. Prefer to make it a function returning bool, and have its caller do something sensible (such as print an error message) if the given numbers aren't valid.

• You have a named abstraction for largestNumber, when that could just as well have been a named local variable int largestNumber = pow(...);.

• You don't have a named abstraction for produceTheActualAnswer; instead, you inline a complicated test if (answer = divisbleBy(largestNumber(num1), num2)) straight into main. This makes it unnecessarily difficult to switch out your bad old algorithm for a new and better one.

• Putting an assignment inside an if condition is supremely bad style — so bad that both GCC and Clang (and probably MSVC too) will emit a warning on this code. You should write either

  int answer = produceTheActualAnswer(num1, num2);
  if (answer != 0) {
   ...
  } else {
   ...
  }
  

  or, if you really want to use "interesting" features of C++, you might write

  if (int answer = produceTheActualAnswer(num1, num2)) {
   ...
  } else {
   ...
  }
  

  But I don't recommend the latter.

---

You should also consider taking your num1 and num2 parameters via the command line, instead of reading them from stdin:

int main(int argc, char **argv) {
 if (argc < 3) {
 // maybe read them from stdin anyway
 } else {
 int m = std::atoi(argv[1]);
 int n = std::atoi(argv[2]);
 int answer = f(m, n);
 if (answer != 0) { ... } else { ... }
 }
}

This makes it easier to test your code quickly from the command line, and also makes it easy to time ./a.out 9 500000001 to see if you've beaten my 0.007 seconds yet. ;)

• Magirldooger: Hey thanks for the answers :) Why is declaration in if bad? I fixed up my code just not that 0(1) thing can you explain it? Btw this isn't homwork I just found it off /r/dailyprogrammer :) Heres my code pastebin.com/yfBg1yPW
• Quuxplusone: You didn't change very much in that pastebin — all the logic is still stacked up in main instead of being factored out into a function (produceTheActualAnswer was my slightly humorous suggestion for that function's name). I don't recommend if (int answer = ...) because it's an arcane feature of the language, so it would confuse people. Plus, once you slip into that habit, it's just a matter of time before you write if (auto it = map.find(key)) { ... *it ... } and ta-da, you've written a bug. Better to just not tempt fate at all.
• Magirldooger: Here I put the logic in a function and if it returns non zero its good if its 0 its bad pastebin.com/6zaCT3D0 also can you tell me what that 0(1) this was I have algorithms in the next chapter so it should cover it :)
• Magirldooger: Or should I make it so it just returns the answer and doesn't change num1 so I could call it multiple times but then I couldn't get the largest num.
• Quuxplusone: Well, here's a hint: Given some integer x, how would you (in a single arithmetic expression) find the largest number less than or equal to x that is divisible by 2? divisible by 4? divisible by 10? divisible by m? And then, having done that, how would you check whether that number had exactly n digits or fewer than n digits?

Answer 2

User interface improvement

Tell the requirements as near to their need as possible, your interface is:

Enter 2 nums and we'll find biggest number possible with num1 digits and we'll then 
find closest number that num2 can divide by.
Num1 has to be between 1-9 and num2 between 2-999-999-999

The user then has to enter the two numbers with no prompt at all.

I would prefer this interface:

Enter 2 nums and we'll find biggest number possible with num1 
digits and we'll then find closest number that num2 can divide by.
The first number? [From 1 to 9] 5
The second number? [From 2 to 999_999_999] 412

This way the probability of error drops as the user gets the constraints one by one just before entering the numbers.

Even better would be to avoid vague names like num1 and num2 or first number and second number and give the user a more precise prompt:

Given a number of digits `d` and a number `n`
This program will find the biggest number with `d` digits divisible by `n` 
How many digits? [From 1 to 9] 8
Divisible by? [From 2 to 999_999_999] 213414

This final version is way more clear and user friendly than the first prompt, that was pretty vague.

And while I am at it, I would also clean up the output to avoid the 9999... triviality and give just the information asked for in a more precise format:

The biggest number with 7 digits divisible by 999 is: 9999990