views:

208

answers:

4

What is the algorithm in c# to do this?

Example 1: Given n = 972, function will then append 3 to make 9723, because 9 + 7 + 2 + 3 = 21 (ends with 1). Function should return 3.

Example 2: Given n = 33, function will then append 5 to make 335, because 3 + 3 + 5 = 11 (ends with 1). Function should return 5.

+2  A: 

The algorithm in general:

(10 - (sum of digits mod 10) + 1) mod 10

The answer of the above expression is your needed digit.

sum of digits mod 10 gives you the current remainder, when you subtract this from 10 you get the needed value for a remainder of 0. When you add 1 you get the needed value to get a remainder of 1. The last mod 10 gives you the answer as a 1 digit number.

So in C# something like this:

    static int getNewValue(string s)
    {
        int sum = 0;
        foreach (char c in s)
        {
            sum += Convert.ToInt32(c.ToString());
        }
        int newDigit = (10 - (sum % 10) + 1) % 10;
        return newDigit;
    }
Brian R. Bondy
Actually, if the sum of the digits mod 10 is 0, then your expression gives 11. The correct one is (10 - (sum of digits mod 10) + 1) mod 10. Or, equivalently, (1 - sum of digits) mod 10. [Since as per the usual number-theoretic convention, (-33 mod 10) is 7, etc.] This gives an answer that is always between 0 and 9.
ShreevatsaR
@ShreevatsaR: Yup thanks fixed.
Brian R. Bondy
+3  A: 

Algorithms are language independent. Asking for "an algorithm in C#" doesn't make much sense.

Asking for the algorithm (as though there is only one) is similarly misguided.

So, let's do this step by step.

First, we note that only the last digit of the result is meaningful. So, we'll sum up our existing digits, and then ignore all but the last one. A good way to do this is to take the sum modulo 10.

So, we have the sum of the existing digits, and we want to add another digit to that, so that the sum of the two ends in 1.

For the vast majority of cases, that will mean sum + newDigit = 11. Rearranging gives newDigit = 11 - sum

We can then take this modulo 10 (again) in order to reduce it to a single digit.

Finally, we multiply the original number by 10, and add our new digit to it.

Anon.
A: 

Another alternative using mod once only

   int sum = 0;
    foreach (char c in s)
        sum += Convert.ToInt32(c.ToString());
    int diff = 0;
    while (sum % 10 != 1)
    {
        sum++; 
        diff++; 
    }
    if (diff > 0)
       s += diff.ToString();
Fadrian Sudaman
A: 

Well, it's easier in C++.

std::string s = boost::lexical_cast<string>( i );
i = i * 10 + 9 - std::accumulate( s.begin(), s.end(), 8 - '0' * s.size() ) % 10;

Addicted to code golf…

Potatoswatter