Check divisibility by 7

Given a number n, the task is to check if it is divisible by 7 or not.
Note: You are not allowed to use the modulo operator, floating point arithmetic is also not allowed. 

Examples:

Input: n = 371
Output: True
Explanation: The number 371: 37 – (2×1) = 37 – 2 = 35; 3 – (2 × 5) = 3 – 10 = -7; thus, since -7 is divisible by 7, 371 is divisible by 7.

Input: n = 7673
Output: False
Explanation: The number 7673: 767 – (2×3) = 767 – 6 = 761; 76 – (2 × 1) = 76 – 2 = 74; 7 – (2 × 4) = 7 – 8 = -1; thus, since -1 is not divisible by 7, 7673 is not divisible by 7.

[Naive Approach] Using Repeated Subtraction – O(n) Time and O(1) Space 

A simple method is repeated subtraction.

• Repeated subtraction is done by continuously subtracting 7 from the given number n.
• If at any point, the result of subtraction becomes zero, the number is divisible by 7.
• If the number reduces to a value smaller than 7, and is not zero, it’s not divisible by 7.

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

bool isDivBy7(int n) {
    if (n == 0) 
        return true;
    while (n >= 7) {
        n -= 7;  
    }
    return n == 0;  
}

int main() {
    int n = 371;
    if(isDivBy7(abs(n)))
    cout<<"True"<<"\n";
    else
    cout<<"False"<<"\n";
    return 0;
}

public class GfG {
    public static boolean isDivBy7(int n)
    {
        if (n == 0)
            return true;
        while (n >= 7) {
            n -= 7;
        }
        return n == 0;
    }

    public static void main(String[] args)
    {
        int n = 371;
        if (isDivBy7(Math.abs(n)))
            System.out.println("True");
        else
            System.out.println("False");
    }
}

def isDivBy7(n):
    if n == 0:
        return True
    while n >= 7:
        n -= 7
    return n == 0

n = 371
print(isDivBy7(abs(n)))

using System;

class Program {
    static bool isDivBy7(int n) {
        if (n == 0) {
            return true;
        }
        while (n >= 7) {
            n -= 7;
        }
        return n == 0;
    }

    static void Main() {
        int n = 371;
        Console.WriteLine(isDivBy7(Math.Abs(n)));
    }
}

// Function to check if a number is divisible by 7
function isDivBy7(n) {
    if (n === 0) 
        return true;
    while (n >= 7) {
        n -= 7;
    }
    return n === 0;
}

// Main function
const n = 371;
if (isDivBy7(Math.abs(n)))
    console.log("True");
else
    console.log("False");

True

[Expected Approach] Using Iterative Division– O(log₁₀n) Time and O(1) Space

A number of the form 10a + b is divisible by 7 if and only if a – 2b is divisible by 7. In other words, subtract twice the last digit from the number formed by the remaining digits. Continue to do this until a small number. 

• Start by checking if the number is 0 or 7, as these are trivially divisible by 7.
• Iteratively remove the last digit and apply the rule: subtract twice the last digit from the remaining number.
• Repeat the process until a single-digit number is left, and check if it’s 0 or 7 to confirm divisibility.

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

bool isDivBy7(int n)
{
    if (n == 0 || n == 7)
        return true;

    while (n >= 10)
    {
        int lastD = n % 10;
        n = n / 10;
        n = abs(n - 2 * lastD);
    }

    return n == 0 || n == 7;
}

int main()
{
    int n = 371;
    if (isDivBy7(abs(n)))
    {
        cout << "True\n";
    }
    else
    {
        cout << "False\n";
    }
    return 0;
}

// Java implementation
public class GfG {
    public static boolean isDivBy7(int n)
    {
        if (n == 0 || n == 7)
            return true;

        while (n >= 10) {
            int lastD = n % 10;
            n = n / 10;
            n = Math.abs(n - 2 * lastD);
        }

        return n == 0 || n == 7;
    }

    public static void main(String[] args)
    {
        int n = 371;
        if (isDivBy7(Math.abs(n))) {
            System.out.println("True");
        }
        else {
            System.out.println("False");
        }
    }
}

# Python implementation
def isDivBy7(n):
    if n == 0 or n == 7:
        return True

    while n >= 10:
        lastD = n % 10
        n //= 10
        n = abs(n - 2 * lastD)

    return n == 0 or n == 7


n = 371
if isDivBy7(abs(n)):
    print("True")
else:
    print("False")

// C# implementation
using System;

class GfG{
    static bool isDivBy7(int n) {
        if (n == 0 || n == 7)
            return true;

        while (n >= 10) {
            int lastD = n % 10;
            n /= 10;
            n = Math.Abs(n - 2 * lastD);
        }

        return n == 0 || n == 7;
    }

    static void Main() {
        int n = 371;
        if (isDivBy7(Math.Abs(n))) {
            Console.WriteLine("True");
        } else {
            Console.WriteLine("False");
        }
    }
}

// JavaScript implementation
function isDivBy7(n) {
    if (n === 0 || n === 7)
        return true;

    while (n >= 10) {
        const lastD = n % 10;
        n = Math.floor(n / 10);
        n = Math.abs(n - 2 * lastD);
    }

    return n === 0 || n === 7;
}

const n = 371;
if (isDivBy7(Math.abs(n))) {
    console.log("True");
} else {
    console.log("False");
}

True

How does this work? Let ‘b’ be the last digit of a number ‘n’ and let ‘a’ be the number we get when we split off ‘b’. 
The representation of the number may also be multiplied by any number relatively prime to the divisor without changing its divisibility. After observing that 7 divides 21, we can perform the following: 

 10.a + b 

after multiplying by 2, this becomes  

 20.a + 2.b 

and then 

 21.a - a + 2.b 

Eliminating the multiple of 21 gives 

 -a + 2b

and multiplying by -1 gives 

 a - 2b

Time Complexity: O(log₁₀n) The number of digits in the number is the no of times the iteration occurs.

If suppose the number given is very large like 10¹⁰⁰⁰⁰⁰ then you can take input in the form of string and can use a-2b approach using addition and subtraction of strings, but then the complexity will be O(n²), where n is the length of the number.

Space Complexity: O(1)

kartik

Follow

Improve

Article Tags :

• DSA
• Mathematical
• Basic Coding Problems
• divisibility

Practice Tags :

• Mathematical