×

# Bleak Numbers

 0 Bleak Numbers In Mathematics each number has one special number, which it supports, chosen as follows. It counts the number of ones in its own binary representation, and adds this count to itself to obtain the value of the number it supports. That is, if j(m) means the number of ones in the binary representation of m, then m supports m+j(m). For example, the number eight (1000 in binary) supports nine, whereas nine supports eleven. However, in this way not all the numbers get supported; some are left without support, and we call these numbers bleak. For example since one supports two, two supports three and three supports five, there is no number less than four, which would support four, so four is bleak. Your task is for a given number recognize if it is bleak or supported by some number. How to solve this question asked 26 Oct '14, 22:00 3★shivhack 31●1●3 accept rate: 0% what are the constraints ?? (26 Oct '14, 22:08) If you have taken this question from another site, please mention the source. (26 Oct '14, 22:20) How does it make a difference where the question is taken from!! Constraints you can take say n<10^6 ,though i want the general solution! (26 Oct '14, 23:03) shivhack3★

 4 Brother, you'll get your answer here : http://www.careercup.com/question?id=5661070769258496 answered 28 Oct '14, 20:17 2.9k●31●53 accept rate: 9%
 1 Suppose you have a number 'm' and it is supported by another number say 'n'. We know n < m. Therefore, the maximum number of set bits in the binary representation of 'n' will be log2(m). (Logarithm of 'm' w.r.t. base 2). For each i, (1 <= i <= log2(m)), check if number of set bits in (m-i) is equal to 'i'. If this is true for any i, then the number m is not bleak, as it will be supported by (m-i), otherwise it is bleak. Time complexity: O(k^2), where k is the size of input, that is, log2(m). So, now, we have a polynomial time algorithm to determine if a number is bleak. Sample code in C++. You can easily extend this for "big" numbers, if needed. bool isBleak(int m) { int k = __builtin_popcount(m); for(int i=1; i<=k; i++) { if(__builtin_popcount(m-i) == i) return false; } return true; }  answered 28 Oct '14, 19:42 221●3●4 accept rate: 27%
 1 most optimized and well explained solution http://www.waytocrack.com/blog/how-to-check-if-a-number-is-bleak-or-supported-number/ answered 23 Jul '17, 12:18 1★anu1234 114●3●10●18 accept rate: 0%

// this is the solution in vs cpp

# include <bitset>

using namespace std; int main() { int i,j; int size; cin>>size; int *arr=new int[size]; for(i=0;i<size;i++) {="" cin="">>arr[i]; } for(i=0;i<size;i++) {="" bitset<32="">a=arr[i]; bitset<32>b=1; int b_deci=b.to_ulong(); int flag=0; for(j=0;b_deci<=arr[i];j++) { if(b_deci==arr[i]) { flag=1; cout<<"SUPPORTED"; break; } else { b_deci+=b.count(); b=b_deci; } } if(flag==0) { cout<<"BLEAK"; } } _getch(); }

1
accept rate: 0%

 0 Full Solution in Java public class BleakNumber{ int convert(int decimal) { int result = 0; int multiplier = 1; int count =0; while(decimal > 0) { int residue = decimal % 2; if(residue==1) count++; decimal = decimal / 2; result = result + residue * multiplier; multiplier = multiplier * 10; } return count; } boolean isBleak(int m) { int k = convert(m); for(int i=1; i<=k; i++) { if(convert(m-i) == i) return false; } return true; } public static void main(String args[]) { MinMax conv = new MinMax(); boolean x=conv.isBleak(4); if(x){ System.out.println("Number is Bleak"); }else{ System.out.println("Supported by some number"); } }  } answered 19 Sep '15, 23:35 1 accept rate: 0%

for c

# define sz 10

int bin( ); int check(int,int );

int main() { int i; bin(); return 0; } int bin( ) { int gn,i;

scanf("%d",&gn);

if(gn==1||gn==0)
{
printf("Bleak!");
exit(0);
}

for(i=1;i<gn;i++)
{
check(i,gn);
}
return 0;


} int check(int gn,int chk) { int i=0,j=0,gn1,gn2; int bn[sz]; gn1=gn; gn2=gn;

while(gn!=0)
{
bn[i]=gn%2;
gn=gn/2;
i++;
j=i;
}
for(i=0;i<j;i++)
{
gn1=gn1+bn[i];
}
if(gn1==chk)
{
printf("Supported\n");
exit(0);
}
else if(gn2+1==chk)
{
printf("Bleak!");
exit(0);
}


}

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×4

question asked: 26 Oct '14, 22:00

question was seen: 14,359 times

last updated: 23 Jul '17, 12:18