Just solved it.. The approach is same as Don's but starting from the
front... Hence, penning it down..
Let F(i) be defined as the no. of integers that are possible to be
formed using the first 'i' integral differences..
Then F(i+1) = No. of integers from set F(i) where the units place >= 'i
+1' integral difference // as a result of subtracting 'i+1' integral
difference from the units place
+
No. of integers from set F(i) where the units
place <= [ 9 - ('i+1' integral difference)] // as a result of adding
'i+1' integral difference to the units place
To keep track of all the integers for F(i) which end at values 0 to 9,
lets take an array A[10], where A[k] represents the no. of integers
which end at value 'K' for the first 'i' integral differences.
Here, 0 <= k <= 9.
So to start with A[10] = {0,1,1,1,1,1,1,1,1,9} ... A[0] is 0 because
an integer cannot start with value 0.
Lets also take an array B[10] to hold the intermediate calculated
values. B[10] is initialized to 0.
For ex- say we need to generate count of all nos. where the difference
array is {1, 4}.
Units place val = 0 1 2 3 4 5 6 7 8
9
A[10] = 0 1 1 1 1 1 1 1
1 1
B[10] = 0 0 0 0 0 0 0 0
0 0
For difference 1, on subtracting from the units place, // adding the
values from A[10] to B[10].
B[10] = 1 1 1 1 1 1 1 1
1 0 // if analyzed this is nothing but left shifting the array
A[10] by 1 unit and with trailing 0's.
For difference 1, on adding to the units place, // adding the values
from A[10] to B[10].
B[10] = 1 1 1 1 1 1 1 1
1 0
+ 0 1 1 1 1 1 1 1
1 1 // if analyzed this is nothing but right shifting the array
A[10] by 1 unit and with leading 0's.
= 1 2 2 2 2 2 2 2
2 1 // The sum of this array will give u the no. of 2 digit
integers that can be formed where the difference is 1.
Now. copying B[10] to A[10] and initializing B[10] = 0, for next
iteration..
A[10] = 1 2 2 2 2 2 2 2
2 1 // The sum of this array will give u the no. of 2 digit
integers that can be formed where the difference is 1.
For difference 4, on subtracting from the units place, // adding the
values from A[10] to B[10].
B[10] = 2 2 2 2 2 1 0 0
0 0 // if analyzed this is nothing but left shifting the array
A[10] by 4 unit and with trailing 0's.
For difference 4, on adding to the units place, // adding the values
from A[10] to B[10].
B[10] = 2 2 2 2 2 1 0 0
0 0
+ 0 0 0 0 1 2 2 2
2 2 // if analyzed this is nothing but right shifting the array
A[10] by 4 unit and with leading 0's.
= 2 2 2 2 3 3 2
2 2 2 // The sum of this array will give u the no. of 3 digit
integers that can be formed where the difference is {1,4}.
Hence, the no. of integers that can formed with {1,4} is 22.
There is a special case where the difference is 0, and we need not
calculate B[10], as A[10] will be same for the next iteration..
--------------------------------------------
Let Diff[n] be the difference array,
A[0] = 0, B[0]=0;
for (int i = 1; i < 10; ++i)
A[i] =1; B[i] =0;
for (int i = 0; i < n; ++i)
{
int k = 0;
int diff = Diff[i];
if (diff != 0 )
{
for (int j = diff ; j < 10; ++j) // left shift
B[j - diff] += A[j];
for (int j = 0 ; j < 10 - diff ; ++ j) // right shift
B[j + diff] += A[j];
// Copying B[10] to A[10] and initializing B[10] = 0 for the
next iteration..
for (int j=0 ; j < 10; ++j)
{ A[j] = B[j]; B[j] = 0; }
}
}
int totalCount = 0;
for (int i = 0; i < 10; ++i)
totalCount += A[i];
On Dec 14, 11:11 am, Dave <dave_and_da...@juno.com> wrote:
> @Moheed: 0 is not a three-digit number. By convention, we do not print
> leading zeros except in the units position. Thus, there are only 9
> three digit numbers with absdiff={0,0}.
>
> Dave
>
> On Dec 13, 12:58 pm, Moheed Moheed Ahmad <mohe...@gmail.com> wrote:
>
>
>
>
>
>
>
> > 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(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.
--
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.
