Re: [algogeeks] Re: Find Largest number in log(n)
Thanks Dave, Don and all others for this clarification. On Mon, Dec 12, 2011 at 11:23 PM, Prakash D cegprak...@gmail.com wrote: only the number of comparisons is log(n) On Mon, Dec 12, 2011 at 11:04 PM, Ankur Garg ankurga...@gmail.com wrote: Agree with dave..Its still O(n) On Mon, Dec 12, 2011 at 10:57 PM, Dave dave_and_da...@juno.com wrote: @Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first round, involving n/2 comparisons, is O(n). Dave On Dec 12, 11:23 am, sagar pareek sagarpar...@gmail.com wrote: Yes Mr. DoN First round of Tournament sort results in log(n) time for finding largest no. n/2+n/4+n/8 results n/(2^i) where ^ = power On Mon, Dec 12, 2011 at 8:16 AM, Don dondod...@gmail.com wrote: No. To find the largest number in an unsorted array requires looking at each number, which is order n by definition. Don On Dec 12, 10:02 am, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING 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. -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING 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] MYSIS AND DRISHTI-SOFT
aal puzzle from techinterview. more then 50 % came from there . -- 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.
[algogeeks] Suggest Algo for this Question
Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. This question was also asked in Amazon -- 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.
[algogeeks] Dynamic programming question
We have apples arranged in a mxn matrix. We start from the upper left corner and have to reach bottom right corner with maximum apples. We can only move either down or right. Now if we can start any where in the matrix and have to reach anywhere on the right(reach n column). We can either up, down, right(but not left). We have to collect maximum apples from a given location. I am trying to solve problem. solution for the first one is given at http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=dynProg . What data structure would be suitable for the second problem and will dynamic programming work. Thanks in advance. Azhar. -- 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] Dynamic programming question
i thnk it can be done using dynamic programming.. let the array b 25 3 25 1 10 2 5 now at at every point in the matrix..there can be two ways..to reach that point..either from left..or from right.. for example to reach at the center of the above matrix..we can come from 2-5-5 or 2-2-5..and can select the path that give max apples..similarly..we can calculate this..for every point in the 2D array the above matrix can be transformed into maximum apples at every point 2 7 10 4 12 13 14 1621 for top most row and left most column..we only add..the previous value..(because we dont have second direction) for arr(1,1) we calculate the max..that is from 7 and 4..and add it to the center value..to get 12 for arr(1,2) we calculate the max ..that if rom 12 and 10 and add it to arr(1,2) to get ..13.. this is how..we can do for..arr(2,1) and arr(2,2)... this is what we can do.. correct me if am wrong..i am naive solution provider On Tue, Dec 13, 2011 at 4:14 PM, Azhar Hussain azhar...@gmail.com wrote: We have apples arranged in a mxn matrix. We start from the upper left corner and have to reach bottom right corner with maximum apples. We can only move either down or right. Now if we can start any where in the matrix and have to reach anywhere on the right(reach n column). We can either up, down, right(but not left). We have to collect maximum apples from a given location. I am trying to solve problem. solution for the first one is given at http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=dynProg . What data structure would be suitable for the second problem and will dynamic programming work. Thanks in advance. Azhar. -- 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. -- *Dheeraj Sharma* -- 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.
[algogeeks] Re: Dynamic programming question
Graph take up, right and bottom as nodes connected to current and do find max path. On Dec 13, 3:44 pm, Azhar Hussain azhar...@gmail.com wrote: We have apples arranged in a mxn matrix. We start from the upper left corner and have to reach bottom right corner with maximum apples. We can only move either down or right. Now if we can start any where in the matrix and have to reach anywhere on the right(reach n column). We can either up, down, right(but not left). We have to collect maximum apples from a given location. I am trying to solve problem. solution for the first one is given athttp://community.topcoder.com/tc?module=Staticd1=tutorialsd2=dynProg. What data structure would be suitable for the second problem and will dynamic programming work. Thanks in advance. Azhar. -- 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] MYSIS AND DRISHTI-SOFT
On Tue, Dec 13, 2011 at 3:21 PM, hary rathor harry.rat...@gmail.com wrote: aal puzzle from techinterview. more then 50 % came from there . -- 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. @aayush all the memebers approx. have joined both the groups -- 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] MYSIS AND DRISHTI-SOFT
@aayush Lots of member are here but that doesn't mean that you should start posting the things which are strictly banned on this group. I hope you will take care next time while posting anything in this group. On Tue, Dec 13, 2011 at 7:40 PM, rahul sharma rahul23111...@gmail.comwrote: On Tue, Dec 13, 2011 at 3:21 PM, hary rathor harry.rat...@gmail.comwrote: aal puzzle from techinterview. more then 50 % came from there . -- 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. @aayush all the memebers approx. have joined both the groups -- 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. V 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] Nice question
actually there are infinite number of sequences that match it for example if the absolute differences are 3 2 5 1 one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5 7 2 3 and you can add any integer value to all elements and the result will still be valid actually you can start with any number and and then the second number will be equal to the first number that you chose plus/minus the first absolute difference and so on so if we are given the first element of the sequence there are 2^(n-1) ways to find a valid sequence because for each absolute difference we can either add the absolute difference to the last sequence element or subtract the absolute difference from it On Mon, Dec 12, 2011 at 9:01 PM, KAY amulya.manches...@gmail.com wrote: If for a number n digits long, the absolute difference between adjacent digits is given, how to find out the number of different numbers with these absolute differences ? for eg, if n=5 and the absolute differences are 3 2 5 1 then 1 possible number is 6 3 5 0 1(because |6-3|=3,|3-5|=2 and so on...) How many such numbers will be there? -- 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] simpel DP solution
1 is not a prime number!
On Mon, Oct 31, 2011 at 4:07 PM, mc2 . qlearn...@gmail.com wrote:
Hey guys ,
I am trying to solve this DP problem :
http://community.topcoder.com/stat?c=problem_statementpm=10033rd=13513
SRM 422, DIV 2 ,level 2.
Here is my DP solution. But it is not working. Can someone please tell me
the flaw in this code :
#includetopheader.h
int prime(int i)
{
return i==1 ||i==2 || i==3 || i==5 || i==7 || i==11 || i==13|| i==17;
}
int method(double p,double q)
{
double a[19][19]={0.,0.},b[19][19]={0.,0.};
a[0][0]=1;
for(int i=1;i=18;i++)
{
a[i][i]=pow(p/100,i);
b[i][i]=pow(q/100,i);
for(int j=1;j=18;j++)
{
a[i][j]=(100-p)/100 * a[i-1][j] + (p/100) * a[i][j-1];
b[i][j]=(100-q)/100 * b[i-1][j] + (q/100) * b[i][j-1];
}
}
double ar[19]={0.};
for (int i=0; i18; i++) {
for (int j=18; j=0; j--)
ar[j] = ((ar[j-1])*p + ar[j]*(100-p))/100.0;
}
for(int i=0;i=18;i++)
coutar[i]\ta[i][18]\n;
cout\n;
for(int i=1;i19;i++)
{
double temp=0.0,temp1=0.0;
int k;
for(k=i;k19;k++)
{
temp+=a[i][k];
temp1+=b[i][k];
}
a[i][k-1]=temp;
b[i][k-1]=temp1;
//couttemp temp1 i k-1\n;
}
double res=0.0;
for(int i=1;i19;i++)
{
for(int j=1;j19;j++)
{
if(prime(i) || prime(j))
{
res +=a[i][18] * b[i][18];
// couti j res\n;
}
}
}
coutres\n;
return 0;
}
int main()
{
double p,q;
cinpq;
method(p,q);
return 0;
}
thanx in advance.
--
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.
[algogeeks] Re: Removing same character(s) in a group
After first iteration, adjacent similar characters are converted to
get a single character
After second iteration, similar adjacent strings of length 2 in the
remaining string are replaced with single string of length 2
After third iteration, similar adjacent strings of length 3 in the
remaining string are replaced with single string of length 3
Hope I have clarified
On Dec 13, 10:26 am, atul anand atul.87fri...@gmail.com wrote:
well 1st part can be done of removing similar character ,
for the 2nd iteration where you want to remove continuous duplicate sub
string then i guess this can be done :-
for example :-
input : aabbabc
1st iteration : ababc
for 2nd iteration consider queue
1) maintain front value inserted int the queue in a variable :
now queue will have : ba : front = a
for i=3, front == str[i];
start=i;
while ( dequeue() != NULL)
{
val=dequeue();
if(val == str[i])
{
i++;
}
}
if(isDequeueEmpty())
{
//we know that from start to i is a repeated substr and should be
removed.
}
On Mon, Dec 12, 2011 at 7:52 PM, top coder topcode...@gmail.com wrote:
For example if aabbabc is given as input after first iteration, it
should be ababc and after that it should become abc. if aabbcabc is
given it should give abcabc after first interation, no change in
second iteration and abc after third iteration.
--
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.- 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.
[algogeeks] Re: Nice question
@Amir: Presumably, since these are digits in a number, they are bounded on the bottom by 0 and on the top by radix-1. So in decimal, if a digit is 7 and the absolute difference between it and the next digit is 3, there is only one possibility for the next digit, 7-3 = 4, since 7+3 is too large. So only some subset of the 2^(n-1) combinations of addition and subtraction may be possible. Dave On Dec 13, 4:15 am, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: actually there are infinite number of sequences that match it for example if the absolute differences are 3 2 5 1 one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5 7 2 3 and you can add any integer value to all elements and the result will still be valid actually you can start with any number and and then the second number will be equal to the first number that you chose plus/minus the first absolute difference and so on so if we are given the first element of the sequence there are 2^(n-1) ways to find a valid sequence because for each absolute difference we can either add the absolute difference to the last sequence element or subtract the absolute difference from it On Mon, Dec 12, 2011 at 9:01 PM, KAY amulya.manches...@gmail.com wrote: If for a number n digits long, the absolute difference between adjacent digits is given, how to find out the number of different numbers with these absolute differences ? for eg, if n=5 and the absolute differences are 3 2 5 1 then 1 possible number is 6 3 5 0 1 (because |6-3|=3,|3-5|=2 and so on...) How many such numbers will be there? -- 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] MYSIS AND DRISHTI-SOFT
which other group u people are talking about, i would like to join that group. On Tue, Dec 13, 2011 at 9:21 PM, sunny agrawal sunny816.i...@gmail.comwrote: @aayush Lots of member are here but that doesn't mean that you should start posting the things which are strictly banned on this group. I hope you will take care next time while posting anything in this group. On Tue, Dec 13, 2011 at 7:40 PM, rahul sharma rahul23111...@gmail.comwrote: On Tue, Dec 13, 2011 at 3:21 PM, hary rathor harry.rat...@gmail.comwrote: aal puzzle from techinterview. more then 50 % came from there . -- 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. @aayush all the memebers approx. have joined both the groups -- 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. V 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. -- * Regards* *The Coder* *Life is a Game. The more u play, the more u win, the more u win , the more successfully u play* -- 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] Suggest Algo for this Question
O(k) in the worst-case , then i guess it would better to use median-of median algo to find element at rank k. and comparing with x. or we can us hashtable to solve this. On Tue, Dec 13, 2011 at 3:23 PM, Ankur Garg ankurga...@gmail.com wrote: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. This question was also asked in Amazon -- 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.
[algogeeks] Re: Nice question
The following is a dynamic programming solution to this problem.
It builds up an array num[i][j] such that num[i][j] is the number of
combinations of digits starting with digit j at position i.
The answer is the sum of num[1][1]..num[9][1].
#include stdio.h
int main(int argc, char* argv[])
{
int n, i, j;
int adj[10];
int num[10][11];
scanf(%d, n);
for(i = 1; i n; ++i)
scanf(%d, adj[i]);
for(i = 0; i 10; ++i)
num[i][n] = 1;
for(j = n-1; j; --j)
{
for(i = 0; i 10; ++i)
{
num[i][j] = 0;
if ((i - adj[j]) = 0) num[i][j] = num[i-adj[j]][j+1];
if ((i + adj[j]) 10) num[i][j] += num[i+adj[j]][j+1];
}
}
j = 0;
for(i = 1; i 10; ++i)
j += num[i][1];
printf(%d\n, j);
return 0;
}
On Dec 12, 11:31 am, KAY amulya.manches...@gmail.com wrote:
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1 (because |6-3|=3,|3-5|=2 and so on...)
How many such numbers will be there?
--
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.
[algogeeks] find numbers if pair wise sums are given
If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 4 5 7 10 12 13 o/p: 1 3 4 9 -- 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] MYSIS AND DRISHTI-SOFT
http://groups.google.com/group/interview-street On Tue, Dec 13, 2011 at 10:19 PM, tech coder techcoderonw...@gmail.comwrote: which other group u people are talking about, i would like to join that group. On Tue, Dec 13, 2011 at 9:21 PM, sunny agrawal sunny816.i...@gmail.comwrote: @aayush Lots of member are here but that doesn't mean that you should start posting the things which are strictly banned on this group. I hope you will take care next time while posting anything in this group. On Tue, Dec 13, 2011 at 7:40 PM, rahul sharma rahul23111...@gmail.comwrote: On Tue, Dec 13, 2011 at 3:21 PM, hary rathor harry.rat...@gmail.comwrote: aal puzzle from techinterview. more then 50 % came from there . -- 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. @aayush all the memebers approx. have joined both the groups -- 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. V 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. -- * Regards* *The Coder* *Life is a Game. The more u play, the more u win, the more u win , the more successfully u play* -- 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. V 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.
[algogeeks] Re: Nice question
The following is a dynamic programming solution to this problem.
It builds up an array num[i][j] such that num[i][j] is the number of
combinations of digits starting with digit j at position i.
The answer is the sum of num[1][1]..num[9][1].
#include stdio.h
int main(int argc, char* argv[])
{
int n, i, j;
int adj[10];
int num[10][11];
scanf(%d, n);
for(i = 1; i n; ++i)
scanf(%d, adj[i]);
for(i = 0; i 10; ++i)
num[i][n] = 1;
for(j = n-1; j; --j)
{
for(i = 0; i 10; ++i)
{
num[i][j] = 0;
if ((i - adj[j]) = 0) num[i][j] = num[i-
adj[j]][j+1];
if (adj[j] ((i + adj[j]) 10)) num[i][j] +=
num[i+adj[j]][j+1];
}
}
j = 0;
for(i = 1; i 10; ++i)
j += num[i][1];
printf(%d\n, j);
return 0;
}
On Dec 12, 11:31 am, KAY amulya.manches...@gmail.com wrote:
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1 (because |6-3|=3,|3-5|=2 and so on...)
How many such numbers will be there?
--
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: Nice question
I tried the problem and written the code for it . it is in java. it is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832 36498 47945
47943 41389 41387 58612 52498 69723 69721 63167 63165 74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com wrote:
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in decimal,
if a digit is 7 and the absolute difference between it and the next
digit is 3, there is only one possibility for the next digit, 7-3 = 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5 7 2 3
and you can add any integer value to all elements and the result will
still
be valid
actually you can start with any number and and then the second number
will
be equal to the first number that you chose plus/minus the first absolute
difference and so on
so if we are given the first element of the sequence there are 2^(n-1)
ways
to find a valid sequence because for each absolute difference we can
either
add the absolute difference to the last sequence element or subtract the
absolute difference from it
On Mon, Dec 12, 2011 at 9:01 PM, KAY amulya.manches...@gmail.com
wrote:
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1(because |6-3|=3,|3-5|=2 and so on...)
How many such numbers will be there?
--
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.
--
*
Regards*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win , the
more successfully u play*
--
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.
[algogeeks] Re: Nice question
One other observation: if any of the absolute differences was zero, it
would print the same number more than once.
Your algorithm is fine for n=5, but as n gets larger, the execution
time increases exponentially. The dynamic programming algorithm is
O(n).
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com wrote:
I tried the problem and written the code for it . it is in java. it is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832 36498 47945
47943 41389 41387 58612 52498 69723 69721 63167 63165 74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com wrote:
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in decimal,
if a digit is 7 and the absolute difference between it and the next
digit is 3, there is only one possibility for the next digit, 7-3 = 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5 7 2 3
and you can add any integer value to all elements and the result will
still
be valid
actually you can start with any number and and then the second number
will
be equal to the first number that you chose plus/minus the first absolute
difference and so on
so if we are given the first element of the sequence there are 2^(n-1)
ways
to find a valid sequence because for each absolute difference we can
either
add the absolute difference to the last sequence element or subtract the
absolute difference from it
On Mon, Dec 12, 2011 at 9:01 PM, KAY amulya.manches...@gmail.com
wrote:
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1 (because |6-3|=3,|3-5|=2 and so on...)
How many such numbers will be there?
--
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.
--
*
Regards*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win , the
more successfully u play*
--
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: Nice question
thanks don , i got it , it was due the condition in if expression .
modified code
i have highlighted the change
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};
for(int num=1;num=9;num++)
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o=0)
// change done
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
output is
14612 14610 14278 14276 25723 25721 25389 25387 36834 36832 36498
30278 30276 47945 47943 47501 41389 41387 58612 58610 52498
52056 52054 69723 69721 63501 63167 63165 74612 74610 74278
74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 1 second)
now it's ok DON
On Wed, Dec 14, 2011 at 12:50 AM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and 52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com wrote:
I tried the problem and written the code for it . it is in java. it is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832 36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165 74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com wrote:
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in decimal,
if a digit is 7 and the absolute difference between it and the next
digit is 3, there is only one possibility for the next digit, 7-3 = 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5 7 2
3
and you can add any integer value to all elements and the result will
still
be valid
actually you can start with any number and and then the second number
will
be equal to the first number that you chose plus/minus the first
absolute
difference and so on
so if we are given the first element of the sequence there are
2^(n-1)
ways
to find a valid sequence because for each absolute difference we can
either
add the absolute difference to the last sequence element or subtract
the
absolute difference from it
On Mon, Dec 12, 2011 at 9:01 PM, KAY amulya.manches...@gmail.com
wrote:
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1(because |6-3|=3,|3-5|=2 and so on...)
How many such numbers will be there?
--
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.
Re: [algogeeks] Re: Nice question
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k l m ...
(w(i) x w(j) x w(k) x w(l) x.)
Now algo will be to scan the given abs diff and multiply the w(i) for each
absdiff .
int calculate_possible_nums(int absdiff[], int len){
int ways[]={10, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1};
int numways=1;
for ( i=0; i len; i++){
numways = numways * ways[absdiff[i]];
}
return numways;
}
-Moheed
'If a man neglects education, he walks lame to the end of his life.'
On Tue, Dec 13, 2011 at 11:20 PM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and 52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com wrote:
I tried the problem and written the code for it . it is in java. it is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832 36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165 74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com wrote:
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in decimal,
if a digit is 7 and the absolute difference between it and the next
digit is 3, there is only one possibility for the next digit, 7-3 = 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5 7 2
3
and you can add any integer value to all elements and the result will
still
be valid
actually you can start with any number and and then the second number
will
be equal to the first number that you chose plus/minus the first
absolute
difference and so on
so if we are given the first element of the sequence there are
2^(n-1)
ways
to find a valid sequence because for each absolute difference we can
either
add the absolute difference to the last sequence element or subtract
the
absolute difference from it
On Mon, Dec 12, 2011 at 9:01 PM, KAY amulya.manches...@gmail.com
wrote:
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1(because |6-3|=3,|3-5|=2 and so on...)
How many such numbers will be there?
--
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.
--
*
Regards*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win , the
more successfully u play*
--
You
Re: [algogeeks] find numbers if pair wise sums are given
i am not sure , but this came to me when i first read it here is the idea:- given : 4 5 7 10 12 13 4 should be there boz it is the least. next is 5 , 5-4 =1 which is less that 4 , so 1 should be there next is 7 , 7-4 = 3 which is less than 4 , so 3 should be there next is 10 , 10-4 = 6 which is greater then 4 , so add previous found elements i.e 1,3,4 add them 1+3+4 = 8 , add 1 to 8 = 9 now check ,can we use this number(i.e 9 ) and previous found elements ( 1,3,4) to form 10 ( 9 +1) : yes - so 9 should be there next is 12 , 12-4 = 8 ( but now greatest element among 1,3,4,9 is 9) and 8 9 ,so skip; next is 13 , 13-4 = 9 same reason for skipping as for number 12 before. On Tue, Dec 13, 2011 at 10:28 PM, top coder topcode...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 4 5 7 10 12 13 o/p: 1 3 4 9 -- 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.
[algogeeks] Re: Nice question
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad mohe...@gmail.com wrote:
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k l m ...
(w(i) x w(j) x w(k) x w(l) x.)
Now algo will be to scan the given abs diff and multiply the w(i) for each
absdiff .
int calculate_possible_nums(int absdiff[], int len){
int ways[]={10, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1};
int numways=1;
for ( i=0; i len; i++){
numways = numways * ways[absdiff[i]];
}
return numways;}
-Moheed
'If a man neglects education, he walks lame to the end of his life.'
On Tue, Dec 13, 2011 at 11:20 PM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and 52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com wrote:
I tried the problem and written the code for it . it is in java. it is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832 36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165 74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com wrote:
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in decimal,
if a digit is 7 and the absolute difference between it and the next
digit is 3, there is only one possibility for the next digit, 7-3 = 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5 7 2
3
and you can add any integer value to all elements and the result will
still
be valid
actually you can start with any number and and then the second number
will
be equal to the first number that you chose plus/minus the first
absolute
difference and so on
so if we are given the first element of the sequence there are
2^(n-1)
ways
to find a valid sequence because for each absolute difference we can
either
add the absolute difference to the last sequence element or subtract
the
absolute difference from it
On Mon, Dec 12, 2011 at 9:01 PM, KAY amulya.manches...@gmail.com
wrote:
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1 (because |6-3|=3,|3-5|=2 and so on...)
How many such numbers will be there?
--
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
Re: [algogeeks] Re: Nice question
When the difference is 0, the numbers will be repeated:
000, 111, 222, 333, 444, 555, 666, 777, 888, 999 but only these are
possible.
Gaurav
On Tue, Dec 13, 2011 at 10:47 AM, Don dondod...@gmail.com wrote:
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad mohe...@gmail.com wrote:
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k l m
...
(w(i) x w(j) x w(k) x w(l) x.)
Now algo will be to scan the given abs diff and multiply the w(i) for
each
absdiff .
int calculate_possible_nums(int absdiff[], int len){
int ways[]={10, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1};
int numways=1;
for ( i=0; i len; i++){
numways = numways * ways[absdiff[i]];
}
return numways;}
-Moheed
'If a man neglects education, he walks lame to the end of his life.'
On Tue, Dec 13, 2011 at 11:20 PM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and 52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com wrote:
I tried the problem and written the code for it . it is in java. it
is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible
initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832 36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165 74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com
wrote:
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in
decimal,
if a digit is 7 and the absolute difference between it and the next
digit is 3, there is only one possibility for the next digit, 7-3
= 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5
7 2
3
and you can add any integer value to all elements and the result
will
still
be valid
actually you can start with any number and and then the second
number
will
be equal to the first number that you chose plus/minus the first
absolute
difference and so on
so if we are given the first element of the sequence there are
2^(n-1)
ways
to find a valid sequence because for each absolute difference we
can
either
add the absolute difference to the last sequence element or
subtract
the
absolute difference from it
On Mon, Dec 12, 2011 at 9:01 PM, KAY
amulya.manches...@gmail.com
wrote:
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of
different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1(because |6-3|=3,|3-5|=2 and so on...)
How many such numbers will be there?
--
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
Re: [algogeeks] find numbers if pair wise sums are given
@atul: Suppose the input is :(7,8,9) So output should be (3,4,5) then ur approach is not giving the answers.. Regards, Sayan On Tue, Dec 13, 2011 at 11:51 PM, atul anand atul.87fri...@gmail.comwrote: i am not sure , but this came to me when i first read it here is the idea:- given : 4 5 7 10 12 13 4 should be there boz it is the least. next is 5 , 5-4 =1 which is less that 4 , so 1 should be there next is 7 , 7-4 = 3 which is less than 4 , so 3 should be there next is 10 , 10-4 = 6 which is greater then 4 , so add previous found elements i.e 1,3,4 add them 1+3+4 = 8 , add 1 to 8 = 9 now check ,can we use this number(i.e 9 ) and previous found elements ( 1,3,4) to form 10 ( 9 +1) : yes - so 9 should be there next is 12 , 12-4 = 8 ( but now greatest element among 1,3,4,9 is 9) and 8 9 ,so skip; next is 13 , 13-4 = 9 same reason for skipping as for number 12 before. On Tue, Dec 13, 2011 at 10:28 PM, top coder topcode...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 4 5 7 10 12 13 o/p: 1 3 4 9 -- 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: Nice question
I am just trying to understand the number of ways we can form this number,
lets say d is the absolute difference between the numbers and the length of
the numbers is n. Lets say we are considering base 10 numbers, so lets say
radix r = 10.
if you try to see all the comparisons, here is what holds:
for d = 0, possible 2 digit numbers are ( r - d ) x 2 .
For example if n = 2 the possible 2 digit numbers are (10 -2) x 2 = 16
the only place we have to be careful is when d = 0, because then both the
digits will be same and we will have to divide it by the number of digits
because 11 and 11 are both same if we flip the digits. So according to the
logic, if lets say we have the below difference between numbers:
3 2 5 1 so the total number of numbers possible are (10-3) x 2 x (10- 2) x
2 x (10 -5 ) x 2 x (10 - 1 ) x 2
In case when you have 0 0 0 as the difference, possible combinations are
(10 - 0) x 2 / 2 x 1 way x 1 way = 10 ways
Gaurav
On Tue, Dec 13, 2011 at 10:55 AM, Gaurav Kumar gkuma...@gmail.com wrote:
When the difference is 0, the numbers will be repeated:
000, 111, 222, 333, 444, 555, 666, 777, 888, 999 but only these are
possible.
Gaurav
On Tue, Dec 13, 2011 at 10:47 AM, Don dondod...@gmail.com wrote:
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad mohe...@gmail.com wrote:
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k l m
...
(w(i) x w(j) x w(k) x w(l) x.)
Now algo will be to scan the given abs diff and multiply the w(i) for
each
absdiff .
int calculate_possible_nums(int absdiff[], int len){
int ways[]={10, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1};
int numways=1;
for ( i=0; i len; i++){
numways = numways * ways[absdiff[i]];
}
return numways;}
-Moheed
'If a man neglects education, he walks lame to the end of his life.'
On Tue, Dec 13, 2011 at 11:20 PM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and 52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com wrote:
I tried the problem and written the code for it . it is in java. it
is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible
initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int
i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832 36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165
74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com
wrote:
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in
decimal,
if a digit is 7 and the absolute difference between it and the
next
digit is 3, there is only one possibility for the next digit, 7-3
= 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8
5 7 2
3
and you can add any integer value to all elements and the
result will
still
be valid
actually you can start with any number and and then the second
number
will
be equal to the first number that you chose plus/minus the first
absolute
difference and so on
so if we are given
Re: [algogeeks] Suggest Algo for this Question
Why can't we keep removing the minimum element each time and compare it with x? This should take O(k) time since in a Min heap, the minimum element can be removed in O(1) time? Am I missing something? On Tue, Dec 13, 2011 at 8:43 AM, atul anand atul.87fri...@gmail.com wrote: O(k) in the worst-case , then i guess it would better to use median-of median algo to find element at rank k. and comparing with x. or we can us hashtable to solve this. On Tue, Dec 13, 2011 at 3:23 PM, Ankur Garg ankurga...@gmail.com wrote: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. This question was also asked in Amazon -- 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.
[algogeeks] Re: Nice question
That gives an answer of 40,320, but the correct answer is 39. You
can't multiply all of those values together and expect to get the
right answer. There are not 14 possible values for the first digit,
and if there were, for any particular value of the first digit there
are not 16 possible values for the second digit, there are only one or
two. Your mistake is treating each digit as if it is independent of
the rest of the number, but it is not. Try several input cases and see
if your method gives a reasonable result. For example, if n=10 and the
absolute differences are {6,6,6,6,6,6,6,6,6}, by your thinking there
would be 4^9=262,144 possible numbers. In reality, the only possible
numbers are
1717171717
2828282828
3939393939
6060606060
7171717171
8282828282
9393939393
If your algorithm gives an answer other than 7, keep working on it.
Don
On Dec 13, 1:46 pm, Gaurav Kumar gkuma...@gmail.com wrote:
3 2 5 1 so the total number of numbers possible are (10-3) x 2 x (10- 2) x
2 x (10 -5 ) x 2 x (10 - 1 ) x 2
In case when you have 0 0 0 as the difference, possible combinations are
(10 - 0) x 2 / 2 x 1 way x 1 way = 10 ways
Gaurav
On Tue, Dec 13, 2011 at 10:55 AM, Gaurav Kumar gkuma...@gmail.com wrote:
When the difference is 0, the numbers will be repeated:
000, 111, 222, 333, 444, 555, 666, 777, 888, 999 but only these are
possible.
Gaurav
On Tue, Dec 13, 2011 at 10:47 AM, Don dondod...@gmail.com wrote:
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad mohe...@gmail.com wrote:
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k l m
...
(w(i) x w(j) x w(k) x w(l) x.)
Now algo will be to scan the given abs diff and multiply the w(i) for
each
absdiff .
int calculate_possible_nums(int absdiff[], int len){
int ways[]={10, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1};
int numways=1;
for ( i=0; i len; i++){
numways = numways * ways[absdiff[i]];
}
return numways;}
-Moheed
'If a man neglects education, he walks lame to the end of his life.'
On Tue, Dec 13, 2011 at 11:20 PM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and 52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com wrote:
I tried the problem and written the code for it . it is in java. it
is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible
initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int
i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832 36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165
74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com
wrote:
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in
decimal,
if a digit is 7 and the absolute difference between it and the
next
digit is 3, there is only one possibility for the next digit, 7-3
= 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8
5 7 2
3
and you can add any integer value to all
Re: [algogeeks] Re: Nice question
On Tue, Dec 13, 2011 at 12:40 PM, Don dondod...@gmail.com wrote:
That gives an answer of 40,320, but the correct answer is 39. You
can't multiply all of those values together and expect to get the
right answer. There are not 14 possible values for the first digit,
and if there were, for any particular value of the first digit there
are not 16 possible values for the second digit, there are only one or
two. Your mistake is treating each digit as if it is independent of
the rest of the number, but it is not. Try several input cases and see
if your method gives a reasonable result. For example, if n=10 and the
absolute differences are {6,6,6,6,6,6,6,6,6}, by your thinking there
would be 4^9=262,144 possible numbers. In reality, the only possible
numbers are
1717171717
2828282828
3939393939
6060606060
7171717171
8282828282
9393939393
If your algorithm gives an answer other than 7, keep working on it.
Don
On Dec 13, 1:46 pm, Gaurav Kumar gkuma...@gmail.com wrote:
3 2 5 1 so the total number of numbers possible are (10-3) x 2 x (10- 2)
x
2 x (10 -5 ) x 2 x (10 - 1 ) x 2
In case when you have 0 0 0 as the difference, possible combinations are
(10 - 0) x 2 / 2 x 1 way x 1 way = 10 ways
Gaurav
On Tue, Dec 13, 2011 at 10:55 AM, Gaurav Kumar gkuma...@gmail.com
wrote:
When the difference is 0, the numbers will be repeated:
000, 111, 222, 333, 444, 555, 666, 777, 888, 999 but only these are
possible.
Gaurav
On Tue, Dec 13, 2011 at 10:47 AM, Don dondod...@gmail.com wrote:
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad mohe...@gmail.com wrote:
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k
l m
...
(w(i) x w(j) x w(k) x w(l) x.)
Now algo will be to scan the given abs diff and multiply the w(i)
for
each
absdiff .
int calculate_possible_nums(int absdiff[], int len){
int ways[]={10, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1};
int numways=1;
for ( i=0; i len; i++){
numways = numways * ways[absdiff[i]];
}
return numways;}
-Moheed
'If a man neglects education, he walks lame to the end of his life.'
On Tue, Dec 13, 2011 at 11:20 PM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and
52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com
wrote:
I tried the problem and written the code for it . it is in
java. it
is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible
initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int
i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832
36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165
74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com
wrote:
@Amir: Presumably, since these are digits in a number, they
are
bounded on the bottom by 0 and on the top by radix-1. So in
decimal,
if a digit is 7 and the absolute difference between it and the
next
digit is 3, there is only one possibility for the next digit,
7-3
= 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite
Re: [algogeeks] Re: Nice question
Thanks for pointing out the issue with my logic. What I am wondering is
what is the general solution to finding the number of possible numbers? Is
the only way is to try these combinations? Please share if you know.
Gaurav
On Tue, Dec 13, 2011 at 1:56 PM, Gaurav Kumar gkuma...@gmail.com wrote:
On Tue, Dec 13, 2011 at 12:40 PM, Don dondod...@gmail.com wrote:
That gives an answer of 40,320, but the correct answer is 39. You
can't multiply all of those values together and expect to get the
right answer. There are not 14 possible values for the first digit,
and if there were, for any particular value of the first digit there
are not 16 possible values for the second digit, there are only one or
two. Your mistake is treating each digit as if it is independent of
the rest of the number, but it is not. Try several input cases and see
if your method gives a reasonable result. For example, if n=10 and the
absolute differences are {6,6,6,6,6,6,6,6,6}, by your thinking there
would be 4^9=262,144 possible numbers. In reality, the only possible
numbers are
1717171717
2828282828
3939393939
6060606060
7171717171
8282828282
9393939393
If your algorithm gives an answer other than 7, keep working on it.
Don
On Dec 13, 1:46 pm, Gaurav Kumar gkuma...@gmail.com wrote:
3 2 5 1 so the total number of numbers possible are (10-3) x 2 x (10-
2) x
2 x (10 -5 ) x 2 x (10 - 1 ) x 2
In case when you have 0 0 0 as the difference, possible combinations are
(10 - 0) x 2 / 2 x 1 way x 1 way = 10 ways
Gaurav
On Tue, Dec 13, 2011 at 10:55 AM, Gaurav Kumar gkuma...@gmail.com
wrote:
When the difference is 0, the numbers will be repeated:
000, 111, 222, 333, 444, 555, 666, 777, 888, 999 but only these are
possible.
Gaurav
On Tue, Dec 13, 2011 at 10:47 AM, Don dondod...@gmail.com wrote:
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad mohe...@gmail.com wrote:
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k
l m
...
(w(i) x w(j) x w(k) x w(l) x.)
Now algo will be to scan the given abs diff and multiply the w(i)
for
each
absdiff .
int calculate_possible_nums(int absdiff[], int len){
int ways[]={10, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1};
int numways=1;
for ( i=0; i len; i++){
numways = numways * ways[absdiff[i]];
}
return numways;}
-Moheed
'If a man neglects education, he walks lame to the end of his
life.'
On Tue, Dec 13, 2011 at 11:20 PM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and
52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com
wrote:
I tried the problem and written the code for it . it is in
java. it
is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all
possible
initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int
i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832
36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165
74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave
dave_and_da...@juno.com
wrote:
@Amir: Presumably, since these are digits in a number, they
are
bounded on the bottom by 0 and on the top by radix-1. So in
decimal,
if a digit is 7 and the absolute difference between it and
the
next
digit is 3, there is only one possibility for the next
[algogeeks] Re: Nice question
Trying the combinations is not necessary. See my solution above.
Don
On Dec 13, 3:59 pm, Gaurav Kumar gkuma...@gmail.com wrote:
Thanks for pointing out the issue with my logic. What I am wondering is
what is the general solution to finding the number of possible numbers? Is
the only way is to try these combinations? Please share if you know.
Gaurav
On Tue, Dec 13, 2011 at 1:56 PM, Gaurav Kumar gkuma...@gmail.com wrote:
On Tue, Dec 13, 2011 at 12:40 PM, Don dondod...@gmail.com wrote:
That gives an answer of 40,320, but the correct answer is 39. You
can't multiply all of those values together and expect to get the
right answer. There are not 14 possible values for the first digit,
and if there were, for any particular value of the first digit there
are not 16 possible values for the second digit, there are only one or
two. Your mistake is treating each digit as if it is independent of
the rest of the number, but it is not. Try several input cases and see
if your method gives a reasonable result. For example, if n=10 and the
absolute differences are {6,6,6,6,6,6,6,6,6}, by your thinking there
would be 4^9=262,144 possible numbers. In reality, the only possible
numbers are
1717171717
2828282828
3939393939
6060606060
7171717171
8282828282
9393939393
If your algorithm gives an answer other than 7, keep working on it.
Don
On Dec 13, 1:46 pm, Gaurav Kumar gkuma...@gmail.com wrote:
3 2 5 1 so the total number of numbers possible are (10-3) x 2 x (10-
2) x
2 x (10 -5 ) x 2 x (10 - 1 ) x 2
In case when you have 0 0 0 as the difference, possible combinations are
(10 - 0) x 2 / 2 x 1 way x 1 way = 10 ways
Gaurav
On Tue, Dec 13, 2011 at 10:55 AM, Gaurav Kumar gkuma...@gmail.com
wrote:
When the difference is 0, the numbers will be repeated:
000, 111, 222, 333, 444, 555, 666, 777, 888, 999 but only these are
possible.
Gaurav
On Tue, Dec 13, 2011 at 10:47 AM, Don dondod...@gmail.com wrote:
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad mohe...@gmail.com wrote:
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k
l m
...
(w(i) x w(j) x w(k) x w(l) x.)
Now algo will be to scan the given abs diff and multiply the w(i)
for
each
absdiff .
int calculate_possible_nums(int absdiff[], int len){
int ways[]={10, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1};
int numways=1;
for ( i=0; i len; i++){
numways = numways * ways[absdiff[i]];
}
return numways;}
-Moheed
'If a man neglects education, he walks lame to the end of his
life.'
On Tue, Dec 13, 2011 at 11:20 PM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and
52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com
wrote:
I tried the problem and written the code for it . it is in
java. it
is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all
possible
initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int
i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832
36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165
74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave
dave_and_da...@juno.com
wrote:
@Amir: Presumably, since these are digits in a number,
Re: [algogeeks] find numbers if pair wise sums are given
hmmm i guess i screwed by taking least element as a part of the output set directly. On Wed, Dec 14, 2011 at 12:57 AM, sayan nayak sayanna...@gmail.com wrote: @atul: Suppose the input is :(7,8,9) So output should be (3,4,5) then ur approach is not giving the answers.. Regards, Sayan On Tue, Dec 13, 2011 at 11:51 PM, atul anand atul.87fri...@gmail.comwrote: i am not sure , but this came to me when i first read it here is the idea:- given : 4 5 7 10 12 13 4 should be there boz it is the least. next is 5 , 5-4 =1 which is less that 4 , so 1 should be there next is 7 , 7-4 = 3 which is less than 4 , so 3 should be there next is 10 , 10-4 = 6 which is greater then 4 , so add previous found elements i.e 1,3,4 add them 1+3+4 = 8 , add 1 to 8 = 9 now check ,can we use this number(i.e 9 ) and previous found elements ( 1,3,4) to form 10 ( 9 +1) : yes - so 9 should be there next is 12 , 12-4 = 8 ( but now greatest element among 1,3,4,9 is 9) and 8 9 ,so skip; next is 13 , 13-4 = 9 same reason for skipping as for number 12 before. On Tue, Dec 13, 2011 at 10:28 PM, top coder topcode...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 4 5 7 10 12 13 o/p: 1 3 4 9 -- 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] find numbers if pair wise sums are given
in above case we need to do some checking like in case when next element is 10; next elements is 10 10-4 = 6 , 6 4 add(1,3,4 ) = 8 8 10(required_element) , so add 1 to 8 = 9 and do same as mentioned but if sum( number_found_so_far ) required_num then add 1 to difference of required_num - least number . for example :- suppose in the same example if i add 15 in the end of given input now next elem 15 - 4 = 11 sum(1,3,4,9) = 17 15 17 , so add 1 to 11 = 12 and use this number(i.e 12 ) and element_found_so_far(i.e 1,3,4,9) to form 15 ( 12 + 3 ) : yes , so 12 should be there On Tue, Dec 13, 2011 at 11:51 PM, atul anand atul.87fri...@gmail.comwrote: i am not sure , but this came to me when i first read it here is the idea:- given : 4 5 7 10 12 13 4 should be there boz it is the least. next is 5 , 5-4 =1 which is less that 4 , so 1 should be there next is 7 , 7-4 = 3 which is less than 4 , so 3 should be there next is 10 , 10-4 = 6 which is greater then 4 , so add previous found elements i.e 1,3,4 add them 1+3+4 = 8 , add 1 to 8 = 9 now check ,can we use this number(i.e 9 ) and previous found elements ( 1,3,4) to form 10 ( 9 +1) : yes - so 9 should be there next is 12 , 12-4 = 8 ( but now greatest element among 1,3,4,9 is 9) and 8 9 ,so skip; next is 13 , 13-4 = 9 same reason for skipping as for number 12 before. On Tue, Dec 13, 2011 at 10:28 PM, top coder topcode...@gmail.com wrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 4 5 7 10 12 13 o/p: 1 3 4 9 -- 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: Cliched 'k' largest elements in billion numbers: Heaps or median-of-medians?
@Gene : considering m-of-m algo , one thing that worries me is that using m-of-m for huge data is not good bcoz when practically implementing it constant would be very large so as to make it work for O(N) here is the reason why is not a good approach for huge data :- reccurence eqn for m-of-m is :- T(n) = (c/5) n + (3/4)cn + theta(n) = (19/20)cn + theta(n) = c.n - ( (1/20)cn - theta(n)) now here the residual part i.e = (1/20)cn - theta(n) c should be sufficient large at least 20 times larger that theta(n) so as to make it work for O(n). so for huge data input this is a not a good approach hence heap would win over this. On Mon, Dec 12, 2011 at 3:19 PM, Gene gene.ress...@gmail.com wrote: If N is big enough so that all data will not fit in main memory and k is small enough so that the k top elements fit in memory, then the heap is likely to be the best.This is because disk access is so incredibly slow compared to memory access: A few milliseconds (10^-3) vs. a few nanoseconds (10^-9), a factor of a million. The heap-based algorithms need to touch the disk only once per data item. It would be difficult if not impossible to implement m-of-m that achieves this. On the other hand, if both k and N are so big that this many data do not fit in memory, then the m-of-m algorithm will probably win. I say this because Quicksort is known to have better performance than heapsort, including memory access patterns on large data. (In fact heaps can have terrible access patterns if implemented in the typical textbook way where the children of a[i] are at a[2*i] and a[2*i+1].) This is a strong indicator that m-of-m (which is at heart a Quicksort that stops early) will do better than keeping the top k elements in a heap for this problem when both algorithms need disk i/o. Needing to find the top 10 billion out of a few trillion data is actually a realistic problem in some areas of research. So this is a useful thing to discuss. Gene On Dec 11, 8:11 pm, bharath sriram bharath.sri...@gmail.com wrote: Hey group This is kind of a cliched question but given a file with billion numbers and the task is to compute 'k' largest numbers from this file, what approach is preferred? 1) Using heaps 2) Using Median-of-median algorithm. Have read few links which prefer heaps but clearly median of median algorithm has a linear time complexity and don't see how its any less if not better than using heaps? Any thought? -- 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: Nice question
Thanks Don for pointing it out. It will not work [the second and
consecutive abs-diffs are not mutually exclusive].
However, here are the 10 possible numbers that will work for n=3 and
absdiff={0,0}:
0 0 0
1 1 1
2 2 2
--
8 8 8
9 9 9
-Moheed
'If a man neglects education, he walks lame to the end of his life.'
On Wed, Dec 14, 2011 at 12:17 AM, Don dondod...@gmail.com wrote:
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad mohe...@gmail.com wrote:
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k l m
...
(w(i) x w(j) x w(k) x w(l) x.)
Now algo will be to scan the given abs diff and multiply the w(i) for
each
absdiff .
int calculate_possible_nums(int absdiff[], int len){
int ways[]={10, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1};
int numways=1;
for ( i=0; i len; i++){
numways = numways * ways[absdiff[i]];
}
return numways;}
-Moheed
'If a man neglects education, he walks lame to the end of his life.'
On Tue, Dec 13, 2011 at 11:20 PM, Don dondod...@gmail.com wrote:
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and 52056.
Don
On Dec 13, 11:37 am, tech coder techcoderonw...@gmail.com wrote:
I tried the problem and written the code for it . it is in java. it
is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolute differences
int digit[]={3,2,5,1};
for(int num=1;num=9;num++) // call with all possible
initial
numbers
findNumber(digit,4,num,0,num);
}
public static void findNumber(int digit[],int n,int num,int i,int
oldDigit)
{
if(i==n)
{
System.out.print(num+ );
return;
}
{
int o=digit[i]+oldDigit;
if(o10)
findNumber(digit,n,10*num+o,i+1,o);
o=oldDigit-digit[i];
if(o0)
findNumber(digit,n,10*num+o,i+1,o);
}
}
}
and here is the output
14612 14278 14276 25723 25721 25389 25387 36834 36832 36498
47945
47943 41389 41387 58612 52498 69723 69721 63167 63165 74612
74278 74276 85723 85721 85389 85387 96834 96832 96498
BUILD SUCCESSFUL (total time: 0 seconds)
On Tue, Dec 13, 2011 at 11:11 PM, Dave dave_and_da...@juno.com
wrote:
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in
decimal,
if a digit is 7 and the absolute difference between it and the next
digit is 3, there is only one possibility for the next digit, 7-3
= 4,
since 7+3 is too large. So only some subset of the 2^(n-1)
combinations of addition and subtraction may be possible.
Dave
On Dec 13, 4:15 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5
7 2
3
and you can add any integer value to all elements and the result
will
still
be valid
actually you can start with any number and and then the second
number
will
be equal to the first number that you chose plus/minus the first
absolute
difference and so on
so if we are given the first element of the sequence there are
2^(n-1)
ways
to find a valid sequence because for each absolute difference we
can
either
add the absolute difference to the last sequence element or
subtract
the
absolute difference from it
On Mon, Dec 12, 2011 at 9:01 PM, KAY
amulya.manches...@gmail.com
wrote:
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of
different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1(because |6-3|=3,|3-5|=2 and so on...)
How many such numbers will be there?
--
You received this message because you are subscribed to the
Google
Re: [algogeeks] Suggest Algo for this Question
@gaurav : you need to first build heap and then maintain heap property ever time you remove element.so this would take O(n logn ). On Wed, Dec 14, 2011 at 1:38 AM, Gaurav Kumar gkuma...@gmail.com wrote: Why can't we keep removing the minimum element each time and compare it with x? This should take O(k) time since in a Min heap, the minimum element can be removed in O(1) time? Am I missing something? On Tue, Dec 13, 2011 at 8:43 AM, atul anand atul.87fri...@gmail.comwrote: O(k) in the worst-case , then i guess it would better to use median-of median algo to find element at rank k. and comparing with x. or we can us hashtable to solve this. On Tue, Dec 13, 2011 at 3:23 PM, Ankur Garg ankurga...@gmail.com wrote: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. This question was also asked in Amazon -- 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] find numbers if pair wise sums are given
how is the case taken of when 2 pairs add to the same sum?... On Tue, Dec 13, 2011 at 11:35 AM, atul anand atul.87fri...@gmail.comwrote: hmmm i guess i screwed by taking least element as a part of the output set directly. On Wed, Dec 14, 2011 at 12:57 AM, sayan nayak sayanna...@gmail.comwrote: @atul: Suppose the input is :(7,8,9) So output should be (3,4,5) then ur approach is not giving the answers.. Regards, Sayan On Tue, Dec 13, 2011 at 11:51 PM, atul anand atul.87fri...@gmail.comwrote: i am not sure , but this came to me when i first read it here is the idea:- given : 4 5 7 10 12 13 4 should be there boz it is the least. next is 5 , 5-4 =1 which is less that 4 , so 1 should be there next is 7 , 7-4 = 3 which is less than 4 , so 3 should be there next is 10 , 10-4 = 6 which is greater then 4 , so add previous found elements i.e 1,3,4 add them 1+3+4 = 8 , add 1 to 8 = 9 now check ,can we use this number(i.e 9 ) and previous found elements ( 1,3,4) to form 10 ( 9 +1) : yes - so 9 should be there next is 12 , 12-4 = 8 ( but now greatest element among 1,3,4,9 is 9) and 8 9 ,so skip; next is 13 , 13-4 = 9 same reason for skipping as for number 12 before. On Tue, Dec 13, 2011 at 10:28 PM, top coder topcode...@gmail.comwrote: If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 4 5 7 10 12 13 o/p: 1 3 4 9 -- 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. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- 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.
[algogeeks] Re: Suggest Algo for this Question
@Atul: The initial heap is given. You have to maintain the heap property as k elements are removed, which is O(k log n). This does not satisfy the original request for an algorithm that is O(k) in the worst-case, independent of the size of the heap. Dave On Dec 13, 10:31 pm, atul anand atul.87fri...@gmail.com wrote: @gaurav : you need to first build heap and then maintain heap property ever time you remove element.so this would take O(n logn ). On Wed, Dec 14, 2011 at 1:38 AM, Gaurav Kumar gkuma...@gmail.com wrote: Why can't we keep removing the minimum element each time and compare it with x? This should take O(k) time since in a Min heap, the minimum element can be removed in O(1) time? Am I missing something? On Tue, Dec 13, 2011 at 8:43 AM, atul anand atul.87fri...@gmail.comwrote: O(k) in the worst-case , then i guess it would better to use median-of median algo to find element at rank k. and comparing with x. or we can us hashtable to solve this. On Tue, Dec 13, 2011 at 3:23 PM, Ankur Garg ankurga...@gmail.com wrote: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. This question was also asked in Amazon -- 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.
