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 }