Având în vedere un număr, sarcina este de a verifica dacă un număr este divizibil cu 16 sau nu. Numărul de intrare poate fi mare și nu poate fi stocat chiar dacă folosim long long int.
Exemple:
Input : n = 1128 Output : No Input : n = 11216 Output : Yes Input : n = 1124273542764284287 Output : No
Deoarece numărul de intrare poate fi foarte mare, nu putem folosi n % 16 pentru a verifica dacă un număr este divizibil cu 16 sau nu, mai ales în limbaje precum C/C++. Ideea se bazează pe următorul fapt.
șir la caracter
A number is divisible by 16 if number formed by last four digits of it is divisible by 16.
Ilustrare:
For example let us consider 769616 Number formed by last four digits = 9616 Since 9522 is divisible by 16 answer is YES.
Cum funcţionează asta?
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
// Java program to find if a number // is divisible by 16 or not import 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.
# Python 3 program to find # if a number is divisible # by 16 or not # Function to find that # number divisible by # 16 or not def 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 code st = '769528' if(check(st)) : print('Yes') else : print('No') # This code is contributed by Nikita Tiwari.
// C# program to find if a number // is divisible by 16 or not using 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 program to find if a number // is divisible by 16 or not // Function to find that // number divisible by 16 or not function 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. ?> <script> // Javascript program to find if a number // is divisible by 16 or not // Function to find that number // divisible by 16 or not function 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 code let str = '769528'; if (check(str)) document.write('Yes'); else document.write('No '); // This code is contributed by decode2207 </script>
Ieșire:
No
Complexitatea timpului: O(1)
Spațiu auxiliar: O(1)
O altă abordare (prin utilizarea operatorului AND pe biți):
Pentru a verifica dacă un număr mare este divizibil cu 16 sau nu fără a folosi operatorul modulo putem verifica ultimii 4 biți ai numărului. Dacă acești biți sunt toți 0, atunci numărul este divizibil cu 16, altfel nu este.
Acest lucru se datorează faptului că 16 este reprezentat în binar ca 0b10000, ceea ce înseamnă că are un 1 în poziția al 5-lea bit și toate 0-urile în cei 4 biți inferiori. Prin urmare, dacă un număr este divizibil cu 16, trebuie să aibă toate 0-urile în cei 4 biți inferiori.
Mai jos este implementarea abordării de mai sus:
hopa concepteC++
#include
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'); } } }
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's num = 769528 if(is_divisible_by_16(num)): print('Yes') else: print('No')
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'); } } }
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'); }
Ieșire
No
Complexitatea timpului: O(1)
Spațiu auxiliar: O(1)
În acest cod folosim operatorul AND pe biți & cu numărul binar 0b1111 (care are toate 1-urile în cei 4 biți inferiori și 0-urile în biții superiori) pentru a extrage ultimii 4 biți ai numărului de intrare num. Apoi verificăm dacă acești 4 biți sunt toți 0 sau nu. Dacă toate sunt 0, funcția returnează True (adică numărul este divizibil cu 16), în caz contrar, returnează False.