logo

تأكد من أن العدد الكبير قابل للقسمة على 16 أم لا

عند إعطاء رقم، تكون المهمة هي التحقق مما إذا كان الرقم قابلاً للقسمة على 16 أم لا. قد يكون رقم الإدخال كبيرًا وقد لا يكون من الممكن تخزينه حتى لو استخدمنا عدد صحيح طويل.

أمثلة: 

Input : n = 1128 Output : No Input : n = 11216 Output : Yes Input : n = 1124273542764284287 Output : No

نظرًا لأن رقم الإدخال قد يكون كبيرًا جدًا، فلا يمكننا استخدام n % 16 للتحقق مما إذا كان الرقم قابلاً للقسمة على 16 أم لا خاصة في لغات مثل C/C++. وتستند الفكرة على الحقيقة التالية. 



Java int كسلسلة
A number is divisible by 16 if number formed by last four digits of it is divisible by 16.


توضيح:  

For example let us consider 769616 Number formed by last four digits = 9616 Since 9522 is divisible by 16 answer is YES.


كيف يعمل هذا؟  

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   using namespace std; // Function to find that // number divisible by 16 or not 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 int 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 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. 
Python3
# 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#
// 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
 // 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. ?> 
JavaScript
<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> 

الإخراج: 

No

تعقيد الوقت: يا(1)
المساحة المساعدة: يا(1)

نهج آخر (باستخدام عامل التشغيل AND):

للتحقق مما إذا كان عدد كبير قابل للقسمة على 16 أم لا دون استخدام عامل التشغيل modulo، يمكننا التحقق من آخر 4 بتات من الرقم. إذا كانت هذه البتات كلها أصفار فإن الرقم قابل للقسمة على 16 وإلا فهو ليس كذلك.

الرموز التعبيرية التفاح على الروبوت

وذلك لأن الرقم 16 يتم تمثيله بشكل ثنائي كـ 0b10000 مما يعني أنه يحتوي على 1 في موضع البت الخامس وجميع الأصفار في البتات الأربعة السفلية. لذلك، إذا كان الرقم قابلاً للقسمة على 16، فيجب أن يحتوي على جميع الأصفار في البتات الأربعة السفلية.

فيما يلي تنفيذ النهج أعلاه:

C++
#include    using namespace std; // Function to check if a number is divisible by 16 bool 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's num = 769528 if(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'); } 

الإخراج
No

تعقيد الوقت: O(1)

المساحة المساعدة: O(1)

في هذا الكود نستخدم عامل التشغيل AND والرقم الثنائي 0b1111 (الذي يحتوي على كل الأرقام 1 في البتات الأربع السفلية و0 في البتات العلوية) لاستخراج آخر 4 بتات من رقم الإدخال num. ثم نتحقق مما إذا كانت هذه البتات الأربع جميعها 0 أم لا. إذا كانت جميعها 0، فسترجع الدالة True (بمعنى أن الرقم قابل للقسمة على 16) وإلا فإنها ترجع False.


 

إنشاء اختبار