TCS Codevita problem

22

This \log_2(N)+1 only.

4 Likes
23

@bing_ambar, the approach needed for such questions is trying to generate the numbers. When you start with $1 onwards, you will find that you need $1 and $2 and then you will come to know that $3 is not required since we can generate it from $1 and $2. Then, you will eventually need $4 as it can not be generated in any way with the existing coins. Now that $4 is present, you already know that you can generate all values from $1 to $3, which means 4+(1 or 2 or 3) can also be generated, i.e., upto $7 can be generated. Now, the new coin required would be $8. Now, using the same technique, we know that we could generate all values between 1 and 7, and hence, 8 + (1 to 7) gives us all values between 1 and 15 and then the new coin required would be $16.
If you keenly observe, there is a pattern, 1, 2, 4, 8, 16, 32, 64, …
Hope you now understood why it is (1 + floor(log(N, 2))

16 Likes
24

Somebody please tell, in codevita all the inputs are valid or we also have to taken care of that??

25

Till now there has not been any such instances .So ,all the inputs will be valid.

26

i think u should be little more specific in ur question
Because i think $1 and $2 coins are enough to get sum of any number
for example if max is $5
2 * $2 + $1 = $5
2 * $2 = $4
$2 + $1 = $3
…
so on the case with max $10.
If I am wrong Plzzzz correct me ???

27

Well According to your logic only ‘1’ coin is enough to make any $…

We have to distribute various coins with different value so thats not the case

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.