TCS Codevita problem

28

This dosen’t work.The logic is preposterously incorrect.It only works for sample case 0.
Thanks for posting you code

29

I am not getting option to choose Btech Cse in code vita

30

t = int(input())
for i in range(t):
n = int(input())
j = 0
k = 0
while j < n:
k+=1
j+=k
print(k)

but somewhat the system showing runtime error

31

thanks brother…it helped me…before that i was taking in other manner like 1, 2 3, 4 5 6, 7 8 9 10 ,…
in this pattern i did take the o/p

32

can u elaborate

33

floor(1+log2(N))

34

see …it is like 2^n where n is from 0

35

I think you just have to add
1 2 4 8 16 32… until you are greater than or equal to n.

1 Like
36

That’s wrong. You should have tried it for sample and it passes. On the whole, all test cases don’t pass. The solution would be something like this:
Given ‘N’, we are supposed to find the minimum Number of Denominations required so that we can represent any number between 1 and N inclusive using those denominations.
Now, let’s have a look at the Binary representation for some numbers:
1: 00000001; Denominations: $1;
2: 00000010; Denominations: $1, $2;
3: 00000011; Denominations: $1, $2;
4: 00000100; Denominations: $1, $2, $4;
5: 00000101; Denominations: $1, $2, $4;
6: 00000110; Denominations: $1, $2, $4;
7: 00000111; Denominations: $1, $2, $4;
8: 00001000; Denominations: $1, $2, $4, $8;
9: 00001001; Denominations: $1, $2, $4, $8;
Using these Denominations each of them only once, we can obtain any number between 1 and N.
So, the problem is clear that we are required to print the length of binary representation of given number N.
Typical python solution:
for test in range(int(input())):
____ print(len(bin(int(input()))[2:]))#Replace _ with space

2 Likes
37

Awesome way of explanation sir. The approach and way of explanation is mind-blowing. I am really impressed.

38

@bal_95 i got why it is 1,2,4,8,16 but how do i know that it is 1 + floor(log(n,2))?

39 
#include <iostream>
#include <algorithm>
#include<cmath>
#include <bits/stdc++.h> 
using namespace std;


int main()
{
   long long t;
   cin>>t;
   while(t--)
   {
       long long n;
       cin>>n;
       
       
       long long i=0,j=0,k;
       while(n>0)
       {
           n=n>>1;
           i+=1;
       }
       cout<<i<<endl;
   }
   return 0;
}
1 Like
40

I solved it by formula 1+math.floor(math.log(n,2))

41

Logarithm is used to count the number of digits present in a number when expressed in a base b. 1 is added to count the leftmost digit, and finally the floor function is applied to get the final value.

Example:

1+log10(10000000) = 8, which is the no. of digits in the number expressed in base 10.

When a number is expressed in base 2, it counts the number of bits required to express that number. E.g. 27 = 11011 , so 1+log2(27) = 5.755. Applying the floor, we get 5, which as you can see, is the no. of bits used to express the number. It’s a very shortcut way to count digits, instead of running a loop and dividing the number by the base and incrementing the counter, until the number reduces to 1.

42

for example, if input is 11, we should consider $1, $2, $3, $5
so that he can buy any items upto $11 ?
isn’t this is the problem asked?

43

Yes, it’s right.I did the same thing and got Correct answer.

44

Great way of explanation sir! Although i knew this thing and done exact same thing but the way you explained it here is worth praising!!!

45

The key idea of this question is that we can write any number as sum of powers of two( which is the binary presentation of a number).
So we keep adding from powers of 2 from 0,1,2,… until the sum is greater than equal to the given number and the number of iteration will be our answer.

46

Every number can be represented in binary. Hence answer is simply found using base-2 log.

47

Hello, I am new to coding here, can you please explain why we need to count no of digits when we express number in bits ? I understood that 1$,2$,4$,8$…thing still cant able to correlate this with the formula.
Thanks