## Microsoft Interview Question

Software Engineer / Developersthis is so called gray-code combinations, don't ask me why it works

personally I don't understand it completely, it's magic ;))

```
int N = 7; // number of bits in words
int K = 3; // number of bits in words
int *x; // elements in combination at x[1] ... x[k]
void visit() // prints out one combination
{
for(int j = 1; j <= K; j++)
printf("%d ", x[j]);
printf("\n");
}
void comb_gray(int n, int k, bool z)
{
if(k == n) {
for(int j=1; j<=k; ++j)
x[j] = j;
visit();
return;
}
if(z) {// recurse in forward direction
comb_gray(n-1, k, z);
if(k > 0) {
x[k] = n;
comb_gray(n-1, k-1, !z);
}
} else { // backward direction:
if(k > 0) {
x[k] = n;
comb_gray(n-1, k-1, !z);
}
comb_gray(n-1, k, z);
}
}
main() {
x = new int[N+1];
comb_gray(N, K, 1);
}
```

the Gray codes have the property of differing only in one bit for each consecutive numbers.

e.g. gray code for numbers up to 7 is:

000 : 0

001 : 1

011 : 2

010 : 3

110 : 4

111 : 5

101 : 6

100 : 7

We prepare Gray codes for the number as done above, and

then output the parent set-member if that particular bit position in gray code is '1'. :)

P.S. getting Gray code is not hard either can be achieved

using XOR for consecutive regular bit positions of

standard binary representation.

map all N elements to a bit in a number...creating a N bit number

start with a number with all the lower M bits set...

int start = no with all M lower bits set;

while (start < ( pow(2,N-1) - 1))

{

print elements whose 1 bit is set.

start = no greater than start with same 1 count

}

This method won't work. Suppose we have 5 elements and output a combination of 3.

Now start = 01110, which means we output the middle three elements. Next start which is greater and also with same 1 count is 10011, which differ from the previous in two positions.

using the bit sets logic for printing all combinations

Step 1: finding first m-1 bits to avoid and start from there.

step 2: finding the bits set in next number onward. Then set a BitArray for the same bits. Then counting total bits set in the BitArray.

step 3: if the count of bits set is m, then start printing them , else reset the

BitArray and start step 2.

```
public static void CombinationsOfMoutOfN(char []set,int m)
{
int n = set.Length;
int powerSet = (int)Math.Pow(2, n);
int skippingFirstMminusbits = (int)Math.Pow(2, m) - 1;
BitArray bitArray = new BitArray(n, false );
for (int i = skippingFirstMminusbits; i < powerSet; ++i)
{
int count = 0;
for (int j = 0; j < n; ++j)
{
//this is the logic
if ((i & (1 << j)) > 0)
{
count++;
bitArray[j] = true;
}
else
bitArray[j] = false;
}
if (count == m)
{
for (int j = 0; j < n; ++j)
{
if (bitArray[j] == true)
{
Console.Write(set[j]);
bitArray[j] = false;
}
}
}
count = 0;
Console.WriteLine("");
}
```

Loop(i=1 to N of Set {N})

- sunny June 15, 2007Loop(j=1 to M of Set {M})

Loop(k=1 to M of Set {M})

if( j == k)

print {N[i]};

print {M[k]};

End Loop

End Loop

End Loop