Country: India
Interview Type: In-Person

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

One can make the following observation:

printing for k

is equivalent to

print all combinations of length k with 0 ones
print all combinations of length k with 1 ones
...
print all combinations of length k with k ones

A second observation is:

print all combinations of length k with n ones

is equivalent to
print (prepend 0 to all combinations of length k-1 with n ones)
print (prepend 1 to all combinations of length k-1 with n-1 ones)

This way we get a recursive function where we can cache intermediary results.
This is obviously more space inefficient than just generating all bit combinations and sorting them in place. Can anyone help me out with runtime analysis and tell me if it's faster?

Python class:

``````class KBitGenerator:

cache = {}

def generate(self, k):
result = []
for i in range(k + 1):
result += self.generate_for_num(k, i)
return result

def generate_for_num(self, length, num_ones):
if (length, num_ones) in self.cache:
return self.cache[(length, num_ones)]
result = []
if num_ones == 0:
result = [[0] * length]
elif length == num_ones:
result = [[1] * length]
else:
for pattern in self.generate_for_num(length - 1, num_ones):
result.append([0] + pattern)
for pattern in self.generate_for_num(length - 1, num_ones - 1):
result.append([1] + pattern)
self.cache[(length, num_ones)] = result
return result``````

Comment hidden because of low score. Click to expand.
1
of 3 vote

here is a simple solution in C++:

``````#include <iostream>
#include <vector>

int bitcount(int aArg) {
int c = 0; // bit count
for(; aArg; c++)
aArg &= aArg -1; // clears the least significat bit

return c;
}

void printBitCombinations(int K) {
std::vector<int> A;

for(int i = 0; i <= K; ++i) {
for(int j = 0; j < 1 << K; ++j) {
if(bitcount(j) == i)
A.push_back(j);
}
}

for(auto& a : A) {
std::cout << a << std::endl;
}
}

int
main() {

printBitCombinations(4);

return 0;
}``````

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

First, I think that your sample output is inconsistent to your description of the problem. If two numbers with the same set bits are supposed to be sorted from low to high value, then it should be:

000, 001, 010, 100, 011, 101, 110, 111 (note that 011 should come before 101).

With that said, I took two approaches. The first, naive approach used the Cartesian product of '01' repeated k times. The resulting list is in ascending order. I then sorted it the list by the number of 1 bits in each number.

``````def bins_product(k):
import itertools
bits = [''.join(b) for b in itertools.product('01', repeat=k)]
bits.sort(key = lambda x: x.count('1'))
for x in bits: print x``````

But that's slow. I'm not even sure what the time complexity is of that code. So, my second sweep was to actually just count in binary up to the 2^k, and then perform the same sort:

``````def bins_count(k):
bits = []
b = 0
while b < 2**k:
bits.append(bin(b)[2:].zfill(k))
b += 1
bits.sort(key = lambda x: x.count('1'))
for x in bits: print x``````

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

Here is an O(1) per number algorithm that outputs these numbers in requested order.
If we can assume that k is <= 64, or we can use python long arithmetic, then we can use "gosper hack". This obviously works in O(1) per number, so the whole algorithm works in O(t) where t is number of items we want to print (e.g. 2^k to print everything)

``````def gosper(n):
"""return smallest number > n with the same number of bits set"""
# group is first sequence of 1's in n starting from lowest bits
# 000111110000
#    ^---^ - this is "group"

# the idea is simple - take the highest bit in group
# and move it one position left
# the rest of the group will go to the right
# like this:

# 000111110000
# turns into
# 001000001111
# after another iteration this turns into
# 001000010111
# and so forth...

# lowest_set_bit is the lowest 1 in that group
# 000111110000
#        ^ here it is
lowest_set_bit = ((~n) + 1) & n

# this points straight before the highest bit
# 0001110000
#   ^ here - to the 0
new_group_head = (lowest_set_bit + n) & (~n)

# now let's work with what was left on the left
original_group = n & (new_group_head - 1)
# remove group old head - it has migrated one bit left
new_group = original_group ^ (new_group_head / 2)
# move the tail to the beginning
new_group /= lowest_set_bit

# reassemble result
result = n & ~original_group
result |= new_group

assert result > n
assert bin(result).count('1') == bin(n).count('1')
return result

def all_combinations(k):
yield '0' * k
mask = (1 << k) - 1
for num_bits in xrange(1, k + 1):
n = (1 << num_bits) - 1
while True:
yield bin(n)[2:].rjust(k, '0')
n = gosper(n)
break

k = 5
result = list(all_combinations(k))
print len(result)
assert len(result) == 2 ** k
assert result[-1] == '1' * k

for s in all_combinations(5):
print s``````

Example output: ideone.com/FO329N

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

``````def getBits(n):
lim = pow(2,n)
opt = {}
for i in range(0,lim):
temp = bin(i)
#print temp[temp.index('b')+ 1:]
temp_int =  int(temp[temp.index('b') + 1:])
#print y
y = temp_int
sum = 0
while y > 0:
sum += y % 10
y = y / 10

#print temp_int, sum
val = []
if sum in opt.keys():
val = opt[sum]

val.append(temp_int)
opt[sum] = val

for key in opt.keys():
print key,
for item in opt[key]:
print item,
print

getBits(5)``````

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

``````public static void driver(int k) {
for(int i = 0; i<=k;i++) {
print1s(k,i,new StringBuilder());
}
}

public static void print1s(int k, int ones, StringBuilder prefix) {
if(ones == 0) {
for(int i = 0; i<k; i++)prefix.append('0');
System.out.println(prefix);

prefix.delete(prefix.length()-k,prefix.length());
return;
}

for(int i = k-ones; i>=0; i--) {
for(int j = 0;j<i;j++)prefix.append('0');
prefix.append('1');
print1s(k-(i+1),ones-1,prefix);

prefix.delete(prefix.length()-1-i,prefix.length());
}

}``````

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

package com.career.cup;

import java.util.Arrays;

public class BinaryCodeGenerator {

public static String binary(int data)
{
int r;
StringBuffer s=new StringBuffer();
while(data!=0)
{
r=data%2;
data=data/2;
s=s.append(r);

}

return s.reverse().toString();
}

public static void main(String[] args) {

int n=4;
int l=(int)Math.pow(2, n);
String[] container=new String[l];
String ss=binary(l-1);
int size=ss.length();
String k="";
for(int i=0;i<l;i++)
{
container[i]=BinaryCodeGenerator.binary(i);

if(container[i].length()<size)
{

for(int j=container[i].length();j<size;j++)
{
k=k+0;
}
k=k+container[i];
container[i]=k;
}
k="";
}

System.out.println(Arrays.toString(container));

}

}

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

``````package com.career.cup;

import java.util.Arrays;

public class BinaryCodeGenerator {

public static String binary(int data)
{
int r;
StringBuffer s=new StringBuffer();
while(data!=0)
{
r=data%2;
data=data/2;
s=s.append(r);

}

return s.reverse().toString();
}

public static void main(String[] args) {

int n=4;
int l=(int)Math.pow(2, n);
String[] container=new String[l];
String ss=binary(l-1);
int size=ss.length();
String k="";
for(int i=0;i<l;i++)
{
container[i]=BinaryCodeGenerator.binary(i);

if(container[i].length()<size)
{

for(int j=container[i].length();j<size;j++)
{
k=k+0;
}
k=k+container[i];
container[i]=k;
}
k="";
}

System.out.println(Arrays.toString(container));

}

}``````

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

A simple solution in C++

``````#include <iostream>
#include <vector>

int bitcount(int aArg) {
int c = 0; // bit count
for(; aArg; c++)
aArg &= aArg -1; // clears the least significat bit

return c;
}

void printBitCombinations(int K) {
std::vector<int> A;

for(int i = 0; i <= K; ++i) {
for(int j = 0; j < 1 << K; ++j) {
if(bitcount(j) == i)
A.push_back(j);
}
}

for(auto& a : A) {
std::cout << a << std::endl;
}
}

int
main() {

printBitCombinations(4);

return 0;
}``````

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

``````public class CombinationNumberKBits {
public static void main(String[] args) {
printCombinationsKBits(3);
}

public static void printCombinationsKBits(int k) {
if (k <= 0) return;

int pow = new Double(Math.pow(2, k)).intValue();
int i = 0, j = 0;
int num = 0;
List<int[]> r = new ArrayList<>();
int[] arr = null;

while (i < pow) {
num = i;
j = k-1;
arr = new int[k];
while(num > 0 && j >= 0) {
if ((num & 1) > 0) {
arr[j] = 1;
}
j--;
num = num >> 1;
}
i++;
}

for (int l = 0; l <= k && !r.isEmpty(); l++) {
List<int[]> subset = findArraysWithKBits(r, l);
printArrays(subset);
r.removeAll(subset);
}

}
private static List<int[]> findArraysWithKBits(List<int[]> arr, int k) {
List<int[]> r = new ArrayList<>();
for (int[] is : arr) {
if (countBits(is) == k) {
}
}
return r;
}

public static int countBits(int[] arr) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
count++;
}
}
return count;
}

public static void printArrays(List<int[]> arr) {
for (int[] is : arr) {
System.out.println();
for (int i = 0; i < is.length; i++) {
System.out.print(is[i] + " ");
}
}
}
}
// ouput:
/*
0 0 0
0 0 1
0 1 0
1 0 0
0 1 1
1 0 1
1 1 0
1 1 1
*/``````

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

A solution in C:

``````static unsigned
bits_set (unsigned v)
{
unsigned c;
for (c=0; v; c++)
v &= (v-1);
return c;
}

int
main (int argc, char **argv)
{
unsigned k = atoi(argv[1]);
unsigned sz = power(2, k);
signed *heads = (signed*)malloc(sizeof(signed) * (k+1));
signed *tails = (signed*)malloc(sizeof(signed) * (k+1));
signed *nexts = (signed*)malloc(sizeof(signed) * sz);
signed i, nbits;

for(nbits=0; nbits<=k; nbits++)

for(i=1; i<sz; i++) {
nbits = bits_set(i);
if (tails[ nbits ] == -1) {
tails[ nbits ] = i;
nexts[ i ] = -1;
continue;
}
nexts[ tails[nbits] ] = i;
nexts[ i ] = -1;
tails[ nbits ] = i;
}

for(nbits=1; nbits<=k; nbits++) {
printf("%d bits: ", nbits);
printf("%d ", i);
printf("\n");
}

return 0;
}``````

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

Just a thought correct me if I am wrong.

Will take an example and try to explain, If input is 4

0 bits set elements : 0
only 1 bit set elements : 1 , 2 , 4 , 8 ( powers of 2 < pow(2,4))
only 2 bit set elements : 3, 5, 6 , 9, 10 , 12 (sum of 2 1 bit set numbers in the above list )
only 3 bit set elements : 7 , 11, 13, 14 ( sum of above list and power of 2 elements)
All bits set ( 4 in this case) elements : 15 ( pow(2,4) -1 )

not a program but just an approach dont really have a working code ready , will try and post it when it is done.

I suppose the worst case would be O(m^2) where m would be maximum elements in a m bits set element array.

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

``````package test;

import java.util.Iterator;
import java.util.Scanner;

@SuppressWarnings("resource")
public static void main(String[] args) {

Scanner in = new Scanner(System.in);
int totalOfBites = in.nextInt();

solution (arrayofBits,  totalOfBites );

//System.out.println("arrayofBites.size "+arrayofBites.size());

Iterator<String> spacesofBits = arrayofBits.iterator();

while ( spacesofBits.hasNext()){

String listIntegers= spacesofBits.next();

System.out.println(listIntegers);

}

}

private static void solution (LinkedHashSet<String> arrayofBits, int totalOfBits ){

int numberofBitInternal = 0, lengthofNumberOfBits=0,
counterIndexBite=totalOfBits;

String binaryNumberofDecimal = new String();
int totalofLines = (int) Math.pow(2, totalOfBits);

while (numberofBitInternal <= (totalofLines-1) ){

lengthofNumberOfBits = Integer.toBinaryString(numberofBitInternal).length();
counterIndexBite = lengthofNumberOfBits;
binaryNumberofDecimal = Integer.toBinaryString(numberofBitInternal);
//System.out.println("toBinaryString "+ Integer.toBinaryString(numberofBitInternal));
//System.out.println("numberofBiteInternal "+numberofBiteInternal);

if (lengthofNumberOfBits == totalOfBits ){

}else{

StringBuilder arrayWithBits = new StringBuilder();

while (counterIndexBite < totalOfBits ){

arrayWithBits.append(0);
counterIndexBite++;

}

arrayWithBits.append(binaryNumberofDecimal);

}

numberofBitInternal++;

}

}

}``````

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

``````package test;

import java.util.Iterator;
import java.util.Scanner;

@SuppressWarnings("resource")
public static void main(String[] args) {

Scanner in = new Scanner(System.in);
int totalOfBites = in.nextInt();

solution (arrayofBits,  totalOfBites );

//System.out.println("arrayofBites.size "+arrayofBites.size());

Iterator<String> spacesofBits = arrayofBits.iterator();

while ( spacesofBits.hasNext()){

String listIntegers= spacesofBits.next();

System.out.println(listIntegers);

}

}

private static void solution (LinkedHashSet<String> arrayofBits, int totalOfBits ){

int numberofBitInternal = 0, lengthofNumberOfBits=0,
counterIndexBite=totalOfBits;

String binaryNumberofDecimal = new String();
int totalofLines = (int) Math.pow(2, totalOfBits);

while (numberofBitInternal <= (totalofLines-1) ){

lengthofNumberOfBits = Integer.toBinaryString(numberofBitInternal).length();
counterIndexBite = lengthofNumberOfBits;
binaryNumberofDecimal = Integer.toBinaryString(numberofBitInternal);
//System.out.println("toBinaryString "+ Integer.toBinaryString(numberofBitInternal));
//System.out.println("numberofBiteInternal "+numberofBiteInternal);

if (lengthofNumberOfBits == totalOfBits ){

}else{

StringBuilder arrayWithBits = new StringBuilder();

while (counterIndexBite < totalOfBits ){

arrayWithBits.append(0);
counterIndexBite++;

}

arrayWithBits.append(binaryNumberofDecimal);

}

numberofBitInternal++;

}

}

}``````

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

``````public static void kbitGenerator(int[] arr, int k, int i) {
if (i < k) {
for (int m = 0; m <= 1; m++) {
arr[i] = m;
kbitGenerator(arr, k, i + 1);
}
} else {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j]);
}
System.out.println();
}
}``````

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

``````public static void kbitGenerator(int[] arr, int k, int i) {
if (i < k) {
for (int m = 0; m <= 1; m++) {
arr[i] = m;
kbitGenerator(arr, k, i + 1);
}
} else {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j]);
}
System.out.println();
}
}``````

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

public static void kbitGenerator(int[] arr, int k, int i) {
if (i < k) {
for (int m = 0; m <= 1; m++) {
arr[i] = m;
kbitGenerator(arr, k, i + 1);
}
} else {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j]);
}
System.out.println();
}
}

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

``````class MyArrayItem {
public int data;
public int next;

public MyArrayItem(int numOfCombinations) {
this.data = -1;
this.next = numOfCombinations;
}
}

MyArrayItem[] Arr;

public void printAllBitCombinations(int k) {
final int numOfCombinations = (int)Math.pow(2.0,(double)k);

Arr = new MyArrayItem[numOfCombinations];
for(int i=0; i<numOfCombinations; i++)
Arr[i] = new MyArrayItem(numOfCombinations);

System.out.println("input "+ k + "  has " + numOfCombinations + "  combinations to show");
int combinationsToShow = numOfCombinations;

// Combination with All 0's is only 0
Arr[0].data = 0;
combinationsToShow--;

System.out.println(" 0 bits set list ");
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
} while(Arr[startIdxToShow].next != numOfCombinations);

// Combination with only 1 bit set are powers of 2
Arr[1].data = 1;

int temp = 1;
for (int i=1; i<k; i++) {
int t = temp * 2;
Arr[temp].next = t;
Arr[t].data = t;
temp = t;
}

System.out.println(" 1 bits set list ");
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);

// Combination with 2 bits set is sum of 2 digits with 1 bit set
int n=2;
while(n<k) {
int a = headlist.get(n-1); //previous list
int b = headlist.get(1); // single bit list

for (int i=0; i<k; i++) {
int t = a + b;
if (Arr[t].data == -1)
break;
b = Arr[b].next;
}

System.out.println(n +" bits set list ");
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);

n++;
}

// For All bits set
Arr[numOfCombinations-1].data = numOfCombinations - 1;

System.out.println(k +" bits set list ");
System.out.println(" " + Arr[numOfCombinations-1].data + " " );

}

int sumIncreasing(int a, int b, int numOfCombinations) {
int t = a + b;

if (a == b)
return numOfCombinations;

if (Arr[t].data != -1)
return numOfCombinations;

int l1 =numOfCombinations, l2 =numOfCombinations;
if ((Arr[b].next < numOfCombinations) && (a+Arr[b].next < numOfCombinations))
l1 = sumIncreasing(a,Arr[b].next,numOfCombinations);
if (b+Arr[a].next < numOfCombinations)
l2 = sumIncreasing(Arr[a].next,b,numOfCombinations);

Arr[t].data = t;
if (l2 < l1) {
Arr[t].next = l2;
int temp = l2;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l1;
} else if (l1 < l2) {
Arr[t].next = l1;
int temp = l1;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l2;
}

return t;
}``````

I am only printing the decimal numbers herewith increasing number of bits.
To print in binary format you would need a function to convert from decimal to binary string of fixed size

I am not sure of the exact complexity, think it is O(k^2).
Could someone confirm / correct me here. Also any suggestions would be great

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

``````class MyArrayItem {
public int data;
public int next;

public MyArrayItem(int numOfCombinations) {
this.data = -1;
this.next = numOfCombinations;
}
}

MyArrayItem[] Arr;

public void printAllBitCombinations(int k) {
final int numOfCombinations = (int)Math.pow(2.0,(double)k);

Arr = new MyArrayItem[numOfCombinations];
for(int i=0; i<numOfCombinations; i++)
Arr[i] = new MyArrayItem(numOfCombinations);

System.out.println("input "+ k + "  has " + numOfCombinations + "  combinations to show");
int combinationsToShow = numOfCombinations;

// Combination with All 0's is only 0
Arr[0].data = 0;
combinationsToShow--;

System.out.println(" 0 bits set list ");
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
} while(Arr[startIdxToShow].next != numOfCombinations);

// Combination with only 1 bit set are powers of 2
Arr[1].data = 1;

int temp = 1;
for (int i=1; i<k; i++) {
int t = temp * 2;
Arr[temp].next = t;
Arr[t].data = t;
temp = t;
}

System.out.println(" 1 bits set list ");
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);

// Combination with 2 bits set is sum of 2 digits with 1 bit set
int n=2;
while(n<k) {
int a = headlist.get(n-1); //previous list
int b = headlist.get(1); // single bit list

for (int i=0; i<k; i++) {
int t = a + b;
if (Arr[t].data == -1)
break;
b = Arr[b].next;
}

System.out.println(n +" bits set list ");
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);

n++;
}

// For All bits set
Arr[numOfCombinations-1].data = numOfCombinations - 1;

System.out.println(k +" bits set list ");
System.out.println(" " + Arr[numOfCombinations-1].data + " " );

}

int sumIncreasing(int a, int b, int numOfCombinations) {
int t = a + b;

if (a == b)
return numOfCombinations;

if (Arr[t].data != -1)
return numOfCombinations;

int l1 =numOfCombinations, l2 =numOfCombinations;
if ((Arr[b].next < numOfCombinations) && (a+Arr[b].next < numOfCombinations))
l1 = sumIncreasing(a,Arr[b].next,numOfCombinations);
if (b+Arr[a].next < numOfCombinations)
l2 = sumIncreasing(Arr[a].next,b,numOfCombinations);

Arr[t].data = t;
if (l2 < l1) {
Arr[t].next = l2;
int temp = l2;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l1;
} else if (l1 < l2) {
Arr[t].next = l1;
int temp = l1;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l2;
}

return t;
}``````

I am only printing the decimal numbers here.
To print in binary format you would need a function to convert from decimal to binary string of fixed size

Also not sure of complexity, think it is O(k^2) . Please confirm / correct me here.

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

``````class MyArrayItem {
public int data;
public int next;

public MyArrayItem(int numOfCombinations) {
this.data = -1;
this.next = numOfCombinations;
}
}

MyArrayItem[] Arr;

public void printAllBitCombinations(int k) {
final int numOfCombinations = (int)Math.pow(2.0,(double)k);

Arr = new MyArrayItem[numOfCombinations];
for(int i=0; i<numOfCombinations; i++)
Arr[i] = new MyArrayItem(numOfCombinations);

System.out.println("input "+ k + "  has " + numOfCombinations + "  combinations to show");
int combinationsToShow = numOfCombinations;

// Combination with All 0's is only 0
Arr[0].data = 0;
combinationsToShow--;

System.out.println(" 0 bits set list ");
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
} while(Arr[startIdxToShow].next != numOfCombinations);

// Combination with only 1 bit set are powers of 2
Arr[1].data = 1;

int temp = 1;
for (int i=1; i<k; i++) {
int t = temp * 2;
Arr[temp].next = t;
Arr[t].data = t;
temp = t;
}

System.out.println(" 1 bits set list ");
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);

// Combination with 2 bits set is sum of 2 digits with 1 bit set
int n=2;
while(n<k) {
int a = headlist.get(n-1); //previous list
int b = headlist.get(1); // single bit list

for (int i=0; i<k; i++) {
int t = a + b;
if (Arr[t].data == -1)
break;
b = Arr[b].next;
}

System.out.println(n +" bits set list ");
do {
System.out.println(" " + Arr[startIdxToShow].data + " " );
startIdxToShow = Arr[startIdxToShow].next;
} while(startIdxToShow != numOfCombinations);

n++;
}

// For All bits set
Arr[numOfCombinations-1].data = numOfCombinations - 1;

System.out.println(k +" bits set list ");
System.out.println(" " + Arr[numOfCombinations-1].data + " " );

}

int sumIncreasing(int a, int b, int numOfCombinations) {
int t = a + b;

if (a == b)
return numOfCombinations;

if (Arr[t].data != -1)
return numOfCombinations;

int l1 =numOfCombinations, l2 =numOfCombinations;
if ((Arr[b].next < numOfCombinations) && (a+Arr[b].next < numOfCombinations))
l1 = sumIncreasing(a,Arr[b].next,numOfCombinations);
if (b+Arr[a].next < numOfCombinations)
l2 = sumIncreasing(Arr[a].next,b,numOfCombinations);

Arr[t].data = t;
if (l2 < l1) {
Arr[t].next = l2;
int temp = l2;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l1;
} else if (l1 < l2) {
Arr[t].next = l1;
int temp = l1;
while (Arr[temp].next != numOfCombinations) {
temp = Arr[temp].next;
}
Arr[temp].next = l2;
}

return t;
}

I am only printing the decimal numbers here.
To print in binary format you would need a function to convert from decimal to binary string of fixed size

Also not sure of complexity, think it is O(k^2) .  Please confirm / correct me here.``````

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

A simple recursive solution:

``````void print_nums(int n) {
for(q = 0; q < n; q++)
print_intern(0, 0, 0, q, n);
}

void print_intern(int x, int next_pos, int bits, int cur_len, int total_len) {
if (bits >= cur_len) {
printf("%d\n", x);
return;
}

for(j = next_pos; j < total_len; j++) {
y = set_bit(x, j);
print_intern(y, j + 1, bits + 1, cur_len, total_len);
}
}``````

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

In Python >= 2.6 itertools has a handy combinations method that'll emit r-length subsequences in lexicographic sort order. Using itertools.chain by increasing the number of bits sets creates a space-constant generator.

Arrays are indexed 0 from the left, bits indexed 0 from the right, so we call reversed().

``````from itertools import chain
from itertools import combinations

def BitsSet(k):
return chain.from_iterable(combinations(range(k), count) for count in range(k+1))

def PrintBits(k):
for bits in BitsSet(k):
print(''.join(reversed('1' if idx in bits else '0' for idx in range(k)))``````

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

``````public void setBits(int k) {
int n = 0, t = 0, l = k;
while (n < Math.pow(2, k) - 1) {
for (int i = 0; i < l; i++) {
t = n | 1 << i;
System.out.println(t);
}
l--;
n = t;
}
}``````

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

You are correct with the thought. For getting the number of elements with only ! bit set is similar to knowing the number of ways we can pick one box out of k boxes. This gives us the following formula: (n be the num of set bits)
k! / (n! * (k-n)!)
Thus, if k=4, n=0 => 1 element
if k=4, n=1 => 4!/3!*1! = 4 elements
if k=4, n=2 => 4!/2!*2! = 6 elements
if k=4, n=3 => 4!1!*3! = 4 elements
if k=4, n=4 => 4!/4!*0! = 1 element

That way I think we can get the total number of elements for every set bit reserve space accordingly.

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

``````#include "stdafx.h"
#include <vector>

void shiftBits(unsigned long number, int shiftStartIndex, int shiftEndIndex) {
if(shiftStartIndex < 0){
return;
}
if (( (1 << shiftStartIndex) && number )== 0){
return;
}
for(int i = shiftStartIndex; i < shiftEndIndex - 1; ++i) {
unsigned long mask = ~(1 << i);
number = number | ( 1 << (i + 1) );
printf("%d ", number);
shiftBits(number, shiftStartIndex - 1, i + 1);
}
}

void insertBits(int bitCount){
unsigned long number = 0;
printf("%d ", number);
for(int i = 0; i< bitCount;++i) {
number = number | (1 << i);
printf("%d ", number);
shiftBits(number, i, bitCount);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int bits;
scanf_s("%d", &bits);
insertBits(bits);
getchar();
getchar();
return 0;
}``````

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

``````import java.util.*;

public class EnumKBitSet {
char[] ch=null;
public void enumKBitSet(int K)
{
ch = new char[K];
for (int i=0; i < ch.length; i++) ch[i]='0';
for (int k =0; k <= ch.length ; k++)
enumKBit(k, ch, ch.length);
}
private void enumKBit(int k, char[] ch, int pos)
{
int n = ch.length-1;
if (k==0)
{
System.out.print(new String(ch)+" ");
return;
}
for (int p=n-(k-1); p > n-pos; p--)
{
ch[p]='1';
enumKBit(k-1, ch, n-p);
ch[p]='0';
}
}
public static void main(String argv[])
{
EnumKBitSet ekbs = new EnumKBitSet();
ekbs.enumKBitSet(4);
}
}
// k = 3
// 000, 001, 010, 100, 011, 101, 110,
// k = 4
// 0000 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111``````

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

``````public class BitSet {

public static void main(String[] args) {
BitSet b = new BitSet();
b.generateBit(3);
}

public void generateBit(int k) {
for (int i = 0; i <= k; i++) {
generateBitSet(k, i, "");
}
}

public void generateBitSet(int size, int d, String suffix) {
if (d < 0) {
return;
}
if (size <= 0) {
System.out.println(suffix);
} else if (size == d) {
generateBitSet(size - 1, d - 1, "1" + suffix);
} else {
generateBitSet(size - 1, d - 1, "1" + suffix);
generateBitSet(size - 1, d, "0" + suffix);
}
}``````

}

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

Stack<Integer> stack = new Stack<>();
stack.push(0);
while(!stack.isEmpty()) {
Stack newStack = new Stack<>();
while(!stack.isEmpty()) {
int c = stack.pop();
for(int i = 0; i < n; i++) {
int toAdd = (c | (1 << i));
} else {
break;
}
}
}
stack = newStack;
}

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

public class Solution {

public static void main(String [] args) {

printK(4);

System.out.println();

printK(5);

}

public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}

public static void printPrefix(String prefix, int one, int length) {

if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);

newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}

}

}

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

``````public class Solution {

public static void main(String [] args) {

printK(4);

System.out.println();

printK(5);

}

public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}

public static void printPrefix(String prefix, int one, int length) {

if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);

newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}

}``````

}

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

Code in Java. Complexity of the solution is k * 2 ^ k.

``````public static void main(String[] args) {
int k = 4;
for (int i = 0; i <= k; i++)
Func(k, 0, "", i);
}

public static void Func(int k, int ones, String prefix, int max_ones)
{
if (prefix.length() == k)
{
if (ones == max_ones)
System.out.println(prefix);
}
else {
Func(k, ones, prefix + "0", max_ones);
if (ones < max_ones)
{
Func(k, ones + 1, prefix + "1", max_ones);
}
}
}``````

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

``````public class Solution {

public static void main(String [] args) {

printK(4);

System.out.println();

printK(5);

}

public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}

public static void printPrefix(String prefix, int one, int length) {

if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);

newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}
}
}``````

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

Java solution

``````public void printK(int k) {
int N = (int) Math.pow(2,k);
for(int i = 0; i < N; ++i) {
String s = "";
for(int j = 0; j < k; ++j) {
s = String.valueOf(i >> j & 0x1) + s;
}
System.out.println(s);
}
}``````

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

Basically this is the same as printing out all of the binary representation of numbers from 0 to 2^k.

``````public void printK(int k) {
int N = (int) Math.pow(2,k);
for(int i = 0; i < N; ++i) {
String s = "";
for(int j = 0; j < k; ++j) {
s = String.valueOf(i >> j & 0x1) + s;
}
System.out.println(s);
}
}``````

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

``````import java.util.*;

public class BitSetSorter {

public static void getAllBitSets(int k) {
Set<Integer> currBitSet = new HashSet<>();
printBitSet(currBitSet, k);
currBitSet.remove(0);
int num = 1;
for (int i = 0; i < k; i++) {
num <<= 1;
}
for (int i = 2; i <= k; i++) {
printBitSet(currBitSet, k);
Set<Integer> nextBitSet = new HashSet<>();
for (int n : currBitSet) {
for (int m : currBitSet) {
if (n != m) {
}
}
}
currBitSet = nextBitSet;
}
}

public static void printBitSet(Set<Integer> bitset, int len) {
for (int n : bitset) {
System.out.println(String.format("%" + len + "s",
Integer.toBinaryString(n))
.replace(' ', '0'));
}
}

public static void main(String[] args) {
getAllBitSets(4);
}

}``````

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

Is this problem not same as just printing integers from 0 to 2^(k+1) - 1 ? 0 will have zero 1 bits and 2^(k+1) - 1 will have k 1 bits ?

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

``````def print_padded_binaries(n):
format_str = "{0:{fill}" + str(n) + "b}"
for i in xrange(2**n):
print format_str.format(i, fill='0')

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

def convert_num_to_binary(num):
k=0
s=[]
if num==0:
return '000'
while num>0:
rem=num%2
s.append(rem)
num=num/2
str1=''
for i in range(len(s)-1,-1,-1):
str1+=str(s[i])
return str1

def set_k_bits(k):
limit=2**k
num_list=[]
for i in range(limit):
bits_req = 0
binary_num = convert_num_to_binary(i)
if len(binary_num)<k:
bits_req=k-len(binary_num)
num_list.append('0'*bits_req+binary_num)
if binary_num.count('1')==k:
break;
return ','.join(num_list)

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

In Python:

def convert_num_to_binary(num):
k=0
s=[]
if num==0:
return '000'
while num>0:
rem=num%2
s.append(rem)
num=num/2
str1=''
for i in range(len(s)-1,-1,-1):
str1+=str(s[i])
return str1

def set_k_bits(k):
limit=2**k
num_list=[]
for i in range(limit):
bits_req = 0
binary_num = convert_num_to_binary(i)
if len(binary_num)<k:
bits_req=k-len(binary_num)
num_list.append('0'*bits_req+binary_num)
if binary_num.count('1')==k:
break;
return ','.join(num_list)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````void printBin(int i) {
if(i <= 0) {
cout << 0 << endl;
}

while(i) {
cout << (i & 1);
i >>= 1;
}
cout << endl;
}

void print(int i) {
if(i == 0) {
cout << i << endl;
return;
}

print(i - 1);
printBin(i);
}

int main() {

int K = 3;
int res = (1 << K) - 1; // for K = 3, res == 1000 - 1 == 111;

print(res);

return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

In Java

``````public static void printBinaryKBits(int k) {
int length = (int) Math.pow(2, k);

for(int i = 0; i < length; i++) {
System.out.println(Integer.toBinaryString(i));
}
}``````

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.