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?
Yes, it’s right.I did the same thing and got Correct answer.
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!!!
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.
Every number can be represented in binary. Hence answer is simply found using base-2 log.
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
Every number can be expressed as sum powers of a base b, i.e.
which is the main reason why we use 1+floor(logb(N)) to count the number of digits required to express N in base b. ‘a’ coefficients are the weights used to decide whether to include the particular power of b in the expression. a lies between 0 to b-1.
Now, I’ll limit this to base 2. Then, a will have values 0 and 1. In boolean, 0 and 1 mean off and on values, like a switch. If switch is off (0) electricity doesn’t flow, if on (1) electricity flows.
In this problem, 0 and 1 will decide whether we need to include that (power of 2) weight, while adding upto N, or not.
E.g. 45 = 32+8+4+1 = 1 X 2^5 + 0 X 2^4 + 1 X 2^3 + 1 X 2^2 + 0 X 2^1 + 1 X 2^0 = 101101
1 indicates I’ll include the weight, 0 means I won’t. Thus, we need minimum 6 weights to express all numbers upto 45.
To break N into powers of 2, find the power value of 2 closest to N, subtract it from N and do the same thing to remainder iteratively until 0 or 1.
Please inform me for any confusion 
Is this is Correct???
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t!=0)
{
int a=sc.nextInt();
int count=0;
for(int i=1;i<=a;i++)
{
if(count>=a)
{
System.out.println(i-1);
break;
}
else
{
count=count+i;
}
}
t–;
}
}
}
1 Like
#include <iostream.h>
#include<stdlib.h>
using namespace std;
int main()
{
system(“cls”);
int T;
cin>>T;
int sum, a, c[T]={0},i,d;
int N[T]={0};
for(i=0;i<T;i++)
cin>>N[i];
for(i=0;i<T;i++)
{
d=N[i];
sum=0,a=1;
while(sum<N[i])
{
sum=sum+a;
a=a+1;
c[i]++;
}
cout<<c[i]<<endl;
}
return 0;
}
this is my code, But i am getting presentation error for private test cases, and wrong answer for public test cases?? Can anyone help me to fix it??
Can i know what is wrong with my program
from sys import stdin
l=[]
t=int(input()) #Number of test Cases
for i in range(t):
n=int(input()) #the Total Money
l.append(n)
answer=[]
for i in l:
amount=0
count=0
for j in range(1,i+1):
amount+=j
count+=1
if(amount>=i):
answer.append(count)
break
print(*answer,sep="\n",end="")sorry I am a newbie in coding so i am not able to correlate ur explanation with the formula 1+floor(log(n,2))… Please help me to understand this. I mean how you developed this formula ?
but what is logic behind counting of number of digits in N converted into binary number ? I am still confused…sry
Thanks for explaining, I think you should write editorials.
When N is converted to a binary string, the 0s and 1s indicate which power of 2 you need to add up together to get N and which you don’t need. So, by counting the number of digits, we count the (minimum) number of power values of 2 you need to add up together to get N. You may think why to count 0s even when they are not used to get N? The reason is that they might be used for values less than N. Therefore, the length of the bit string tells you how many minimum weights you need to express all numbers from 1 to N.
Please inform me for any doubt
You can follow this :Coins required will be 1,2,4,8,16,32,64… Because if coin of 4 is considered,then it can make upto 7i.e(1,2,3(1+2),4,5(1+4),6(2+4),7(1+2+4))but not 8,so next will be 8 and so on .
I got the logic, thanks for such a good explanation and I value your time to explain me.Thanks
No problems. I feel happy that I’m able to explain the logic to you
for _ in range(int(input())):
s=1
c=1
l=[1]
n=int(input())
for i in range(1,n):
s=s*2
c=c+s
l.append(s)
if (c)>=n:
break
print(len(l))
This Can Work Too…!
for _ in range(int(input())):
s=1
c=1
l=[1]
n=int(input())
for i in range(1,n):
s=s*2
c=c+s
l.append(s)
if (c)>=n:
break
print(len(l))
This Can Work Too…
Sir,Can you please shear the code.I am new at coding so i am unable to understand that formula…