Re: [algogeeks] Re: finding vlaue of nCr
@oppilas thanks! Wladimir Araujo Tavares *Federal University of Ceará * On Tue, Jun 21, 2011 at 9:47 PM, oppilas . wrote: > @Wladmir. > If you see carefully,then it is quite obvious that product of n > consecutive number will be divisible by n!. > > 3 must be a divisor of at least one number out of three consecutive > number.( because each multiple of 3 lies, 3 number ahead of previous > one.) > Similarly, we can argue for ith number. that it will be a divisor of > at least one number out of i consecutive number. > > On 6/22/11, Wladimir Tavares wrote: > > @sunny agrawal > > In theory, it would be necessary to prove that the product of n > consecutive > > numbers is divisible by n! > > do you agree? > > > > > > Wladimir Araujo Tavares > > *Federal University of Ceará > > > > * > > > > > > > > > > On Tue, Jun 21, 2011 at 5:01 PM, kartik sachan > > wrote: > > > >> sir i think the same ans i gave the above.. > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algogeeks@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com. > >> For more options, visit this group at > >> http://groups.google.com/group/algogeeks?hl=en. > >> > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
@Wladmir. If you see carefully,then it is quite obvious that product of n consecutive number will be divisible by n!. 3 must be a divisor of at least one number out of three consecutive number.( because each multiple of 3 lies, 3 number ahead of previous one.) Similarly, we can argue for ith number. that it will be a divisor of at least one number out of i consecutive number. On 6/22/11, Wladimir Tavares wrote: > @sunny agrawal > In theory, it would be necessary to prove that the product of n consecutive > numbers is divisible by n! > do you agree? > > > Wladimir Araujo Tavares > *Federal University of Ceará > > * > > > > > On Tue, Jun 21, 2011 at 5:01 PM, kartik sachan > wrote: > >> sir i think the same ans i gave the above.. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
@sunny agrawal In theory, it would be necessary to prove that the product of n consecutive numbers is divisible by n! do you agree? Wladimir Araujo Tavares *Federal University of Ceará * On Tue, Jun 21, 2011 at 5:01 PM, kartik sachan wrote: > sir i think the same ans i gave the above.. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
sir i think the same ans i gave the above.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
hey anika here n<=1 and n>=0 so its 1 only -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
hey 1Cn is not 1..
On Tue, Jun 21, 2011 at 2:33 PM, ross wrote:
> A small correction, j = 0 to i.
>
> On Jun 21, 2:01 pm, ross wrote:
> > Hi,
> > Ya DP with memoization is best..
> >
> > nCr= n-1Cr-1 + n-1 C r
> >
> > DP]i,j] = DP[i-1,j-1] + DP[i-1,j];
> >
> > (LINEAR SPACE COMPLEXITY is possible because at each time we require
> > only 2 rows of the matrix)
> >
> > Base Cases,
> > nCn = 1. DP[i,i]=1.
> > 1Cn = 1 DP[1,j] =1.
> > nC1 = n .
> > nC0 = 1
> >
> > for ( i = 0 - N )
> > for ( j= i - N )
> > {
> > if(i == j) dp[i.j] =1.
> > else if (j==1) dp[i j ] = i;
> > else if (j == 0) dp [ i j] = 1;
> > else
> > DP]i,j] = DP[i-1,j-1] + DP[i-1,j];
> >
> > }
> >
> > On Jun 21, 1:34 pm, kartik sachan wrote:
> >
> >
> >
> >
> >
> >
> >
> > > but for big numbers this method is very expensiveand
> hope
> > > give TLE in 1 sec question where n=1000
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
both will work fine
in first case in each step what is done is ans = (ans*(n+1-i))/i;
what happens is
first iteration ans = n, i =1 so i divides ans
sec. iteration ans = product of 2 consecutive nos at least one even so
divisible by 2
in third, ans is prod of 3 consecutive no.s so divisible by 3 and so on
On Tue, Jun 21, 2011 at 9:15 PM, Wladimir Tavares
wrote:
>
> I got a doubt in the following code:
>
> if (k> n / 2)
> k = n-k;
> for (i = 1; i <= k, i + +)
> ans = ans * (n +1- i) / i;
>
> If (n +1- i) is not divisible by i this code should be wrong?
>
> I thought I needed to keep the numerator and denominator and go by
dividing the numerator and denominator gcd
>
> num = 1
> den = 1
>
> for (i = 1; i <= k, i + +) {
> num *= n +1- i;
> den *= i;
> d = gcd (num, den);
> num /= d;
> den / = d;
> }
>
> printf ("% d", num);
>
> Wladimir Araujo Tavares
> Federal University of Ceará
>
>
>
>
>
>
> On Tue, Jun 21, 2011 at 12:34 PM, PRAMENDRA RATHi rathi <
prathi...@gmail.com> wrote:
>>
>> i have also got AC...i am only asking for best algo.
>>
>>
>>
>>
>>
>>
>> PRAMENDRA RATHI
>> NIT ALLAHABAD
>>
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
I got a doubt in the following code:
if (k> n / 2)
k = n-k;
for (i = 1; i <= k, i + +)
ans = ans * (n +1- i) / i;
If (n +1- i) is not divisible by i this code should be wrong?
I thought I needed to keep the numerator and denominator and go by dividing
the numerator and denominator gcd
num = 1
den = 1
for (i = 1; i <= k, i + +) {
num *= n +1- i;
den *= i;
d = gcd (num, den);
num /= d;
den / = d;
}
printf ("% d", num);
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Tue, Jun 21, 2011 at 12:34 PM, PRAMENDRA RATHi rathi wrote:
> i have also got AC...i am only asking for best algo.
>
>
>
>
>
>
> PRAMENDRA RATHI
> NIT ALLAHABAD
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
i have also got AC...i am only asking for best algo. PRAMENDRA RATHI NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
i dont know why r u thinking so but this was my accepted solution for the problem. On Tue, Jun 21, 2011 at 7:34 PM, kartik sachan wrote: > hey sunny suppose u have to calculate 100c50 then there is a lot of > chances of over flow becoz u have to multiply 100 to 50...i > don't think it will work.. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
hey sunny suppose u have to calculate 100c50 then there is a lot of chances of over flow becoz u have to multiply 100 to 50...i don't think it will work.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
i have already mentioned that if final answer fits in 64 bit integer then it
will not overflow
On Tue, Jun 21, 2011 at 5:34 PM, Dumanshu wrote:
> @Sunny: the value can still overflow because
> Using the while loop u r dividing the res value whenever possible. so
> the while checks if the current j divides res or not. What if current
> res value is not divisible by that particular j ... it will multiply
> by i for next res value and it will keep doing this until u get a res
> value divisible by that specific current j. So in the meantime, when
> the res value is increasing just because j doesn't divide it, it can
> overflow.
>
> On Jun 21, 4:12 pm, sunny agrawal wrote:
> > i am doing the same thing without using array
> >
> >long long int res = 1;
> >int j = 2;
> >for(int i = n-k+1; i <= n; i++){
> >res *= (long long int)i;
> >while(j <= k && res%j == 0){
> >res/=j;
> >j++;
> >}
> >}
> >
> > On Tue, Jun 21, 2011 at 4:25 PM, kartik sachan
> > wrote:
> >
> >
> >
> >
> >
> > > @ sunny i am not getting ur apporach
> > > but i am thinking like this..
> > > taking an array from and intilize it to n to n-r
> >
> > > a[1000];
> > > int k=0;
> > > for(int i=n;i>=n-r;i--)
> > > a[k++]=i;
> >
> > > for(int y=n-r;y>1;y--)
> > > for(j=0;j > > if(a[j]%y==0)
> > > {a[j]=a[j]/y;break;}
> >
> > > for example we take 7c3
> >
> > > so first array is intilize to {7,6,5,4}
> > > then we check divisibilty by {3,2}
> > > so 6 is divisible by 3 so put 6/3 back in array 2
> > > so finally 7*2*5*2;
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> >
> > "Algorithm Geeks" group.> To post to this group, send email to
> algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> >
> > algogeeks+unsubscr...@googlegroups.com.> For more options, visit this
> group at
> >
> > http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Sunny Aggrawal
> > B-Tech IV year,CSI
> > Indian Institute Of Technology,Roorkee- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding vlaue of nCr
but it is O(N^2)...will give TLE
On Tue, Jun 21, 2011 at 2:33 PM, ross wrote:
> A small correction, j = 0 to i.
>
> On Jun 21, 2:01 pm, ross wrote:
> > Hi,
> > Ya DP with memoization is best..
> >
> > nCr= n-1Cr-1 + n-1 C r
> >
> > DP]i,j] = DP[i-1,j-1] + DP[i-1,j];
> >
> > (LINEAR SPACE COMPLEXITY is possible because at each time we require
> > only 2 rows of the matrix)
> >
> > Base Cases,
> > nCn = 1. DP[i,i]=1.
> > 1Cn = 1 DP[1,j] =1.
> > nC1 = n .
> > nC0 = 1
> >
> > for ( i = 0 - N )
> > for ( j= i - N )
> > {
> > if(i == j) dp[i.j] =1.
> > else if (j==1) dp[i j ] = i;
> > else if (j == 0) dp [ i j] = 1;
> > else
> > DP]i,j] = DP[i-1,j-1] + DP[i-1,j];
> >
> > }
> >
> > On Jun 21, 1:34 pm, kartik sachan wrote:
> >
> >
> >
> >
> >
> >
> >
> > > but for big numbers this method is very expensiveand
> hope
> > > give TLE in 1 sec question where n=1000
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
