หมายเลขก่อนหน้าเหมือนกับส่วนเสริมของ 1 ใน C++

ในปัญหานี้ เราได้รับจำนวนเต็ม n หน้าที่ของเราคือตรวจสอบสภาพอากาศว่าตัวเลขก่อนหน้านั้นเท่ากับส่วนเติมเต็มของตัวเลข 1

มาดูตัวอย่างกันเพื่อทำความเข้าใจปัญหาของเรา

Input: 12
Output: No
Explanation: (12)10 = (1100)2
Preceding number 11 = (1011)2
1’s complement of 12 = (0011)2
Input: 4
Output: Yes
Explanation: 4 = (100)2
Preceding number 3 = (011)2
1’s complement of 12 = (011)2

ในการแก้ปัญหานี้ เราสามารถใช้วิธีง่ายๆ โดยการเปรียบเทียบตัวเลขก่อนหน้ากับส่วนเสริมของตัวเลข 1

วิธีการนี้เรียบง่ายแต่กินพื้นที่และเวลา ความซับซ้อนของเวลา:O(n)

วิธีแก้ปัญหาที่มีประสิทธิภาพอาจใช้วิธีการทั่วไปที่เราพยายามแก้ปัญหา ในที่นี้ เฉพาะเลขยกกำลัง 2 เท่านั้นที่จะเป็นไปตามเงื่อนไข กล่าวคือ จำนวนก่อนหน้าจะเท่ากับส่วนเติมเต็มของ 1

โปรแกรมแสดงการใช้งานโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;
bool sameBits(unsigned long int n){
   if ((n & (n - 1)) == 0)
      return true;
   return false;
}
int main(){
   unsigned long int n = 64;
   if(sameBits(n))
      cout<<"Both are the same";
   else
      cout<<"Both aren't the same";
   return 0;
}

ผลลัพธ์

Both are the same