I need to write a program that will count how many numbers within an interval have an even sum of digits. you are given two numbers, a and b. i wrote a little program that is a little slow.. it checks for the sum of the digits for every number in the interval. Any suggestions about a better algorithm appreciated.

#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int main()
{
    string c;
    stringstream ss;
    int a,b, rezx, count;
    cin>>a>>b;
    for(int i=a; i<b; i++)
    {
            ss<<i;
            c=ss.str();
            ss.str("");
            for(int x=0; x<c.length(); x++)
            {
                    rezx=rezx+c[x];
            }
            if(rezx%2==0)
            {
                         count++;
            }
            rezx=0;
    }
    cout<<count-1;
    system("pause");
    return 0;
}

I think the following algorithm is a better one:

If you know the starting number of the interval:
-> Check whether the sum of it's digits are even (you could use the modulo operator for this)
-> If the sum was even, you automatically know the next number's sum of digits is odd

e.g: 450 => odd ; 451 => even ; 452 => odd ; 453 => even ; etc. ...

Edit:: So actually you don't have to check each number's sum of digits

Hope this helps ! :)

Comments
Tux is awsome

yeah but what when you get to a number like 159... 1+5+9=15 which is odd. than the next one 160 its odd again.. how do i get over these?

The method described here is probably a more efficient one as yours as it isn't converting the number to a string each time ...

Edit:: I have to admit my previous post was a bad one ...

It's not only the most slow algorithm (the original one) but it's a wrong algorithm. You have got not a sum of digits but a sum of char codes of digits. It's the other story that char code of '0' is even numbert in ASCII table; the C language does not specify this fact.

It's so easy to get the last digit of integer n: n%10 then get the last digit of n /= 10 and so on...

Comments
I also think that's the best method :)

should i try to make an algorithm that checks if the first number's sum of digits is even and than to count the interval until 9 is reached and than to switch? example:
289-false
290-false
291-true
292-false
293-true
....
299-true
300-false
and than to count the true ones

should i try to make an algorithm that checks if the first number's sum of digits is even and than to count the interval until 9 is reached and than to switch? example:
289-false
290-false
291-true
292-false
293-true
....
299-true
300-false
and than to count the true ones

No, you only have to write a function which calculates the sum of the digits of a number (using the information mentioned in my previous post (look at the link) and ArkM's post) ...

I don't understand - why do you have the numbers input as 'int'? Why don't you have the numbers input directly into a string and then use the operator [] to move through the digits and count values? I think it could be much more efficient - just run a loop like for(index=0;index<number.length();index++) and add every digit to a variable that holds the sum. If you assume ASCII, you won't even need to convert the character digits into digits, because their ASCII values are even for even digits.

I don't understand - why do you have the numbers input as 'int'? Why don't you have the numbers input directly into a string and then use the operator [] to move through the digits and count values? I think it could be much more efficient - just run a loop like for(index=0;index<number.length();index++) and add every digit to a variable that holds the sum. If you assume ASCII, you won't even need to convert the character digits into digits, because their ASCII values are even for even digits.

I actually don't understand why you need a string for that purpose, you can do it using mathematical operations only.
Why making it difficult if it can be easy ?

Look at ArkM's post ! :)

I actually don't understand why you need a string for that purpose, you can do it using mathematical operations only.
Why making it difficult if it can be easy ?

Look at ArkM's post ! :)

When you don't need to do calculations with the number there's no reason for doing the mathematical operations on it - you have the possibility to separate the characters more easily usign strings.

When you don't need to do calculations with the number there's no reason for doing the mathematical operations on it - you have the possibility to separate the characters more easily usign strings.

Not agreed, using strings is more processor intensive, dealing with numbers is actually a speed boost ...
BTW, You can get the last digit of a number using the modulo operator like this: lastdigit = number % 10;

Running a loop for such a purpose will look like this using mathematical operations:

unsigned short int a,Sum=0;
a=12522;
   while(a)
   {
   Sum+=a%10;
   a/=10;
   }

Using string operations:

string a;
unsigned short int Sum=0,i;
a="12522";
for(i=0;i<a.length();i++) Sum+=a[i];

I personally prefer the second option when you assume ASCII and don't need a speedy algorithm - for example in this program. It looks clearer for me - more self-explanatory.
It doesn't change much, however. It doesn't worth an argument.

Using string operations:

string a;
unsigned short int Sum=0,i;
a="12522";
for(i=0;i<a.length();i++) Sum+=a[i];

This code isn't returning the sum of the digits in the number !!
And that's the code you prefer ? Code which isn't working ??!!

Dear unbeatable, to make your code work change it to the following:

string a;
unsigned short int Sum=0,i;
a="12522";
for(i=0;i<a.length();i++) Sum+=a[i]-'0';

It's working for determining if the sum is even or not. The Sum mod 2 remains the same.

Can you explain we how it (your example using strings) was working ??

ASCII '0' is 48, '1' is 49... '9' is 57 - '0' mod 2 remains 0, '1' mod 2 remains 1, ... , '9' mod 2 remains 1.

Nope. It doesn't change the answer of Sum%2 simply because '0' mod 2 = 0.
If x=y (mod n), and z=0 (mod n), x+z will still equal y (mod n).

You can try if you don't believe me but this code:

#include <iostream>

using namespace std;

int main()
{
	unsigned short int a,Sum=0;
	a=12522;
	while(a)
	{
		Sum+=a%10;
		a/=10;
	}
	cout << Sum << endl;
}

Has another output than this code:

#include <iostream>

using namespace std;

int main()
{
	string a;
	unsigned short int Sum=0,i;
	a="12522";
	for(i=0;i<a.length();i++) Sum+=a[i];
	cout << Sum << endl;
}

Convinced ?

The result is the same.

Both programs were intended to calculate the sum of the digits of a number, however, the second program's output is different, try it !:angry:

I agree that the sum is different. I said so before. All I say is that the result of what we're interested in, in this case, remains the same - just because the ASCII value of '0' modulo 2 is 0.
We're not interested in the sum of the digits. We're interested to know if the number's sum of digits is even or odd, or in other words: if it's 0 (modulo 2) or 1 (modulo 2) respectively.

Guys instead of USING AN ARPHODOX method to solve your conversion from char to numerical. Why dont you use the atoi() function built in. That way you will not need to care abt any format.

string a;
unsigned short int Sum=0,i;
a="12522";
for(i=0;i<a.length();i++)
{
string b;
b=a[i];
 Sum+=atoi(b.c_str())];
}

Guys instead of USING AN ARPHODOX method to solve your conversion from char to numerical. Why dont you use the atoi() function built in. That way you will not need to care abt any format.

string a;
unsigned short int Sum=0,i;
a="12522";
for(i=0;i<a.length();i++)
{
string b;
b=a[i];
 Sum+=atoi(b.c_str())];
}

Yeah, but with atoi you're again doing conversions, which means it's not the most efficient way ...

just because the ASCII value of '0' modulo 2 is 0.

Agreed, but that's logic: 48 modulo 2 is equal to 0 ...

We're interested to know if the number's sum of digits is even or odd

Agreed.

or in other words: if it's 0 (modulo 2) or 1 (modulo 2) respectively.

You'll have to explain this carefully using an example ...

Agreed, but that's logic: 48 modulo 2 is equal to 0 ...


Agreed.


You'll have to explain this carefully using an example ...

48%2=0;

THats true.
Unbeatable wants

48,
4+8=12;//SUM OF DIGITS
12%2=0// even

Unbeatable wants

48,
4+8=12;//SUM OF DIGITS
12%2=0// even

Agreed with what you're saying, I also want that, but my problem is that Unbeatable explained this in a very strange way ...

I thought I would throw another solution using recursion out there. Not fully tested but should do the job.

int sum_digits(int number)
{
    int remainder = number%10;
    if (remainder > 0)
        return remainder+sum_digits((number-remainder)/10);
    else if (number >= 10 && remainder == 0)
        return sum_digits(number/10);
    return number;
}

bool sum_digits_even(int number)
{
    return !(sum_digits(number) % 2);
}

sorry your algorithm is not working correctly. Any ideas

;)

bool isEven(const char* number)
{
    bool even = false;
    if (number) {
        if (*number == '-' || *number == '+')
            number++;
        if (*number) {
            even = true;
            do switch (*number++) {
                case '1': case '3': case '5': case '7': case '9':
                    even = !even; 
                    continue;
                case '0': case '2': case '4': case '6': case '8':
                    continue;
                default: return false; // not a number
            } while (*number);
        }
    }
    return even;
}
inline
bool isEven(const std::string& number) {
    return isEven(number.c_str());
}
/// for true integers:
bool isEven(unsigned long number)
{
    std::string buff;
    std::ostringstream is(buff);
    (is << number).flush(); 
    return isEven(buff);
}
using std::cout;
using std::cin;
void TestEven()
{
    std::string line;
    while (cout << "Integer: ",std::getline(cin,line))
        cout << isEven(line) << '\n';
}
Comments
That algo is a win.
This article has been dead for over six months. Start a new discussion instead.