Given a number, the task is to check if a number is divisible by 16 or not. The input number may be large and it may not be possible to store even if we use long long int.
Examples:
Input : n = 1128 Output : No Input : n = 11216 Output : Yes Input : n = 1124273542764284287 Output : No
Since input number may be very large, we cannot use n % 16 to check if a number is divisible by 16 or not, especially in languages like C/C++. The idea is based on following fact.
A number is divisible by 16 if number formed by last four digits of it is divisible by 16.
Illustration:
For example, let us consider 769616 Number formed by last four digits = 9616 Since 9522 is divisible by 16, answer is YES.
How does this work?
Let us consider 76952, we can write it as 76942 = 7*10000 + 6*1000 + 9*100 + 5*10 + 2 The proof is based on below observation: Remainder of 10i divided by 16 is 0 if i greater than or equal to four. Note that 10000, 100000,... etc lead to remainder 0 when divided by 16. So remainder of "7*10000 + 6*1000 + 9*100 + 5*10 + 2" divided by 16 is equivalent to remainder of following : 0 + 6*1000 + 9*100 + 5*10 + 2 = 6952 Therefore we can say that the whole number is divisible by 16 if 6952 is divisible by 16.
C++
// C++ program to find if a number// is divisible by 16 or not#include<bits/stdc++.h>using namespace std;// Function to find that// number divisible by 16 or notbool check(string str){ int n = str.length(); // Empty string if (n == 0 && n == 1) return false; // If there is double digit if (n == 2) return (((str[n-2]-'0')*10 + (str[n-1]-'0'))%16 == 0); // If there is triple digit if(n == 3) return ( ((str[n-3]-'0')*100 + (str[n-2]-'0')*10 + (str[n-1]-'0'))%16 == 0); // If number formed by last four // digits is divisible by 16. int last = str[n-1] - '0'; int second_last = str[n-2] - '0'; int third_last = str[n-3] - '0'; int fourth_last = str[n-4] - '0'; return ((fourth_last*1000 + third_last*100 + second_last*10 + last) % 16 == 0);}// Driver codeint main(){ string str = "769528"; check(str)? cout << "Yes" : cout << "No "; return 0;} |
Java
// Java program to find if a number// is divisible by 16 or notimport java.io.*;class GFG { // Function to find that // number divisible by 16 or not static boolean check(String str) { int n = str.length(); // Empty string if (n == 0 && n == 1) return false; // If there is double digit if (n == 2) return (((str.charAt(n-2)-'0')*10 + (str.charAt(n-1)-'0'))%16 == 0); // If there is triple digit if(n == 3) return ( ((str.charAt(n-3)-'0')*100 + (str.charAt(n-2)-'0')*10 + (str.charAt(n-1)-'0'))%16 == 0); // If number formed by last // four digits is divisible by 16. int last = str.charAt(n-1) - '0'; int second_last = str.charAt(n-2) - '0'; int third_last = str.charAt(n-3) - '0'; int fourth_last = str.charAt(n-4) - '0'; return ((fourth_last*1000 + third_last*100 + second_last*10 + last) % 16 == 0); } // Driver code public static void main(String args[]) { String str = "769528"; if(check(str)) System.out.println("Yes"); else System.out.println("No "); }}// This code is contributed by Nikita Tiwari. |
Python3
# Python 3 program to find# if a number is divisible# by 16 or not# Function to find that# number divisible by# 16 or notdef check(st) : n = len(st) # Empty string if (n == 0 and n == 1) : return False # If there is double digit if (n == 2) : return ((int)(st[n-2])*10 + ((int)(st[n-1])%16 == 0)) # If there is triple digit if(n == 3) : return ( ((int)(st[n-3])*100 + (int)(st[n-2])*10 + (int)(st[n-1]))%16 == 0) # If number formed by last # four digits is divisible # by 16. last = (int)(st[n-1]) second_last = (int)(st[n-2]) third_last = (int)(st[n-3]) fourth_last = (int)(st[n-4]) return ((fourth_last*1000 + third_last*100 + second_last*10 + last) % 16 == 0)# Driver codest = "769528"if(check(st)) : print("Yes")else : print("No") # This code is contributed by Nikita Tiwari. |
C#
// C# program to find if a number// is divisible by 16 or notusing System;class GFG { // Function to find that number // divisible by 16 or not static bool check(String str) { int n = str.Length; // Empty string if (n == 0 && n == 1) return false; // If there is double digit if (n == 2) return (((str[n - 2] - '0') * 10 + (str[n - 1] - '0')) % 16 == 0); // If there is triple digit if(n == 3) return (((str[n - 3] - '0') * 100 + (str[n - 2] - '0') * 10 + (str[n - 1] - '0')) % 16 == 0); // If number formed by last // four digits is divisible by 16. int last = str[n - 1] - '0'; int second_last = str[n - 2] - '0'; int third_last = str[n - 3] - '0'; int fourth_last = str[n - 4] - '0'; return ((fourth_last * 1000 + third_last * 100 + second_last * 10 + last) % 16 == 0); } // Driver code public static void Main() { String str = "769528"; if(check(str)) Console.Write("Yes"); else Console.Write("No "); }}// This code is contributed by Nitin Mittal. |
PHP
<?php// PHP program to find if a number// is divisible by 16 or not// Function to find that// number divisible by 16 or notfunction check($str){ $n = strlen($str); // Empty string if ($n == 0 && $n == 1) return false; // If there is double digit if ($n == 2) return ((($str[$n - 2] - '0') * 10 + ($str[$n - 1] - '0')) % 16 == 0); // If there is triple digit if($n == 3) return ((($str[$n -3] - '0') * 100 + ($str[$n - 2] - '0') * 10 + ($str[$n - 1] - '0')) % 16 == 0); // If number formed by last four // digits is divisible by 16. $last = $str[$n - 1] - '0'; $second_last = $str[$n - 2] - '0'; $third_last = $str[$n - 3] - '0'; $fourth_last = $str[$n - 4] - '0'; return (($fourth_last * 1000 + $third_last * 100 + $second_last * 10 + $last) % 16 == 0);}// Driver code$str = "769528";$x = check($str) ? "Yes" : "No ";echo($x);// This code is contributed by Ajit.?> |
Javascript
<script>// Javascript program to find if a number// is divisible by 16 or not// Function to find that number // divisible by 16 or notfunction check(str){ let n = str.length; // Empty string if (n == 0 && n == 1) return false; // If there is double digit if (n == 2) return (((str[n - 2] - '0') * 10 + (str[n - 1] - '0')) % 16 == 0); // If there is triple digit if(n == 3) return (((str[n - 3] - '0') * 100 + (str[n - 2] - '0') * 10 + (str[n - 1] - '0')) % 16 == 0); // If number formed by last // four digits is divisible by 16. let last = str[n - 1] - '0'; let second_last = str[n - 2] - '0'; let third_last = str[n - 3] - '0'; let fourth_last = str[n - 4] - '0'; return ((fourth_last * 1000 + third_last * 100 + second_last * 10 + last) % 16 == 0);}// Driver codelet str = "769528";if (check(str)) document.write("Yes");else document.write("No "); // This code is contributed by decode2207</script> |
Output:
No
Time Complexity: O(1)
Auxiliary Space: O(1)
Another Approach(By Using the AND bitwise Operator):
To check if a large number is divisible by 16 or not without using the modulo operator, we can check the last 4 bits of the number. If these bits are all 0’s, then the number is divisible by 16, otherwise, it is not.
This is because 16 is represented in binary as 0b10000, which means it has a 1 in the 5th bit position and all 0’s in the lower 4 bits. Therefore, if a number is divisible by 16, it must have all 0’s in the lower 4 bits.
Below is the implementation of above approach:
C++
#include <iostream>using namespace std;// Function to check if a number is divisible by 16bool is_divisible_by_16(int num) { int last_four_bits = num & 0b1111; // bitwise AND with 0b1111 to get the last 4 bits return last_four_bits == 0; // check if all 4 bits are 0's}int main() { int num = 769528; if (is_divisible_by_16(num)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0;} |
Java
import java.io.*;public class Gfg { // Function to check if a number is divisible by 16 static boolean is_divisible_by_16(int num) { int lastFourBits = num & 0b1111; // bitwise AND with 0b1111 to get the last 4 bits return lastFourBits == 0; // check if all 4 bits are 0's } public static void main(String[] args) { int num = 769528; if (is_divisible_by_16(num)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
def is_divisible_by_16(num): last_four_bits = num & 0b1111 # bitwise AND with 0b1111 to get the last 4 bits return last_four_bits == 0 # check if all 4 bits are 0'snum = 769528if(is_divisible_by_16(num)): print("Yes")else: print("No") |
C#
using System;class MainClass { static bool IsDivisibleBy16(int num) { int lastFourBits = num & 0b1111; // bitwise AND with 0b1111 to get the last 4 bits return lastFourBits == 0; // check if all 4 bits are 0's } public static void Main (string[] args) { int num = 769528; if (IsDivisibleBy16(num)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }} |
Javascript
function is_divisible_by_16(num) { let last_four_bits = num & 0b1111; // bitwise AND with 0b1111 to get the last 4 bits return last_four_bits === 0; // check if all 4 bits are 0's}let num = 769528;if (is_divisible_by_16(num)) { console.log("Yes");} else { console.log("No");} |
Output
No
Time Complexity: O(1)
Auxiliary Space: O(1)
In this code, we use the bitwise AND operator & with the binary number 0b1111 (which has all 1’s in the lower 4 bits and 0’s in the upper bits) to extract the last 4 bits of the input number num. Then, we check if these 4 bits are all 0’s or not. If they are all 0’s, the function returns True (meaning the number is divisible by 16), otherwise it returns False.
This article is contributed by Danish_Raza. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
