神刀安全网

Check if a number is Bleak

A number ‘n’ is called Bleak number if it cannot be represented as sum of a positive number x and set bit count in x, i.e., x +countSetBits(x) is not equal to n for any non-negative number x.

Examples :

Input : n = 3 Output : false 3 is not Bleak as it can be represented as 2 + countSetBits(2) which is 2 + 1.  Input : n = 4 Output : true 4 is t Bleak as it cannot be represented  as sum of a number x and countSetBits(x) for any number x.

Source : SAP Lab Interview

We strongly recommend you to minimize your browser and try this yourself first.

Below is one simple solution.

bool isBleak(n) 1) Consider all numbers smaller than n     a) If x + countSetBits(x) == n            return false  2) Return true

Below is C++ implementation of the simple approach.

// C++ program to find if a number is Bleak #include <bits/stdc++.h> using namespace std;  /* Function to get no of set bits in binary    representation of passed binary no. */ int countSetBits(int x) {     unsigned int count = 0;     while (x)     {       x &= (x-1) ;       count++;     }     return count; }  // Returns true if n is Bleak bool isBleak(int n) {    // Check for all numbers 'x' smaller    // than n.  If x + countSetBits(x)    // becomes n, then n can't be Bleak    for (int x=1; x<n; x++)       if (x + countSetBits(x) == n)           return false;     return true; }  // Driver code int main() {   isBleak(3)? cout << "Yes/n" : cout << "No/n";   isBleak(4)? cout << "Yes/n" : cout << "No/n";   return 0; }

Output :

No Yes

Time complexity of above solution is O(n Log n). Can there be a better solution, please comment.

This article is contributed by Rahul Jain . Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Check if a number is Bleak

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址