Check if a number is a multiple of 3 w/o the module operation

[Nebur]

I want to code a program to check if n is a multiple of 3 basing on the property that if the sum of its didigts is a multiple of 3, then so is n.

I try to reduce the number n until its smaller than 10 so that if it is equal to 3,6 or 9 n was originally a multiple of 3. Otherwise, it wasn't.

I am asked to use a recursive function called sum_of_digits to add up the digits of n as well as a recursive boolean function called is_multiple_of_3 to tell wether it is a multiple or not.

#include <iostream>
using namespace std;

int sum_digits(int n) {
	if (n < 10) return n;
	else return sum_digits(n%10 + sum_digits(n/10));
}

bool is_multiple_3 (int n) {
	int a = sum_digits(n);
	if (a < 10) {
		if (a == 3 or a == 6 or a == 9) return true;
			else return false;
	}
		else return is_multiple_3(a);
}

int main () {
	int n;
	while (cin >> n)  {
		if (is_multiple_3(n)) cout << "SI" << endl;
			else cout << "NO" << endl;
	}
}

In my opinion this code should work perfectly, but somehow it doesen't. It appears that I am missing something or i am not considering a very special case.

Thanks for reading guys!

[norm b]

How is the code not working?

12
SI
42
SI
1002
SI
1001
NO

[Nebur]

I submit the program to an online evaluator that tries it with an incredibly big amount of numbers and it turned out it doesen't work.

[Nebur]

Very annoying! :p

[keskiverto]

How big? Beyond range of int?

[Catfish4]

The algorithm looks OK to me, so how about you change the data type?

Meaning: instead of int use unsigned long int.

int sum_digits(unsigned long int n);
bool is_multiple_3 (unsigned long int n);

[JLBorges]

> It appears that I am missing something or i am not considering a very special case.

Yes. The number being negative.

To return the sum of digits:

int sum_digits(int n) {
	if (n < 10) return n;
	// else return sum_digits(n%10 + sum_digits(n/10));
	else return n%10 + sum_digits(n/10) ; 
} 

[Chervil]

Rather than analysing the actual code, I just tested it with a lot of values:
i

nt main () 
{
    
    for (int n=0; n<10000000; n++)
    {
        if (is_multiple_3(n)) 
        {
            if (n%3 != 0)
            {
                cout << n << " Not Valid A" <<  endl;
            }
        }
        else
        {
            if (n%3 == 0)
            {
                cout << n << " Not Valid B" <<  endl;
            }
        }
    }
    cout << "Done" << endl;
    return 0;
}

Output:

0 Not Valid B
Done

which indicates the code fails for n == 0.

But change the for loop like this:
for (int n=-10; n<10; n++)

-9 Not Valid B
-6 Not Valid B
-3 Not Valid B
0 Not Valid B
Done

Which shows that negative numbers don't work too.

[Nebur]

Thanks to everyone that tried to help :D

I forgot to say that the program has to work only with strictly positive integer numbers this means, no negative numbers nor 0 :p

[Nebur]

Looks like the online evaluator has gone mad ^^

[Chervil]

This might work

unsigned int sum_digits(int n) 
{
    if (n < 0)
        n = -n;
        
    if (n < 10) 
        return n;
    else 
        return sum_digits(n%10 + sum_digits(n/10));
}

bool is_multiple_3 (int n) 
{
    unsigned int a = sum_digits(n);

    if (a < 10) 
    {
        if (a == 3 or a == 6 or a == 9 or a==0) 
            return true;
        else 
            return false;
    }
    else 
        return is_multiple_3(a);
}

[Nebur]

But the program doesen't need to work for negative numbers, only positive ones.

[Chervil]

Regardless of that, did you test it with the online evaluator ?

[Nebur]

I'm on it i will tell you as soon as I know.

EDIT: nvm, it will not work because the name of the functions must be exactly "int sum_digits(int n)" and "bool is_multiple_3 (int n)"

[Chervil]

That isn't a major problem. I made that change as part of some other variations I tried. You can change it back from unsigned int to just int.

[Duthomhas]

Are you sure the online test program isn't just timing out? You are doing massive amounts of recursion.

[edit] I just tested it for x in [1, 1000000000]. No errors reported.

[JLBorges]

Try this:

#include <iostream>

static constexpr int MAX = 1000000 ;
static int sum[MAX] {0} ;

int sum_digits( int n ) // invariant: n > 0
{
    if( n < MAX ) return sum[n] ;
    else return sum[n%MAX] + sum_digits( n/MAX ) ;
}

bool is_multiple_3( int n ) // invariant: n > 0
{
    if( n < MAX ) return sum[n] == 0 ;
    else return is_multiple_3( sum_digits(n) ) ;
}

int main ()
{
    std::cout.sync_with_stdio(false) ;
    std::cin.tie(nullptr) ;

    int v = 0 ;
    for( int i = 0 ; i < MAX ; ++i )
    {
        sum[i] = v ;
        ++v ;
        if( v == 3 ) v = 0 ;
    }

    int n ;
	while( std::cin >> n )
	    std::cout << ( is_multiple_3(n) ? "SI" : "NO" ) << '\n' ;
}