Write an Efficient Method to Check if a Number is Multiple of 3

Introduction

Navi.

Determining whether a given integer is a multiple of 3 is a common programming task that arises in various contexts, such as data validation, mathematical operations, and algorithmic problems. Efficiently solving this problem is important because being able to quickly and accurately identify multiples of 3 has applications in fields like finance, cryptography, and computer science.

In this article, we will explore three different approaches to check if a number is a multiple of 3, each with its own strengths and tradeoffs. We will dive into the details of each method, provide pseudocode and code examples in multiple programming languages, and discuss the time and space complexities of the solutions.

Approach 1: Using Repeated Sum of Digits

Explanation

The first approach is based on the divisibility rule of 3, which states that a number is a multiple of 3 if the sum of its digits is also a multiple of 3. Instead of directly checking divisibility, we can repeatedly sum the digits of the number until we get a single-digit number. If the final result is 3, 6, or 9, the original number is divisible by 3; otherwise, it is not.

The idea behind this method is to leverage the fact that the sum of the digits of a number is a multiple of 3 if and only if the original number is a multiple of 3. By repeatedly summing the digits, we can efficiently determine the divisibility of the number without performing any complex operations.

Pseudocode

function isMultipleOf3(n):
    if n < 0:
        n = -n

    while n > 9:
        n = sumOfDigits(n)

    return n == 3 or n == 6 or n == 9

function sumOfDigits(n):
    sum = 0
    while n > 0:
        sum += n % 10
        n = n // 10
    return sum

Code Examples

C++

#include <bits/stdc++.h>
using namespace std;

int sumOfDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

bool isMultipleOf3(int n) {
    if (n < 0) {
        n = -n;
    }
    while (n > 9) {
        n = sumOfDigits(n);
    }
    return (n == 3 || n == 6 || n == 9);
}

int main() {
    int n = 9;
    if (isMultipleOf3(n)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Java

class GfG {
    static int sumOfDigits(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    static boolean isMultipleOf3(int n) {
        if (n < 0) {
            n = -n;
        }
        while (n > 9) {
            n = sumOfDigits(n);
        }
        return (n == 3 || n == 6 || n == 9);
    }

    public static void main(String[] args) {
        int n = 9;
        if (isMultipleOf3(n)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Python

def sumOfDigits(n):
    sum = 0
    while n > 0:
        sum += n % 10
        n //= 10
    return sum

def isMultipleOf3(n):
    if n < 0:
        n = -n
    while n > 9:
        n = sumOfDigits(n)
    return (n == 3 or n == 6 or n == 9)

if __name__ == "__main__":
    n = 9
    if isMultipleOf3(n):
        print("Yes")
    else:
        print("No")

C#

using System;

class GfG {
    static int sumOfDigits(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    static bool isMultipleOf3(int n) {
        if (n < 0) {
            n = -n;
        }
        while (n > 9) {
            n = sumOfDigits(n);
        }
        return (n == 3 || n == 6 || n == 9);
    }

    static void Main() {
        int n = 9;
        if (isMultipleOf3(n)) {
            Console.WriteLine("Yes");
        } else {
            Console.WriteLine("No");
        }
    }
}

JavaScript

function sumOfDigits(n) {
    let sum = 0;
    while (n > 0) {
        sum += n % 10;
        n = Math.floor(n / 10);
    }
    return sum;
}

function isMultipleOf3(n) {
    if (n < 0) {
        n = -n;
    }
    while (n > 9) {
        n = sumOfDigits(n);
    }
    return (n == 3 || n == 6 || n == 9);
}

let n = 9;
if (isMultipleOf3(n)) {
    console.log("Yes");
} else {
    console.log("No");
}

Time and Space Complexity

The time complexity of this approach is O(log n), as we need to repeatedly sum the digits of the number until we reach a single-digit number. The space complexity is O(1), as we only use a constant amount of additional memory to store the intermediate sum.

Approach 2: Using Binary Representation

Explanation

The second approach is based on the binary representation of a number. The key observation is that even powers of 2 contribute (3k+1) and odd powers contribute (3k-1) modulo 3. By counting the set bits at odd and even positions and checking their difference, we can determine if the number is divisible by 3.

The mathematical proof behind this approach is as follows:

Consider a number n represented in binary form as abcde. Its decimal equivalent is:

n = (2^4 * a) + (2^3 * b) + (2^2 * c) + (2^1 * d) + (2^0 * e)

Observing powers of 2 modulo 3, we derive:

  • Even powers of 2 can be expressed as 3k + 1 (e.g., 2^0 = 1, 2^2 = 3k + 1).
  • Odd powers of 2 can be expressed as 3k – 1 (e.g., 2^1 = 3k – 1, 2^3 = 3k – 1).

Rewriting the decimal representation in terms of multiples of 3, we get:

n = (3k+1) * a + (3k-1) * b + (3k+1) * c + (3k-1) * d + (3k+1) * e

Rearranging the terms:

n = (3k)(a+b+c+d+e) + (a + c + e) - (b + d)

Since the first term is always a multiple of 3, for n to be a multiple of 3, the expression (a + c + e) - (b + d) must also be a multiple of 3. Thus, a number is divisible by 3 if and only if the difference between the count of set bits at odd positions and even positions is a multiple of 3.

Pseudocode

function isMultipleOf3(n):
    if n < 0:
        n = -n

    if n == 0 or n == 1:
        return n == 0

    odd_count = 0
    even_count = 0

    while n > 0:
        if n & 1 == 1:
            odd_count += 1
        n >>= 1

        if n & 1 == 1:
            even_count += 1
        n >>= 1

    return isMultipleOf3(abs(odd_count - even_count))

Code Examples

C++

#include <bits/stdc++.h>
using namespace std;

bool isMultipleOf3(int n) {
    if (n < 0) {
        n = -n;
    }

    if (n == 0) {
        return true;
    }
    if (n == 1) {
        return false;
    }

    int odd_count = 0, even_count = 0;
    while (n) {
        if (n & 1) {
            odd_count++;
        }
        n >>= 1;

        if (n & 1) {
            even_count++;
        }
        n >>= 1;
    }

    return isMultipleOf3(abs(odd_count - even_count));
}

int main() {
    int n = 9;
    if (isMultipleOf3(n)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Java

class GfG {
    static boolean isMultipleOf3(int n) {
        if (n < 0) {
            n = -n;
        }

        if (n == 0) {
            return true;
        }
        if (n == 1) {
            return false;
        }

        int odd_count = 0, even_count = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                odd_count++;
            }
            n >>= 1;

            if ((n & 1) == 1) {
                even_count++;
            }
            n >>= 1;
        }

        return isMultipleOf3(Math.abs(odd_count - even_count));
    }

    public static void main(String[] args) {
        int n = 9;
        if (isMultipleOf3(n)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Python

def isMultipleOf3(n):
    if n < 0:
        n = -n

    if n == 0:
        return True
    if n == 1:
        return False

    odd_count = 0
    even_count = 0

    while n:
        if n & 1:
            odd_count += 1
        n >>= 1

        if n & 1:
            even_count += 1
        n >>= 1

    return isMultipleOf3(abs(odd_count - even_count))

if __name__ == "__main__":
    n = 9
    if isMultipleOf3(n):
        print("Yes")
    else:
        print("No")

C#

using System;

class GfG {
    static bool isMultipleOf3(int n) {
        if (n < 0) {
            n = -n;
        }

        if (n == 0) {
            return true;
        }
        if (n == 1) {
            return false;
        }

        int odd_count = 0, even_count = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                odd_count++;
            }
            n >>= 1;

            if ((n & 1) == 1) {
                even_count++;
            }
            n >>= 1;
        }

        return isMultipleOf3(Math.Abs(odd_count - even_count));
    }

    static void Main() {
        int n = 9;
        if (isMultipleOf3(n)) {
            Console.WriteLine("Yes");
        } else {
            Console.WriteLine("No");
        }
    }
}

JavaScript

function isMultipleOf3(n) {
    if (n < 0) {
        n = -n;
    }

    if (n === 0) {
        return true;
    }
    if (n === 1) {
        return false;
    }

    let odd_count = 0, even_count = 0;
    while (n > 0) {
        if (n & 1) {
            odd_count++;
        }
        n >>= 1;

        if (n & 1) {
            even_count++;
        }
        n >>= 1;
    }

    return isMultipleOf3(Math.abs(odd_count - even_count));
}

let n = 9;
if (isMultipleOf3(n)) {
    console.log("Yes");
} else {
    console.log("No");
}

Time and Space Complexity

The time complexity of this approach is also O(log n), as we need to repeatedly right-shift the number and count the set bits at odd and even positions. The space complexity is O(log n), as we need to store the intermediate odd and even counts during the recursive calls.

Approach 3: Using Modulo Division

Explanation

The third approach is the most straightforward and efficient method to check if a number is a multiple of 3. It is based on the observation that a number n is a multiple of 3 if and only if n % 3 == 0, meaning it leaves no remainder when divided by 3.

This approach leverages the modulo operation, which is a highly optimized and efficient operation in most programming languages. By simply checking the remainder of the division by 3, we can determine whether the number is a

Did you like this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.