## Sap Labs Interview Question for Software Engineer / Developers

Country: India

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def isBleak(m):
for x in range(1, number_of_bits(m)):
if x + number_of_set_bits(x) == m:
return False
return True``````

Comment hidden because of low score. Click to expand.
0

O(log^2 m) time algorithm.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Brute force?

Comment hidden because of low score. Click to expand.
0

I believe there is a "mental typo" in the above:

``````def isBleak(m):
for x in range(1, number_of_bits(m)):
if number_of_bits(m-x) == x:
return True
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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

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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;

}``````

Comment hidden because of low score. Click to expand.
0

This is O(log(n)^2) algo. You can do it in O(log(n)), as I described above.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Tested this code with some inputs and is working as expected.
Logic is to determine how many bits are required to represent the given input number.
We are testing only form (n-bits required to represent n ) to n

Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess this is more correct:
def isBleak(m):
for x in range(1, m):
if x + number_of_set_bits(x) == m:
return False
return True

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def count_ones(x):
return sum((int(y) for y in bin(x) if y == '1'))

def is_bleak(n):
for each in range(n):
if each + count_ones(each) == n:
print "%s is supported by %s"%(n,each)
return False
return True``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

``````Output is :
true
true
true
true
false
true
false
true
true``````

Comment hidden because of low score. Click to expand.
0

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;

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
int main()
{
int n,c,i;
scanf("%d",&n);

for (i = 1; i <= n; i++)
{
c = count(i);
if ((c+i) == n)
{
printf("Not Bleak\n");
break;
}
}

if(i>=n)
printf("Bleak\n");

return 0;
}
int count(int n)
{
int i=0;
while(n!=0)
{
if(n%2==1)
i++;
n = n/2;
}
return i;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

{n=int(raw_input("Enter number: "))
def is_bleak(n):
for each in range(n):
c=bin(each).count("1")
res=each+c
if res == n:
print "%s is supported by %s"%(n,each)
return False
return True
B=is_bleak(n)

if B==True:
print "number is bleak"}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.