Dots skaitlis, uzdevums ir pārbaudīt, vai skaitlis dalās ar 16 vai nē. Ievades numurs var būt liels, un to var nebūt iespējams saglabāt pat tad, ja mēs izmantojam long long int.
Piemēri:
Input : n = 1128 Output : No Input : n = 11216 Output : Yes Input : n = 1124273542764284287 Output : No
Tā kā ievades skaitlis var būt ļoti liels, mēs nevaram izmantot n % 16, lai pārbaudītu, vai skaitlis dalās ar 16, īpaši tādās valodās kā C/C++. Ideja ir balstīta uz sekojošu faktu.
visu lielo burtu saīsne Excel
A number is divisible by 16 if number formed by last four digits of it is divisible by 16.
Ilustrācija:
For example let us consider 769616 Number formed by last four digits = 9616 Since 9522 is divisible by 16 answer is YES.
Kā tas darbojas?
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>
Izvade:
No
Laika sarežģītība: O(1)
Palīgtelpa: O(1)
Cita pieeja (izmantojot UN bitu operatoru):
Lai pārbaudītu, vai liels skaitlis dalās ar 16 vai nē, neizmantojot modulo operatoru, mēs varam pārbaudīt skaitļa pēdējos 4 bitus. Ja visi šie biti ir 0, tad skaitlis dalās ar 16, pretējā gadījumā tas tā nav.
Tas ir tāpēc, ka 16 binārā veidā tiek attēlots kā 0b10000, kas nozīmē, ka tam ir 1 5. bita pozīcijā un visi 0 zemākajos 4 bitos. Tāpēc, ja skaitlis dalās ar 16, tā apakšējos 4 bitos ir jābūt visiem 0.
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana:
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'); }
Izvade
No
Laika sarežģītība: O(1)
Palīgtelpa: O(1)
cik daudz augļu tur ir
Šajā kodā mēs izmantojam bitu pagrieziena operatoru & ar bināro skaitli 0b1111 (kuram ir visi 1 apakšējos 4 bitos un 0 augšējos bitos), lai iegūtu pēdējos 4 bitus no ievades numura num. Pēc tam mēs pārbaudām, vai visi šie 4 biti ir 0 vai nē. Ja tie visi ir 0, funkcija atgriež True (tas nozīmē, ka skaitlis dalās ar 16), pretējā gadījumā tā atgriež False.