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(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 <
> >> 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.
>
> >> > >> --
> >> > >> 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.
>
> ...
>
> read more »
--
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.
