You are not logged in. Please login at www.codechef.com to post your questions!

×

Bleak Numbers

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

shivhack's gravatar image

3★shivhack
3113
accept rate: 0%

what are the constraints ??

(26 Oct '14, 22:08) neo1tech9_76★

If you have taken this question from another site, please mention the source.

(26 Oct '14, 22:20) nisargshah953★

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★

Brother, you'll get your answer here : http://www.careercup.com/question?id=5661070769258496

link

answered 28 Oct '14, 20:17

topcoder_7's gravatar image

2★topcoder_7
2.9k3153
accept rate: 9%

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;
}
link

answered 28 Oct '14, 19:42

aakashc31's gravatar image

4★aakashc31
22134
accept rate: 27%

link

answered 23 Jul '17, 12:18

anu1234's gravatar image

1★anu1234
11431018
accept rate: 0%

// this is the solution in vs cpp

include "stdafx.h"

include<iostream>

include<conio.h>

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(); }

link

answered 07 Nov '14, 01:19

decoder01's gravatar image

2★decoder01
1
accept rate: 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");
    }
}

}

link

answered 19 Sep '15, 23:35

sabah_khanam's gravatar image

0★sabah_khanam
1
accept rate: 0%

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);
}

}

link

answered 18 Feb '16, 02:50

chf_shuvo's gravatar image

0★chf_shuvo
1
accept rate: 0%

edited 18 Feb '16, 02:52

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Related questions