Bir sayı verildiğinde görev, sayının 16'ya bölünebilir olup olmadığını kontrol etmektir. Girilen sayı büyük olabilir ve long long int kullansak bile saklamak mümkün olmayabilir.
Örnekler:
Input : n = 1128 Output : No Input : n = 11216 Output : Yes Input : n = 1124273542764284287 Output : No
Girilen sayı çok büyük olabileceğinden, özellikle C/C++ gibi dillerde bir sayının 16'ya bölünüp bölünmediğini kontrol etmek için n % 16'yı kullanamayız. Fikir aşağıdaki gerçeğe dayanmaktadır.
java çoklu iş parçacığı
A number is divisible by 16 if number formed by last four digits of it is divisible by 16.
İllüstrasyon:
For example let us consider 769616 Number formed by last four digits = 9616 Since 9522 is divisible by 16 answer is YES.
Bu nasıl çalışır?
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>
Çıkış:
No
Zaman Karmaşıklığı: Ç(1)
Yardımcı Alan: Ç(1)
Başka Bir Yaklaşım (AND bitsel Operatörünü Kullanarak):
Büyük bir sayının 16'ya bölünüp bölünemediğini modülo operatörünü kullanmadan kontrol etmek için sayının son 4 bitini kontrol edebiliriz. Bu bitlerin tümü 0 ise sayı 16'ya bölünebilir, aksi halde bölünemez.
Bunun nedeni, 16'nın ikili olarak 0b10000 olarak temsil edilmesidir; bu, 5. bit konumunda 1'e ve alt 4 bitte tüm 0'lara sahip olduğu anlamına gelir. Bu nedenle, eğer bir sayı 16'ya bölünebiliyorsa, alt 4 bitteki tüm 0'ların da olması gerekir.
Aşağıda yukarıdaki yaklaşımın uygulanması yer almaktadır:
c dizisindeki dizeC++
#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'); }
Çıkış
No
Zaman Karmaşıklığı: O(1)
Yardımcı Alan: O(1)
Bu kodda, giriş numarası num'un son 4 bitini çıkarmak için 0b1111 ikili numarasıyla (alt 4 bitte tüm 1'ler ve üst bitlerde 0'lar bulunur) bit düzeyinde AND operatörünü & kullanırız. Daha sonra bu 4 bitin tamamının 0 olup olmadığını kontrol ediyoruz. Bunların hepsi 0 ise işlev True değerini döndürür (yani sayı 16'ya bölünebilir), aksi halde False değerini döndürür.