大きな数が 16 で割り切れるかどうかを確認します

与えられた数値が 16 で割り切れるかどうかを確認するタスクです。入力数値が大きく、long long intを使っても格納できない場合があります。

例:

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

入力数値が非常に大きい可能性があるため、特に C/C++ などの言語では、数値が 16 で割り切れるかどうかを確認するために n % 16 を使用することはできません。この考えは次の事実に基づいています。

ストラセプ

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# 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 で割り切れるかどうかを確認するには、数値の最後の 4 ビットをチェックします。これらのビットがすべて 0 の場合、その数値は 16 で割り切れますが、それ以外の場合は割り切れません。

これは、16 が 2 進数で 0b10000 として表されるためです。これは、5 番目のビット位置に 1 があり、下位 4 ビットにすべて 0 があることを意味します。したがって、数値が 16 で割り切れる場合は、下位 4 ビットがすべて 0 でなければなりません。

上記のアプローチの実装を以下に示します。

Javaユーザー入力

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')

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 演算子 & と 2 進数 0b1111 (下位 4 ビットがすべて 1、上位ビットが 0 である) を使用して、入力数値 num の最後の 4 ビットを抽出します。次に、これらの 4 ビットがすべて 0 であるかどうかを確認します。それらがすべて 0 の場合、関数は True (数値が 16 で割り切れるという意味) を返し、それ以外の場合は False を返します。

クイズの作成