Create a function that takes a number n as an argument and returns the largest integer that is less than or equal to n and has the highest digit sum.

Examples:

largestDigitSum(100) ➞ 99
// Digit Sum for 99 = 9   9 = 18
// All numbers from 0 to 98 and 100 itself have digit sum lesser than 18.

largestDigitSum(48) ➞ 48
// Digit sum for 48 = 4   8 =12
// Digit sum for 39 = 3   9 =12
// Return 48 because 48 > 39

largestDigitSum(10) ➞ 9

So basically I tried solving this problem but the function would return 0 no matter what I did. Here's my attempt at coding:

int largestDigitSum(int n)
{
    int s1 = 0, s2, c, maxi;
    while (n > 0) {
        c = n % 10;
        s1  = c;
        n /= 10;
    }

    while (n > 0) {
        n--;
        while (n > 0) {
            c = n % 10;
            s2  = c;
            n /= 10;
        }
        if (s1 > s2)
            maxi = n;
        else
            s1 = s2;
    }
    return maxi;
}

Can someone please explain what I did wrong?

Edit:

Ok, thanks to everyone who helped me understand this problem. I tried dividing it into 2 functions and now it works! Here's my new code:

int digitSum(int n)
{int s=0;

while(n>0)
    {s  = n%10;
    n/=10;}

return s;
}

int largestDigitSum(int n)
{int i, maxi=1;

for(i=2;i<=n;i  )
    if(digitSum(i) >= digitSum(maxi))
        maxi=i;
return maxi;
}

CodePudding user response：

int largestDigitSum(int n)
{
    int s1 = 0, s2, c, maxi;
    while (n > 0) {
        c = n % 10;
        s1  = c;
        n /= 10; // This loop will never end until n becomes 0
    }

    while (n > 0) { // n is 0 because of the last loop
        n--; // this will never enter
        while (n > 0) {
            c = n % 10;
            s2  = c;
            n /= 10;
        }
        if (s1 > s2)
            maxi = n; // this will never be called
        else
            s1 = s2;
    }
    return maxi; // maxi is never being initialized to begin with
}

maxi isn't even being initialized, so the fact that you see 0 is merely the result of undefined behavior. That's why this function returns 0 all the time.

CodePudding user response：

1. This task makes only sense if the input number is unsigned. If it is signed you should search until the INT_MIN (as anynumner >= INT_MIN).

use function for repeated tasks.

unsigned sumdigits(unsigned x)
{
    unsigned sum = 0;
    while(x) 
    {
        sum  = x % 10;
        x /= 10;
    }
    return sum;
}

unsigned brutForce(unsigned x)
{
    unsigned cmax = 0, csum, maxnum;
    while(x)
    {
        csum = sumdigits(x);
        if(csum > cmax) {cmax = csum; maxnum = x;}
        x--;
    }
    return maxnum;
}


int main(void)
{
    printf("Max number: %u\n", brutForce(100000));
}

Of course there are much more efficient ways of doing it.

CodePudding user response：

Best to separate the evaluation of the function you are maximizing from the actual process of seeking a maximum:

static unsigned int
sum_of_digits(unsigned int n)
{
    unsigned int sum = 0;

    while (n > 0) {
        sum  = n % 10;
        n /= 10;
    }

    return sum;
}

This way, you can reason about the "sum of digits" function separately from any other logic.

I am interested in both the integer that gives me the desired result (argmax) and the maximized value. Therefore, I declare a struct that can hold both values:

struct max_result {
    unsigned int argmax;
    unsigned int max;
};

Now, I can write a function that seeks the maximized value of a another function in a range:

static struct max_result *
max_value_of_function(
        unsigned int n,
        unsigned int (*fn)(unsigned int)
)
{
    unsigned int i = 1;

    struct max_result *r = malloc(sizeof(*r));
    assert(r);

    r->argmax = 0;
    r->max = 0;

    do {
        unsigned int s = fn(i);
        if (s >= r->max) {
            r->max = s;
            r->argmax = i;
        }

        if (i == n) {
            break;
        }

          i;
    } while (1);

    return r;
}

This means you can focus the logic of seeking the maximum independently of calculating the sum of the digits of a number.

When writing stuff like this, it is always useful to start with some test cases. No need to do anything fancy ... Something that compares expected output for a given input with the actual returned value of the function. I put in the cases listed in your question plus two other interesting cases.

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct max_result {
    unsigned int argmax;
    unsigned int max;
};

struct test_case {
    const unsigned int input;
    const unsigned int expected;
};

static
int sum_of_digits(unsigned int n)
{
    int sum = 0;

    while (n > 0) {
        sum  = n % 10;
        n /= 10;
    }

    return sum;
}

static struct max_result *
max_value_of_function(
        unsigned int n,
        unsigned int (*fn)(unsigned int)
)
{
    unsigned int i = 1;

    struct max_result *r = malloc(sizeof(*r));
    assert(r);

    r->argmax = 0;
    r->max = 0;

    do {
        unsigned int s = fn(i);
        if (s >= r->max) {
            r->max = s;
            r->argmax = i;
        }

        if (i == n) {
            break;
        }

          i;
    } while (1);

    return r;
}

int
main(void) {
    int i;

    struct test_case cases[] = {
        { 0, 0 }, { 100, 99 }, { 48, 48 }, { 10, 9 }, { UINT_MAX, 3999999999U },
    };

    for (i = 0; i < sizeof(cases)/sizeof(cases[0]);   i) {
        struct max_result *r = max_value_of_function(cases[i].input, sum_of_digits);
        if (r->argmax == cases[i].expected) {
            printf(
                    "The positive integer with largest sum of digits in [0, %u] is %u\n"
                    "Sum of its digits is %u\n",
                    cases[i].input,
                    r->argmax,
                    r->max
            );
        }
        else {
            printf("Got %u ... expected %u\n", r->argmax, cases[i].expected);
        }
    }

    return 0;
}