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
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;
}
1 Like
// this is the solution in vs cpp
#include “stdafx.h”
#include
#include<conio.h>
#include
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();
}
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");
}
}
}
for c
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#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);
}
}
most optimized and well explained solution waytocrack.com
1 Like
what are the constraints ??
If you have taken this question from another site, please mention the source.
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!
Here is the c/c++ code. Hope it helps
