Hackerrank Solution: Best Divisor

Original Problem

Kristen loves playing with and comparing numbers. She thinks that if she takes two different positive numbers, the one whose digits sum to a larger number is better than the other. If the sum of digits is equal for both numbers, then she thinks the smaller number is better. For example, Kristen thinks that \(13\) is better than\(31\) and that\(12\) is better than \(11\).

Given an integer, \(n\), can you find the divisor of \(n\) that Kristin will consider to be the best?

Input Format

A single integer denoting \(n\).

Constraints

\(0<n\leq 10^5\)

Output Format

Print an integer denoting the best divisor of \(n\).

Sample Input

12

Sample Output

6

Explanation

The set of divisors of \(12\) can be expressed as \(\{1,2,3,4,6,12\}\). The divisor whose digits sum to the largest number is \(6\) (which, having only one digit, sums to itself). Thus, we print \(6\) as our answer.

Solution

The first step is to create a function \(d(n)\) to calculate the digit sum of a number \(n\):

unsigned digitSum(unsigned n) {
  unsigned s = 0;
  while (n > 0) {
    s+= n % 10;
    n = n / 10;
  }
  return s;
}

Now we need a way to list all divisors of a number. The most trivial way to do this is looping from \(1\) to \(n\) and check if one of the numbers \(i\) divides \(n\) without any remainder. It is obvious that we can halve the search space if we initially exclude \(1\) and \(n\). We can easily do much better when seeing any number \(m\) as the product of two other numbers \(p\) and \(q\), from which is clear that the maximum search space is limited by the square root. For any number \(i\) that divides \(n\) we from now on get two divisors, \(p:= i\) and \(q:= n/i\).

All that is left is a check wether our newly found numbers \(p\) or \(q\) have a digit sum greater than a previously best digit sum or when the new best digit sum equals the previously best, we compare the numbers itself - according to the problem statement:

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

int main() {
  unsigned n, best, bestSum, lim;
  scanf("%u", &n);
  best = n;
  bestSum = digitSum(n);
  lim = (unsigned) sqrt(n);

  for (unsigned i = 1; i <= lim; i++) {
    if (n % i == 0) {
      unsigned sum = digitSum(i);
      if (sum > bestSum || sum == bestSum && i < best) {
        bestSum = sum;
        best = i;
      }
      sum = digitSum(n/i);
      if (sum > bestSum || sum == bestSum && n/i < best) {
        bestSum = sum;
        best = n/i;
      }
    }
  }
  printf("%u\n", best);
  return 0;
}

Decide on best Divisor

Intuitively it makes sense to formulate \(d(x) > d(y) \lor d(x) = d(y) \land x < y\) as the condition for the best divisor, but here is a small proof:

From which follows that \(x\text{ is better than }y\Leftrightarrow x>>y\Leftrightarrow d(x) > d(y) \lor d(x) = d(y) \land x < y\), with X being a don't care. Another way to proof it is using the ternary operator \(a ? b : c\), which is equivalent to \( (a \Rightarrow b) \land (a \lor c) \):

\[\begin{array}{rl} x >> y &\Leftrightarrow d(x) = d(y) ? x < y : d(x) > d(y) \\ &\Leftrightarrow (d(x) = d(y) \Rightarrow x < y) \land (d(x) = d(y) \lor d(x) > d(y))\\ &\Leftrightarrow d(x) \neq d(y) \land d(x) = d(y) \lor d(x) \neq d(y) \land d(x) > d(y) \lor x < y\land d(x) = d(y) \lor x < y \land d(x) > d(y)\\ &\Leftrightarrow d(x) > d(y) \lor x < y\land d(x) = d(y) \end{array}\]