# 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:

$$d(x) = d(y)$$$$x < y$$$$d(x) > d(y)$$Result
0000
0011
0100
0111
1000
101X
1101
111X

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}$

« Back to problem overview