## TCS CodeVita Interview Question

**Country:**United States

You know, there is C(n, 2) such n-bit integers, so with N ~ 10^14 output value can be order of 2^(10^7), so problem is not just about "bit manipulation".

Solution: lets look at numbers MSB. There is exactly k numbers in this sequence with MSB at position k (1 for MSB = 2^1 (3), 2 for MSB = 2^2 (5,6) and so on). Inside of this blocks of increasingly larger sizes, LSB goes from 0 to k-1.

So, formal solution is following:

- define k = min x : x*(x+1)/2 >= N

- define p = k*(k+1)/2 - N

Answer is 2^k + 2^(k - p - 1).

```
#include<stdio.h>
2
3 int print_two_ones_no(int x)
4
5 {
6
7 int count=0;
8
9 int num = x;
10
11 while(x)
12
13 {
14 x = x&(x-1);
15
16 count++;
17
18 }
19
20 if(count == 2)
21
22 printf("%d ",num);
23
24 }
25
26 int main()
27
28 {
29
30 int num,i;
31
32 printf("Enter the Range :");
33
34 scanf("%d",&num);
35
36 for(i=1;i<=num;i++)
37
{
39
40 print_two_ones_no(i);
41
42 }
43
44 }
17,0-1 Top
```

```
// NOT FOR Competitive stuff - it is meaningless for practical purposes.
// but cool...
/*
Given S is then sorted sequence of numbers such that
Binary representation contains only 2 bits set to 1.
Find S(n).
We solve it by creating an iterator.
*/
s = seq( 3 ) -> {
bs = str($.p[-1],2)
li = rindex(bs.value, _'1' )
if ( li == 1 ){
r = 2 ** #|bs| + 1
} else {
bs.value[li] = _'0'
bs.value[li-1] = _'1'
r = int(bs,2,0)
}
r
}
fold ( [1:9] ) -> { println( s.next ) }
```

```
#Consider the following sequence: 3, 5, 6, 9, 10, 12, 17, 18, 20....
#Write a function that takes n in range(1, 10**14) and returns the
#nth term of the sequence
import math
def a(n):
a = .5; b = .5; c = -n
#use the quadratic formula to find the first i s.t. n <= i*(i+1)/2
i = int(math.ceil( ( -b - math.pow( (b**2 - 4*a*c), .5 ) )/(2*a) ))
if not (0 < i and i < n):
i = int(math.ceil( ( -b + math.pow( (b**2 - 4*a*c), .5 ) )/(2*a) ) )
#sum of first i numbers
s = (i*(i+1)/2)
offset = i - (s - n) - 1
return (1 << i) + (1 << offset)
def b(n):
s = 0; i = 0
#use a loop to find the first i s.t. n <= i*(i+1)/2
#the time to find such an i will grow according like O(sqrt(n))
while True:
if s >= n:
break
else:
i += 1
s += i
offset = i - (s - n) - 1
return (1 << i) + (1 << offset)
```

```
import math
def how_many_bits(x):
count = 0
while x:
x = x & (x - 1)
count += 1
return count
def how_many_bit(x):
return 1 + int(math.log(x,2))
def foo(x):
top_bit = x&-x
higher_bit_set = top_bit + x
mask = higher_bit_set ^ x
mask = mask>>how_many_bit(top_bit)
mask = mask >> 1
return mask + higher_bit_set
x = 3
for i in range(20):
y = foo(x)
print(y)
if how_many_bits(y) != 2:
print("something wrong", y, how_many_bits(y), bin(y))
x = y
```

Boils down to solving arithmetic series and bit manipulation... but tricky

```
//C#
public static int GetTwoBitSequenceValue(int sequenceNumber)
{
int bit2Position = (int) Math.Round(Math.Sqrt(sequenceNumber * 2), 0) - 1;
int bit1Position = sequenceNumber - ((int)((bit2Position * (bit2Position + 1)) / 2) + 1);
return (2 << bit2Position) | (1 << bit1Position);
}
public static void Test()
{
for (int i = 1; i < 20; i++)
{
int y = GetTwoBitSequenceValue(i);
Console.WriteLine("x {0} => y {1}",i, y);
}
}
```

public class BitWise {

public static void main(String...strings) {

int k = 2;

int currNo = 1, extra = 1, pow =1, base = (int) Math.pow(2, pow);

int seriesNo = base + extra;

while(true) {

System.out.println(seriesNo);

if(currNo == k)

break;

extra = extra << 1;

if(base == extra) {

pow++;

extra = 1;

base = (int) Math.pow(2, pow);

}

seriesNo = base + extra;

currNo++;

}

}

}

```
#include <stdio.h>
int main()
{
int i,j,n,k;
int imask=0;
int jmask=0;
//n bits number
n=8;
//kth number
k=6;
int count=0;
i=1;
int allones=~0;
while(i<n)
{
for(j=0;j<i;j++)
{
count++;
//this is the number. i.e. i+1 are total number of bits with ith bit as 1 and jth bit as 1.
imask=1<<i;
jmask=1<<j;
allones=allones & imask;
allones=allones & jmask;
printf("count %d - %d\n",count,imask | jmask);
}
i++;
}
return 0;
}
```

1 #include<stdio.h>

2

3 int print_two_ones_no(int x)

4

5 {

6

7 int count=0;

8

9 int num = x;

10

11 while(x)

12

13 {

14 x = x&(x-1);

15

16 count++;

17

18 }

19

20 if(count == 2)

21

22 printf("%d ",num);

23

24 }

25

26 int main()

27

28 {

29

30 int num,i;

31

32 printf("Enter the Range :");

33

34 scanf("%d",&num);

35

36 for(i=1;i<=num;i++)

37

38 {

39

40 print_two_ones_no(i);

41

42 }

43

44 }

```
1 #include<stdio.h>
2
3 int print_two_ones_no(int x)
4
5 {
6
7 int count=0;
8
9 int num = x;
10
11 while(x)
12
13 {
14 x = x&(x-1);
15
16 count++;
17
18 }
19
20 if(count == 2)
21
22 printf("%d ",num);
23
24 }
25
26 int main()
27
28 {
29
30 int num,i;
31
32 printf("Enter the Range :");
33
34 scanf("%d",&num);
35
36 for(i=1;i<=num;i++)
37
38 {
39
40 print_two_ones_no(i);
41
42 }
43
44 }
```

#include<stdio.h>

- sandeep kumar EMERTXE June 14, 20172

3 void two_1s_no_generator(unsigned int num)

4

5 {

6 int count=0,bol_val;

7

8 int i,j;

9

10 unsigned int mask;

11

12 for(j=1;j<=num;j++)

13

14 {

15 mask=1<<31;

16 count=0;

17

18 for(i=1;i<=32;i++)

19

20 {

21 bol_val= j&mask?1:0;

22

23 if(bol_val==1)

24 count++;

25

26 mask=mask>>1;

27

28

29 }

30

31 if(count == 2)

32 {

33 printf("%d ",j);

34

35 }

36 }

37 printf("\n\n");

38 }

39 int main()

40

41 {

42 unsigned int num;

43

44 printf("Enter the Range :");

45

46 scanf("%d",&num);

47

48 two_1s_no_generator(num);

49

50 }