Sap Labs Interview Question Software Engineer / Developers
Country: India
Main idea is to check if number can be represented in form of Sum(2^k+1) for some k's:
static bool IsBleak(int m)
{
int len = 0; // number length in binary form enougth to represent n;
while ((1 << len) + len < m) len++;
for (int i = len; i >= 0; i--) if (m >= (1 << i) + 1) m -= (1 << i) + 1;
return m != 0;
}
Care you share the math behind Sum(2^k+1). If you mean 2^k+1 the 4 which is bleak does not fit. if you mean 2^(k+1) then 6 which is bleak does not fit. How about ensuring mathematical correctness before reducing complexity
Suppose we are checking number "M" for weakness.
Number M is supported if there is some number N, such that N + numOfOneBits(N) = M.
Let's look at binary representation of N.
N = Sum(Ni * 2^i) for i in 0..length(N)
numOfOneBits(N) = Sum(Ni * 1) for i in 0..length(N)
After grouping corresponding terms, we get
M = N + numOfOneBits(N) = Sum(Ni * 2^i + Ni * 1) for i in 0..length(N)
M = Sum(Ni * (2^i + 1)) for i in 0..length(N)
So, if M is representable in such way, it is supported number. Any questions?
Also, you said "If you mean 2^k+1 the 4 which is bleak does not fit". Have you even run the code before commenting?
@FLux:
2^1 + 1 + 2^1 + 1 = 6, which you claim is not bleak, but it is bleak.
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
4 + 1 = 5
5 + 2 = 7
Why the F**K should one run wrong code, when it is plainly there to see that your claim is wrong.
Can you look at formula
M = Sum(Ni * (2^i + 1)) for i in 0..length(N)
and see that you CAN NOT represent 6 in such way? In your example, you count 2^1 + 1 TWICE, when it is obvious can be counted 1 or 0 times, because Ni is i-th digit in binary representation of N.
And if you will run my "wrong" code you'll see that output for 6 is TRUE.
@Flux: You should clarify the uniqueness of 2^k+1 in your first statement (i.e. Ni is 0 or 1). People tend not to read fully. The first sentence is important.
You are still making an assumption, though: that the greedy picking of 2^i + 1 (starting from the largest i) will give you such a representation if it exists (and will allow you to say none if not).
Do you have a proof that this works?
Well done, though. Nice solution, looks promising.
Yes, this works. Good job flux.
The greedy algorithm works. Subset sum for Superincreasing sums can be solved by the greedy algorithm, starting with the largest.
Super increasing means s(k) > s(1) + s(2) + ... + s(k-1) for each k.
where s(1), s(2), ..., s(n) are the integers in the input array for subset sum.
s(i) = 2^(i-1) + 1 is our case, and is super increasing.
@Flux: Your algorithm incorrectly classifies as bleak some non-bleak cases like
m = 10 = (111) + 3, m = 34 = (11110) + 4, etc.
For example, classifying a non-bleak number
m = 10 = (111) + 3 = 2^2 + 2^1 +2^0 + 3 = 2^3 + 2
results in len = 3 and a decomposition into
m = m - (2^3 + 1) = 1 => bleak=true
instead of
m = m - (2^2 + 1) = 5;
m = m - (2^1 + 1) = 2;
m = m - (2^0 + 1) = 0 => bleak=false
A simple modification of the algorithm works correctly in all cases. It is based on the following inequality for a non-bleak numbers 'm' given the binary length 'len' of its corresponding supporting number:
2^(len-1) + 1 <= m <= 2^len + len -1.
Based this inequality, one can modify the code to attempt decomposition into (2^k+1) terms with the initial "for" loop settings of both len-1 and len:
static bool IsBleak(int m)
{
int len = 0; // number length in binary form enough to represent n;
int d; // holds the remainder during decomposition into (2^k+1) terms
while ((1 << len) + len < m) len++;
d = m; // set the remainder
for (int i = len-1; i >= 0; i--) if (d >= (1 << i) + 1) {d-= (1 << i) + 1; if (d== 0) return false;}
d = m; // reset the remainder
for (int i = len; i >= 0; i--) if (d >= (1 << i) + 1) {d -= (1 << i) + 1; if (d== 0) return false;}
return true;
}
One can factor out the code for the "for" loop into a function:
int decompose (int number, int length) {
ind d = number;
for (int i = length; i >= 0; i--) if (d >= (1 << i) + 1) {d -= (1 << i) + 1; if (d== 0) return d;}
return d;
}
static bool IsBleak(int m)
{
int len = 0; // number length in binary form enough to represent n;
while ((1 << len) + len < m) len++;
(0 == decompose(m, len-1)) return false;
(0 == decompose(m, len)) return false;
return true;
unsigned int isWeak(unsigned int n)
{
unsigned bitsInNum=0;
unsigned tmp=n;
while(tmp)
{
bitsInNum++;
tmp=tmp>>1;
}
printf("Bits in num =%d \n",bitsInNum);
for(unsigned int k=n-bitsInNum ; k<n ; k++ )
{
unsigned setBits=0;
for(unsigned int i=0;i<32;i++)
{
if((k>>i)&1){setBits++;}
}
if ((k+setBits)==n)
{ printf("STRONG NUMBER , NUMBER =%u Setbits= %u , Sum =%u ",k , setBits,(k+setBits) ); return 0 ;}
}
printf("WEAK NUMBER \n");
return 1;
}
package com.careercup;
public class CC5661070769258496 {
int msbValue = 1 << 30;
/**
* return false if bleak
*/
public boolean isNotBleak(int n){
int msbPos = msbPosition(n);
System.out.print(" n:"+n);
System.out.print(" bits:");printBitPosition(n);
System.out.print(" msbPos:"+msbPos);
if(msbPos>=0)
for(int i=n-msbPos;i<n;i++){
if(countOfOnes(i)+i==n){
System.out.print(" result:"+i);
return true;
}
}
return false;
}
/**
*
* @param num
* @return count of 1s
*/
private int countOfOnes(int num) {
int countOfOnes=0;
for(int i=0;i<Integer.SIZE;i++){
countOfOnes+=((num>>i) & 1);
}
return countOfOnes;
}
/**
*
* @param n
* @return most significant bit position
*/
public int msbPosition(int n){
for(int i=0;i<Integer.SIZE;i++){
if(((n<<i) & msbValue)==msbValue)
return Integer.SIZE-1-i;
}
return -1;
}
public void printBitPosition(int n){
for(int i=0;i<Integer.SIZE-1;i++){
System.out.print(((n<<i) & msbValue)==msbValue?1:0);
}
}
public static void main(String[] args){
System.out.println(new CC5661070769258496().isNotBleak(4));
System.out.println(new CC5661070769258496().isNotBleak(8));
System.out.println(new CC5661070769258496().isNotBleak(7));
System.out.println(new CC5661070769258496().isNotBleak(54));
System.out.println(new CC5661070769258496().isNotBleak(12));
System.out.println(new CC5661070769258496().isNotBleak(1073741824));
System.out.println(new CC5661070769258496().isNotBleak(-1));
System.out.println(new CC5661070769258496().isNotBleak(-100));
}
}
class p1
{
p1()
{
}
public int the_num(int num)
{
int div,rem,count=0,newnum=num;
char[] ch;
String n="";
do
{
rem=num%2;
n=rem+n+"";
num=num/2;
if(num==1)
n="1"+n;
}while(num>1);
//System.out.println(n);
ch=n.toCharArray();
for(int i=0;i<ch.length;i++)
{
if(ch[i]=='1')
count++;
}
newnum=newnum+count;
return newnum;
}
public String do_supports(int num)
{
for(int i=1;i<num;i++)
{
int n=the_num(i);
if(n==num)
return "Supported by"+i;
}
return "Bleak";
}
public static void main(String...ar)
{
p1 p=new p1();
System.out.print(p.do_supports(Integer.parseInt(ar[0])));
}
}
Please find the code as below and its working for any number.
public class BleakOrSupprt {
static int numberOf1sBits(int n){
int count = 0;
while(n>0){
count++;
n&=(n-1);
}
return count;
}
public static void main(String[] args) {
int number = 10;
int i = 1;
while(true){
int supporter = number-i;
int count = numberOf1sBits(supporter);
System.out.println(count);
i++;
if((count+ supporter) == number){
System.out.println("Supported number is :"+supporter);
break;
}
if((count+ supporter) < number){
System.out.println("Bleak number");
break;
}
}
}
}
public class NumberPlay {
public static boolean isBleak(Long l) {
String binary = Long.toBinaryString(l);
int bitLength = binary.length();
for (long i = l - bitLength - 1; i <= l; i++) {
String bin = Long.toBinaryString(i);
int count = 0;
for (int j = 0; j < bin.length(); j++) {
if (bin.charAt(j) == '1') {
count++;
}
}
if (count + i == l) {
//System.out.println("Supported by " + i);
return true;
}
}
return false;
}
public static void main(String args[]) {
System.out.println(isBleak(9l));
System.out.println(isBleak(10l));
System.out.println(isBleak(11l));
System.out.println(isBleak(12l));
System.out.println(isBleak(13l));
System.out.println(isBleak(14l));
System.out.println(isBleak(15l));
System.out.println(isBleak(16l));
System.out.println(isBleak(17l));
}
}
import java.util.Scanner;
public class Bleak {
/**
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.
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
while(true){
System.out.println("Enter Num");
Scanner scanner = new Scanner(System.in);
int val=scanner.nextInt();
System.out.println(isBleak(val,0,val));
System.out.println("-------------------------------");
}
}
static int supppoertedValue(int inputVal){
System.out.println(Integer.toBinaryString(148).replace("0", "").length()+148);
return Integer.toBinaryString(inputVal).replace("0", "").length()+inputVal;
}
static boolean isBleak(int high,int low,final int value){
int med=(high+low)/2;
boolean bool=false;
while (med <= high-1 && low<high-1) {
med=(high+low)/2;
int val=supppoertedValue(med);
System.out.println(" high:"+high+" low:"+low+" med:"+med+" val:"+val+"=="+value);
if (val==value) {
bool= true;
break;
}
if(val<value){
low= med;
}else if(val>value){
high=med;
}
}
return bool;
}
}
int output1[] // we write our ans into this
int setbits(int n) // new func we make
{
int res = 0;
if(n < 0)
return -999;
while(n > 0)
{
if(n&0001)
res++;
n = n >> 1;
}
return res;
}
bleaknumbers(int input1[]) // this method will be there in code window they //provide
{
int t = input1[0];
int num, mj;
int i, flag =0;
i = 1;
while(t>0)
{
num = input1[i];
flag = 0;
for(int j = 1; j <num;++j )
{
mj = setbits(j);
if(mj== -999)
{ flag = 2; break;}
else if ((mj+j) == num)
{ flag =1; break;}
}
if(flag ==1)
output1[i-1] = "SUPPORTED";
else if( flag ==0)
output1[i-1] = "BLEAK";
else
output1[i-1] = mj;
}
}
int output1[] // we write our ans into this
int setbits(int n) // new func we make
{
int res = 0;
if(n < 0)
return -999;
while(n > 0)
{
if(n&0001)
res++;
n = n >> 1;
}
return res;
}
bleaknumbers(int input1[]) // this method will be there in code window they //provide
{
int t = input1[0];
int num, mj;
int i, flag =0;
i = 1;
while(t>0)
{
num = input1[i];
flag = 0;
for(int j = 1; j <num;++j )
{
mj = setbits(j);
if(mj== -999)
{ flag = 2; break;}
else if ((mj+j) == num)
{ flag =1; break;}
}
if(flag ==1)
output1[i-1] = "SUPPORTED";
else if( flag ==0)
output1[i-1] = "BLEAK";
else
output1[i-1] = mj;
}
}
check whether 'n' is bleak or supported?
int bin(int a){
int s=1,q=0,rem=0,count=0;
while(a>0){
rem=a%2;
if(rem==1){count++;}
q=q+rem*s;
s=s*10;
a=a/2;
}
return count;
}
void main(){
int f=0;
for(i=1;i<n;i++)
{k=i+bin(i);
if(k==n){
f=1;break;}
}
if(f==0){
printf("Bleak Number");
}
else{
printf("Supported");
}
import java.util.Scanner;
public class Bleak {
/**
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.
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
while(true){
System.out.println("Enter Num");
Scanner scanner = new Scanner(System.in);
int val=scanner.nextInt();
System.out.println(isBleak(val,0,val));
System.out.println("-------------------------------");
}
}
static int supppoertedValue(int inputVal){
System.out.println(Integer.toBinaryString(148).replace("0", "").length()+148);
return Integer.toBinaryString(inputVal).replace("0", "").length()+inputVal;
}
static boolean isBleak(int high,int low,final int value){
int med=(high+low)/2;
boolean bool=false;
while (med <= high-1 && low<high-1) {
med=(high+low)/2;
int val=supppoertedValue(med);
System.out.println(" high:"+high+" low:"+low+" med:"+med+" val:"+val+"=="+value);
if (val==value) {
bool= true;
break;
}
if(val<value){
low= med;
}else if(val>value){
high=med;
}
}
return bool;
}
}
How about brute force.??
public class BleakNumber {
public static void main(String[] args) {
// TODO Auto-generated method stub
int number = 10;
int counter = 0;
boolean is_bleak = true;
for (int i = 1; i < number - 1; i++) {
counter = 0;
String s = Integer.toBinaryString(i);
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == '1')
counter++;
}
if (i + counter == number) {
System.out.println("Not bleak");
is_bleak = false;
break;
}
}
if (is_bleak) {
System.out.println("Bleak");
}}}
- Anonymous June 16, 2014