https://www.hackerrank.com/challenges/best-divisor

Tìm số trong danh sách các ước số của N sao cho tổng các chữ số của số đó là lớn nhất, nếu có 2 ước số thỏa điều kiện thì lấy ước nhỏ nhất.

vd : 12 {1,2,3,4,6,12} => 6 vd: 26 {1,13,31,403} => 13 (13=31 mà 13<31)

Giải:

Ta có A*B=N => A = N/B; vậy xét số 12 ta có thể có 1x12, 2x6, 3x4, 4x3, 6x2, 12x1 ; nhận thấy các cặp bị lặp lại theo phép giao hoán. Để tìm được số phân chia 2 nhóm này ra nó chính bằng số ở giữa (A*A = N => A=sqrt(N) )

Ta chỉ cần lặp i từ 2 tới khi nào i*i <= N
Tìm ra tổng chữ số lớn nhất của của i và N/i và so sánh với biến hiện tại.

int sumDigits (int n){
    int ret = 0 ;
    while(n>0){
        ret+=n%10;
        n/=10;
    }
    return ret;
}
int best(int a, int b){
    if (a==b) return a;
    int sumA = sumDigits(a), sumB = sumDigits(b);
    if(sumA>sumB) return a;
    else if(sumA < sumB) return b;
    return a<b ? a : b;
}
///...
int cur = best(1, n);    
    for(int i=2;i*i<=n;++i){
        if (n%i==0){
            int c=best(i,n/i);
            cur = best(cur,c);
        }
    }

thafnhlong / hackerrank-storage

https://www.hackerrank.com/challenges/best-divisor #32