دو کی طاقت


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایپل
بٹ بٹ ہیرا پھیری بٹس ریاضی

In دو کی طاقت مسئلہ جو ہم نے ایک عدد دیا ہے ، چیک کریں کہ آیا یہ 2 کی طاقت ہے یا نہیں۔ دو کی طاقت میں ایک عدد اگر اس میں صرف ایک سیٹ ہے بٹ بائنری نمائندگی میں. آئیے ایک نمبر کی ایک مثال دیکھیں جس میں صرف ایک سیٹ سا ہوتا ہے۔ اگر ہمارا ان پٹ 16 ہے تو ہم اسے 10000 جیسے بائنری فارمیٹ میں نمائندگی کرسکتے ہیں۔ یہاں ہم دیکھتے ہیں کہ صرف ایک سا 1 ہے جس کا مطلب ہے نمبر 2 کی طاقت میں نمائندگی کرتا ہے۔ اب ایک مثال دیکھیں جس میں سیٹ بٹ 1 سے زیادہ ہے۔ اگر ہمارا ان پٹ 13 ہے تو ہم 1101 جیسے بائنری فارمیٹ میں اس کی نمائندگی کرتے ہیں۔ یہاں ہم دیکھتے ہیں کہ 3 سیٹ بٹس موجود ہیں۔ لہذا ہم اس کی نمائندگی 2 ^ y کی شکل میں نہیں کرسکتے ہیں جہاں y ایک ہے عددی 0 سے زیادہ

ان پٹ فارمیٹ

پہلی سطر جس میں عددی قیمت N ہو۔

آؤٹ پٹ کی شکل

"سچ" پرنٹ کریں اگر ہم کسی مخصوص شکل میں اس کی نمائندگی کرتے ہیں ورنہ "غلط" پرنٹ کریں۔

رکاوٹوں

  • 1 <= N <= 10 ^ 18۔

نمونہ ان پٹ

4

نمونہ آؤٹ پٹ 

سچ

وضاحت

ہم جانتے ہیں کہ پہلے ہی 4 کی بائنری نمائندگی 100 ہے جس کا مطلب ہے یہاں صرف ایک سیٹ بٹ۔ لہذا ہم شکل 2 ^ y (2 ^ 2) میں اس کی نمائندگی کرتے ہیں۔

Iterative نقطہ نظر 

  • منفی تعداد اور صفر کبھی بھی شکل 2 ^ y میں نہیں ہوسکتے ہیں جہاں y ایک عدد عدد ہوتا ہے۔
  • چیک کریں کہ n کو 2 سے تقسیم کیا جاسکتا ہے۔ اگر ہاں ، تو n کو 2 سے تقسیم کریں اور بار بار چیک کریں۔
  • اگر آخر میں ن 1 کو کم کر دیا گیا ہے تو n 2 کی طاقت ہے ورنہ یہ شکل 2 ^ y نہیں ہے جہاں y ایک عدد صحیح ہے۔

عمل

سی ++ پروگرام برائے پاور

#include <bits/stdc++.h>
using namespace std;
bool isPowerOfTwo(int n) {
  if (n <= 0) return false;
  while (n%2 == 0) n/=2;
  return n == 1;
}
int main()
{   
  int n=4;
  int ans=isPowerOfTwo(n);
  if(ans)
  cout<<"true"<<endl;
  else
  cout<<"false"<<endl;
    return 0;
}

آؤٹ پٹ

true

جاوا پروگرام برائے دو پاور

public boolean isPowerOfTwo(int n) {
  if (n <= 0) return false;
  while (n%2 == 0) n/=2;
  return n == 1;
}

وقت کی پیچیدگی

O (log n) کیونکہ ہر قدم پر ہم تعداد کو 2 سے تقسیم کر رہے ہیں۔

بٹ آپریشن نقطہ نظر

  • منفی تعداد اور صفر کبھی بھی 2 کی طاقت نہیں ہوسکتے ہیں۔
  •  اگر ایک نمبر 2 کی طاقت ہے تو (n & (n-1)) == 0

دو کی طاقت

عمل

سی ++ پروگرام برائے پاور

#include <bits/stdc++.h>
using namespace std;
bool isPowerOfTwo(int n) {
return (n > 0 && (n & (n-1)) == 0); 
}
int main()
{   
  int n=4;
  int ans=isPowerOfTwo(n);
  if(ans)
  cout<<"true"<<endl;
  else
  cout<<"false"<<endl;
    return 0;
}

آؤٹ پٹ

true

جاوا پروگرام برائے دو پاور

 public boolean isPowerOfTwo(int n) {
    return (n>0&&(n & (n-1))==0);
}

وقت کی پیچیدگی

O (1) کیونکہ صرف ایک اور کا استعمال کرتے ہوئے ہم یہ تلاش کرسکتے ہیں کہ نمبر شرط کو پورا کرتا ہے یا نہیں۔

حوالہ جات