Problem

Determine whether a non-negative integer n is divisible by 17 using bitwise operations and simple arithmetic — avoid full integer division where possible.

Examples

Example 1

1
2
3

Input: n = 34
Output: true
Explanation: 34 is divisible by 17.

Example 2

1
2

Input: n = 18
Output: false

Solution

Method 1 - Use mod arithmetic / builtin division

Well the simplest way is to use modulo operator, but we shouldn’t use arithmetic operators.

Intuition

If you can use integer division or %, the check n % 17 == 0 is simplest and usually optimized.

Code

C++
1
2
3

bool isDivBy17_direct(unsigned long long n) {
     return n % 17 == 0;
}

Complexity

  • ⏰ Time complexity: O(1) on typical hardware (single division instruction).
  • 🧺 Space complexity: O(1).

Method 2 — Recursive / Iterative reduction using q - r

Intuition

Use the congruence 16 ≡ −1 (mod 17) to replace division by 17 with a cheap bitwise reduction. Writing n = 16*q + r (so q = n » 4 and r = n & 15) gives

1

n ≡ -q + r  (mod 17)

Hence n ≡ 0 (mod 17) ⇔ q − r ≡ 0 (mod 17). Repeatedly replacing m by |(m»4) − (m&15)| shrinks m by roughly a factor of 16 each step and preserves divisibility-by-17.

Below are the algebraic steps that justify the reduction:

1
2
3

n/17 = (16*n)/(17*16)
     = (17 - 1)*n/(17*16)
     = (n/16) - (n/(17*16))

1
2

n/17 = floor(n/16) + (n%16)/16 - (floor(n/16) + (n%16)/16)/17
     = floor(n/16) - (floor(n/16)-n%16)/17

The final line shows n/17 is integral exactly when floor(n/16) - (n%16) is a multiple of 17. Replacing floor(n/16) with n >> 4 and n%16 with n & 15 yields the bitwise test.

Approach

  • Initialize m = abs(n) to avoid unsigned underflow.
  • While m >= 17:
    • q = m >> 4 and r = m & 15.
    • m = abs(q - r).
  • After the loop, n is divisible by 17 iff m == 0 or m == 17.
Edge cases
  • If n == 0 return true.
  • Use absolute value to handle intermediate negatives; restrict to non-negative inputs when desired.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <cstdlib>

class Solution {
 public:
     bool isDivBy17(unsigned long long n) {
          if (n == 0) return true;
          long long m = static_cast<long long>(n);
          while (m >= 17) {
               long long q = m >> 4;
               long long r = m & 15;
               m = llabs(q - r);
          }
          return (m == 0) || (m == 17);
     }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

package main

import "math"

func IsDivBy17(n uint64) bool {
          if n == 0 {
                    return true
          }
          m := int64(n)
          for m >= 17 {
                    q := m >> 4
                    r := m & 15
                    m = int64(math.Abs(float64(q - r)))
          }
          return m == 0 || m == 17
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
          public boolean isDivBy17(long n) {
                    if (n == 0) return true;
                    long m = Math.abs(n);
                    while (m >= 17) {
                              long q = m >> 4;
                              long r = m & 15;
                              m = Math.abs(q - r);
                    }
                    return m == 0 || m == 17;
          }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
          def is_div_by_17(self, n: int) -> bool:
                    if n == 0:
                              return True
                    m = abs(n)
                    while m >= 17:
                              q = m >> 4
                              r = m & 15
                              m = abs(q - r)
                    return m == 0 or m == 17

Complexity

  • ⏰ Time complexity: O(log_{16} n) = O(log n). Each reduction divides the magnitude roughly by 16.
  • 🧺 Space complexity: O(1).