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 is better than and that is better than .
Given an integer, , can you find the divisor of that Kristin will consider to be the best?
Answers
Explanation:
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 1313 is better than3131 and that1212 is better than 1111.
Given an integer, nn, can you find the divisor of nn that Kristin will consider to be the best?
Input Format
A single integer denoting nn.
Constraints
0<n\leq 10^50<n≤10
5
Output Format
Print an integer denoting the best divisor of nn.
Sample Input
12
Sample Output
6
Explanation
The set of divisors of 1212 can be expressed as \{1,2,3,4,6,12\}{1,2,3,4,6,12}. The divisor whose digits sum to the largest number is 66 (which, having only one digit, sums to itself). Thus, we print 66 as our answer.
Solution
The first step is to create a function d(n)d(n) to calculate the digit sum of a number nn:
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 11 to nn and check if one of the numbers ii divides nn without any remainder. It is obvious that we can halve the search space if we initially exclude 11 and nn. We can easily do much better when seeing any number mm as the product of two other numbers pp and qq, from which is clear that the maximum search space is limited by the square root. For any number ii that divides nn we from now on get two divisors, p:= ip:=i and q:= n/iq:=n/i.
All that is left is a check wether our newly found numbers pp or qq 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;
}