Zadani broj zadatak je provjeriti je li broj djeljiv sa 16 ili ne. Ulazni broj može biti velik i možda ga neće biti moguće pohraniti čak i ako koristimo long long int.
Primjeri:
Input : n = 1128 Output : No Input : n = 11216 Output : Yes Input : n = 1124273542764284287 Output : No
Budući da ulazni broj može biti vrlo velik, ne možemo koristiti n % 16 da provjerimo je li broj djeljiv sa 16 ili nije, posebno u jezicima poput C/C++. Ideja se temelji na sljedećoj činjenici.
mrežni sloj u računalnim mrežama
A number is divisible by 16 if number formed by last four digits of it is divisible by 16.
Ilustracija:
For example let us consider 769616 Number formed by last four digits = 9616 Since 9522 is divisible by 16 answer is YES.
Kako ovo radi?
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>
Izlaz:
No
Vremenska složenost: O(1)
Pomoćni prostor: O(1)
Drugi pristup (upotrebom operatora AND po bitovima):
Da bismo provjerili je li veliki broj djeljiv sa 16 ili ne bez korištenja modulo operatora, možemo provjeriti zadnja 4 bita broja. Ako su svi ovi bitovi 0, onda je broj djeljiv sa 16, inače nije.
To je zato što je 16 binarno predstavljeno kao 0b10000 što znači da ima 1 na poziciji 5. bita i sve 0 u niža 4 bita. Stoga, ako je broj djeljiv sa 16, mora imati sve 0 u niža 4 bita.
U nastavku je implementacija gornjeg pristupa:
C++#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'); }
Izlaz
No
Vremenska složenost: O(1)
Pomoćni prostor: O(1)
U ovom kodu koristimo bitovni AND operator & s binarnim brojem 0b1111 (koji ima sve 1 u niža 4 bita i 0 u gornja bita) za izdvajanje posljednja 4 bita ulaznog broja num. Zatim provjeravamo jesu li sva ova 4 bita nule ili ne. Ako su sve nule, funkcija vraća True (što znači da je broj djeljiv sa 16), inače vraća False.
ssis