Kun luku on annettu, tehtävänä on tarkistaa, onko luku jaollinen 16:lla vai ei. Syötenumero voi olla suuri, eikä sitä ehkä voida tallentaa, vaikka käyttäisimme long long int.
Esimerkkejä:
Input : n = 1128 Output : No Input : n = 11216 Output : Yes Input : n = 1124273542764284287 Output : No
Koska syötettävä luku voi olla hyvin suuri, emme voi käyttää n % 16:ta tarkistamaan, onko luku jaollinen 16:lla vai ei varsinkaan kielissä, kuten C/C++. Ajatus perustuu seuraavaan tosiasiaan.
bellfordin algoritmi
A number is divisible by 16 if number formed by last four digits of it is divisible by 16.
Kuva:
For example let us consider 769616 Number formed by last four digits = 9616 Since 9522 is divisible by 16 answer is YES.
Miten tämä toimii?
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>
Lähtö:
No
Aika monimutkaisuus: O(1)
Aputila: O(1)
Toinen lähestymistapa (käyttämällä AND-bittikohtaista operaattoria):
Tarkistaaksemme, onko suuri luku jaollinen 16:lla vai ei, ilman modulo-operaattoria, voimme tarkistaa luvun 4 viimeistä bittiä. Jos nämä bitit ovat kaikki nollia, luku on jaollinen 16:lla, muuten se ei ole.
Tämä johtuu siitä, että 16 esitetään binäärimuodossa 0b10000, mikä tarkoittaa, että sillä on 1 viidennessä bittipaikassa ja kaikki 0:t alemmassa 4 bitissä. Siksi jos luku on jaollinen 16:lla, siinä on oltava kaikki 0:t alemmassa 4 bitissä.
Alla on yllä olevan lähestymistavan toteutus:
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'); }
Lähtö
No
Aika monimutkaisuus: O(1)
Aputila: O(1)
mysql-määrä
Tässä koodissa käytämme bittikohtaista AND-operaattoria & binääriluvulla 0b1111 (jossa on kaikki 1:t 4 alimmassa bitissä ja 0:t ylemmissä biteissä) poimimaan syötenumeron num viimeiset 4 bittiä. Sitten tarkistamme, ovatko nämä 4 bittiä kaikki nollia vai eivät. Jos ne ovat kaikki nollia, funktio palauttaa True (eli luku on jaollinen 16:lla), muuten se palauttaa False.