A well-kown mathematical property states that a natural number is a multiple of three if and only if the sum of its digits is also a multiple of three. For instance, the sum of the digits of 8472 is 8 + 4 + 7 + 2 = 21, which is a multiple of three. Therefore, 8472 is also a multiple of three.

Implement a recursive function that tells if a strictly positive natural number *n*
is a multiple of three or not.

**Interface**

C++ | bool is_multiple_3(int n); |

C | int is_multiple_3(int n); |

Java | public static boolean isMultiple3(int n); |

Python | is_multiple_3(n) # returns bool |

is_multiple_3(n: int) -> bool |

Solve this problem using a recursive function to return the sum of the digits of a natural number *n*.

**Interface**

C++ | int sum_of_digits(int n); |

C | int sum_of_digits(int n); |

Java | public static int sumOfDigits(int n); |

Python | sum_of_digits(n) # returns int |

sum_of_digits(n: int) -> int |

**Observation**

Here, you are allowed to use the operations of division and integer remainder only with the number 10. Otherwise, this exercise would be totally trivial!

Public test cases

**Input/Output**

is_multiple_3(8472) → true

is_multiple_3(8473) → false

is_multiple_3(4) → false

is_multiple_3(8473) → false

is_multiple_3(4) → false

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C C++ Java Python
- User solutions
- C C++ Java Python