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 <[email protected]> wrote: > > > On Tue, Dec 13, 2011 at 12:40 PM, Don <[email protected]> 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 <[email protected]> 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 <[email protected]> >> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> >> 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(o<10) >> > >> > > > findNumber(digit,n,10*num+o,i+1,o); >> > >> > > > o=oldDigit-digit[i]; >> > >> > > > if(o>0) >> > >> > > > 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 < >> [email protected]> >> > >> 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 >> > >> > > > > <[email protected]> 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 < >> > >> [email protected]> >> > >> > > > > 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 >> > >> [email protected]. >> > >> > > > > > > To unsubscribe from this group, send email to >> > >> > > > > > > [email protected]. >> > >> > > > > > > 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 >> [email protected]. >> > >> > > > > To unsubscribe from this group, send email to >> > >> > > > > [email protected]. >> > >> > > > > 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 [email protected]. >> > >> > > To unsubscribe from this group, send email to >> > >> > > [email protected]. >> > >> > > 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 [email protected]. >> > >> To unsubscribe from this group, send email to >> > >> [email protected]. >> > >> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
