Google Interview Question
Software DevelopersCountry: United States
Good idea to store the states! One small nit:
The for loop can be cleaner as follows:
for (int nextPossibleNumber: lengthTwoResults[prefixNumber])
{
// Have we calculated those results before?
count += getCount(nextPossibleNumber, n-1);
}
I thing all the things you tried to do in the for loop is already done before.
// Original method that is called
int countNumbers(int N)
{
int result[N]; // this works in latest C standard (or malloc/new)
int count=0; // passed by referenced into helper
countNumbersHelper(result, 0, N, count);
return count;
}
int countNumbersHelper(int result[], int posToFill, int N, int &count)
{
// if we have filled N digits into result, then up the count...
if(posToFill = N) {
count++;
return;
}
// if the result array still needs a digit to be filled into 'posToFille'
// ... try all possible digits
for( int i=0; i < 10; i++)
{
if(posToFill == 0 && i==0) continue; // first digit has to be non-zero
//skip if distance to prev. digit < 4
if( posToFill > 0 && abs(result[posToFill-1] , i ) < 4 ) continue;
// Try filling digit 'i' into result and recurse to fill remaining result[ ]
result[posToFill]=i;
countNumbersHelper(result, posToFill+1, N, count);
}
}
Nice logic.
#include <stdio.h>
int out[100];
int count;
void foo(int *out, int pos_to_fil, int size)
{
if (pos_to_fil == size) {
count++;
return;
}
int i;
for (i=0;i<=9;i++) {
if (pos_to_fil == 0 && i == 0)
continue;
if (pos_to_fil >0 && abs(out[pos_to_fil-1] -i) < 4)
continue;
out[pos_to_fil] = i;
foo(out, pos_to_fil + 1, size);
}
}
int main(void) {
foo(out, 0, 3);
printf("count %d\n", count);
return 0;
}
how many possible number your can get where each digit of the possible number is four bigger/smaller than the next digit
if n =3
then 159 is one possible number because the second digit i.e 5 is bigger than 1 by four and also 9 is bigger than second digit i.e 5 by 4.
other possible numbers could be 151,161,171,181,191,162,173 etc
public class CountNumbersNSmallerGreaterThanPrevAfter {
final static int[][] A = {
{}, // 0
{5, 6, 7, 8, 9}, // 1
{6, 7, 8, 9}, // 2
{7, 8, 9}, // 3
{8, 9}, // 4
{1, 9}, // 5
{1, 2}, // 6
{1, 2, 3}, // 7
{1, 2, 3, 4}, // 8
{1, 2, 3, 4, 5}, // 9
};
public static void main(String[] args) {
countNumbers("", 0, 5);
}
static int count = 0;
static void countNumbers(String prefix, int index, int n) {
if (index == 0) {
for (int i = 1; i <= 9; i++) {
countNumbers(prefix + i, index + 1, n);
}
} else {
if (index == n) {
System.out.println(prefix);
count++;
} else {
int prev = prefix.charAt(index - 1) - '0';
for (int k : A[prev]) {
countNumbers(prefix + k, index + 1, n);
}
}
}
}
}
Using Dyanmic programming.
If you know that you have N_{1,n} number finishing with 1 of length n ... N_{9,n} numbers finishing with 9 of length n, then for instance
N_{2,n+1} = N_{6,n}+N_{7,n}+N_{8,n} + N_{9,n}
public class countNumbers {
public static void main(String[] args) {
int n = 5;
int res = howMany( n );
System.out.println( res );
}
static int howMany( int n ){
int[][] tabRes = new int[n][9];
for( int i = 0 ; i < 9 ; i++) tabRes[0][i] = 1;
for( int i = 1 ; i < n ; i++){
for( int j = 0 ; j < 4 ; j++ ){
tabRes[ i ][ j ] = sumArray( tabRes , i - 1, 4 + j , 8 );
tabRes[ i ][ 8 - j ] = sumArray( tabRes , i - 1, 0 , 4-j);
}
tabRes[ i ][ 4 ] = tabRes[ i - 1][ 0 ] + tabRes[ i - 1][ 8 ];
}
return sumArray( tabRes , n-1 , 0 , 8 );
}
static int sumArray( int[][] array , int idxRow , int first , int last ){
int res = 0;
for( int i = first; i<= last ; i++){
res += array[ idxRow ][ i ];
}
return res ;
}
}
solution if we already calculate all number of length (n-1) ending with 0-9.
long improvedCount (int n) {
long arr[10], tmp[10], tot=0;
int i, j, k;
arr[0] = 0; // First number cannot be 0
tmp[0] = 0;
for (i =1; i<10; i++) {
arr[i] = 1; //all elements can occur 1 time in number of length 1
tmp[i] = 0;
}
for (i=1; i<n; i++) {
for (j=0; j<10; j++) {
for (k=0;k<10; k++) {
if (ABS(k-j) >=4)
tmp[j] += arr[k];
}
}
for (j=0; j<10; j++) {
arr[j] = tmp[j];
tmp[j] = 0;
}
}
tot = 0;
for (i=0; i<10; i++) {
tot += arr[i];
}
return (tot);
}
solution if we already calculate all number of length (n-1) ending with 0-9.
long improvedCount (int n) {
long arr[10], tmp[10], tot=0;
int i, j, k;
arr[0] = 0; // First number cannot be 0
tmp[0] = 0;
for (i =1; i<10; i++) {
arr[i] = 1; //all elements can occur 1 time in number of length 1
tmp[i] = 0;
}
for (i=1; i<n; i++) {
for (j=0; j<10; j++) {
for (k=0;k<10; k++) {
if (ABS(k-j) >=4)
tmp[j] += arr[k];
}
}
for (j=0; j<10; j++) {
arr[j] = tmp[j];
tmp[j] = 0;
}
}
tot = 0;
for (i=0; i<10; i++) {
tot += arr[i];
}
return (tot);
}
If we find all possible combination of number ending 0-9 with n-1 length, then we can calculate all possible combinations of bumber ending 0-9 with n length
long improvedCount (int n) {
long arr[10], tmp[10], tot=0;
int i, j, k;
arr[0] = 0; // First number cannot be 0
tmp[0] = 0;
for (i =1; i<10; i++) {
arr[i] = 1; //all elements can occur 1 time in number of length 1
tmp[i] = 0;
}
for (i=1; i<n; i++) {
for (j=0; j<10; j++) {
for (k=0;k<10; k++) {
if (ABS(k-j) >=4)
tmp[j] += arr[k];
}
}
for (j=0; j<10; j++) {
arr[j] = tmp[j];
tmp[j] = 0;
}
}
tot = 0;
for (i=0; i<10; i++) {
tot += arr[i];
}
return (tot);
}
If we find all possible combination of number ending 0-9 with n-1 length, then we can calculate all possible combinations of bumber ending 0-9 with n length
long improvedCount (int n) {
long arr[10], tmp[10], tot=0;
int i, j, k;
arr[0] = 0; // First number cannot be 0
tmp[0] = 0;
for (i =1; i<10; i++) {
arr[i] = 1; //all elements can occur 1 time in number of length 1
tmp[i] = 0;
}
for (i=1; i<n; i++) {
for (j=0; j<10; j++) {
for (k=0;k<10; k++) {
if (ABS(k-j) >=4)
tmp[j] += arr[k];
}
}
for (j=0; j<10; j++) {
arr[j] = tmp[j];
tmp[j] = 0;
}
}
tot = 0;
for (i=0; i<10; i++) {
tot += arr[i];
}
return (tot);
}
int getAllNum (int n, int length) {
// cout << n << endl;
if (length == 1) {
return 1;
}
int combination = 0;
for (int i = 0; i <= (n-4); i ++) {
combination += getAllNum(i, length-1);
}
for (int i = 9; i >= (n+4); i--) {
combination += getAllNum(i, length-1);
}
return combination;
}
int generateDigit(int length) {
int total = 0;
for (int i = 1; i < 10; i ++) {
total += getAllNum(i, length);
}
return total;
}
using recursion
public class FourDifference {
public int find(int length) {
int count = 0;
for (int i = 1; i <= 9; i++) {
count += generateNumber(length, 0, i, 0, 0);
}
return count;
}
private int generateNumber(int length, int index, int currentNumber, int nextNumber, int count) {
if (length == index + 1 || nextNumber < 0 || nextNumber > 9) return count;
if (isNextBiggerByFour(currentNumber, nextNumber) || iSNextSmallerByFour(currentNumber, nextNumber)) {
if (length == index + 2) count += 1;
count = generateNumber(length, index + 1, nextNumber, 0, count);
}
return generateNumber(length, index, currentNumber, nextNumber + 1, count);
}
private boolean isNextBiggerByFour(int currentDigit, int nextDigit) {
return (nextDigit - currentDigit >= 4);
}
private boolean iSNextSmallerByFour(int currentDigit, int nextDigit) {
return (currentDigit - nextDigit >= 4);
}
}
source - git.io/vOArQ
test - git.io/vOAom
Using dynamic programming approach, while also saving ALL the numbers that are found following the above constraints:
def solution(distance, digits):
"""Find how many numbers of length n are there such that each digit in such a number
is at least k smaller/greater than the number before and after it.
e.g. If (n == digits == 5) and (k == distance == 4), then, the numbers "39518" and "15951"
are both part of the solution set.
"""
n = digits
k = distance
if (n < 2):
raise ValueError('# of digits must be 2 or above!')
if (distance >= 10):
raise ValueError('Distance must be between 0 and 9!')
# Using a dynamic programming approach:
# let dp be a two-dimensional array following this property:
# dpk[n][p] = the set of numbers with `n` digits and prefix number `p` that satisfy the above constraint
# for a constant `k`.
dpk = {}
# we can construct the solution set for n = 2
for i in range(10): # i is the digit in the tens position
dpk[(2, i)] = set() # initialize dpk[2][i] to empty
for j in range(10): # j is the digit in the ones position
if abs(i - j) < k:
continue
# add all possible two-digit numbers "ij" such that i and j are k distance apart
dpk[(2, i)].add('{:d}{:d}'.format(i, j))
# we now have the base dpk[2][i] for all 1-digit prefixes filled in
# now, iteratively build our solution from n = 3 onward
# here, for 3 <= n <= digits:
#
# dpk[n][p] = Union{ {"pD" for all D in dpk[n-1][i] } for all i such that |i - p| >= k
#
for n in range(3, n+1):
for p in range(10): # build a solution for all prefixes in [0,9]
build = set()
dpk[(n,p)] = build
for i in range(10): # find all possible suffixes with a given prefix
if abs(i - p) < k:
continue
suffixes = dpk[ ((n-1),i) ]
for suffix in suffixes:
build.add('{:d}{:s}'.format(p, suffix))
return dpk
if __name__ == '__main__':
distance = 4
digits = 5
print 'Problem parameters . . .'
print '# of digits: {:d}'.format(digits)
print 'Distance between digits: {:d}'.format(distance)
dpk = solution(distance, digits)
# from the above, only collect dpk[n] where n == digits
keys = [(n, p) for (n, p) in dpk if (n == digits and p != 0)]
# ignoring prefix '0', collect all numbers from each prefix
sol_numbers = set()
for key in keys:
subset = dpk[key]
for n in subset:
sol_numbers.add(int(n))
print
print 'Solution . . .'
#print sol_numbers
print 'There are {:d} such numbers.'.format(len(sol_numbers))
##
## Output:
##
## $ python numdistance.py
## Problem parameters . . .
## # of digits: 5
## Distance between digits: 4
##
## Solution . . .
## There are 3224 such numbers.
##
int getCount(int N) {
if (N <= 0) { return 0; }
if (N == 1) { return 10; }
int count1[10] = { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
int count2[10] = { };
int *pPrevCounts = &count1[0];
int *pCounts = &count2[0];
for (int iDigit = 1; iDigit < N; ++iDigit) {
if (iDigit % 2) {
pPrevCounts = &count1[0];
pCounts = &count2[0];
} else {
pPrevCounts = &count2[0];
pCounts = &count1[0];
}
for (int i = 0; i <= 9; ++i) {
for (int j = i - 4; j >= 0; --j) {
pCounts[j] += pPrevCounts[i];
}
for (int j = i + 4; j <= 9; ++j) {
pCounts[j] += pPrevCounts[i];
}
}
}
int result = 0;
for (int i = 0; i <= 9; ++i) {
result += pCounts[i];
}
return result;
}
int main() {
int N = 2;
cout << getCount(N) << endl;
cout << countNumbers(N) << endl;
return 0;
}
{{
int numnum( int n )
{
if ( n <= 1 ) return 0;
int len = 10;
vector< vector<int> > dp( 2, vector<int>( 10, 0 ) );
int pre = 0, cur = 1;
//init
for ( int i = 1; i < len; ++i )
dp[cur][i] = 1;
//dp[cur][i] = { count(nums)| nums are which end with i}
for ( int k = 2; k <= n; ++k ) {
swap( pre, cur );
for ( int i = 0; i < len; ++i ) {
for ( int j = 0; j <= i - 4; ++j ) {
dp[cur][j] += dp[pre][i];
}
for ( int j = i + 4; j < len; ++j ) {
dp[cur][j] += dp[pre][i];
}
}
}
int sum = 0;
for ( int i = 0; i < len; ++i ) {
// cout << dp[cur][i] << " ";
sum += dp[cur][i];
}
cout << endl << " total: " << sum << endl;
}
}}
int numnum( int n )
{
if ( n <= 1 ) return 0;
int len = 10;
vector< vector<int> > dp( 2, vector<int>( 10, 0 ) );
int pre = 0, cur = 1;
//init
for ( int i = 1; i < len; ++i )
dp[cur][i] = 1;
//dp[cur][i] = { count(nums)| nums are which end with i}
for ( int k = 2; k <= n; ++k ) {
swap( pre, cur );
for ( int i = 0; i < len; ++i ) {
for ( int j = 0; j <= i - 4; ++j ) {
dp[cur][j] += dp[pre][i];
}
for ( int j = i + 4; j < len; ++j ) {
dp[cur][j] += dp[pre][i];
}
}
}
int sum = 0;
for ( int i = 0; i < len; ++i ) {
// cout << dp[cur][i] << " ";
sum += dp[cur][i];
}
cout << endl << " total: " << sum << endl;
}
int[] map = {0, 5, 4, 3, 2, 2, 2, 3, 4, 5 };
int[][] ranges = new int[][]
{
new int[] { 5, 6, 7, 8, 9 },
new int[] { 6, 7, 8, 9 },
new int[] { 7, 8, 9 },
new int[] { 8, 9 },
new int[] { 9, 1 },
new int[] { 1, 2 },
new int[] { 1, 2, 3 },
new int[] { 1, 2, 3, 4 },
new int[] { 1, 2, 3, 4, 5 }
};
public int NumberCombinations(int n)
{
if (n == 1)
return 9;
else if (n == 0)
return 0;
else if (n < 0)
return -1;
int total = 0;
for (int i = 1; i <= 4; i++)
{
total += NumberCombinations(n - 1, i);
}
total *= 2;
total += NumberCombinations(n - 1, 5);
return total;
}
private int NumberCombinations(int n, int value)
{
if (n == 1)
return map[value];
int total = 0;
int[] a = ranges[value - 1];
for (int i = 0; i < a.Length; i++)
total += NumberCombinations(n - 1, a[i]);
return total;
}
Can be solved without using the ranges array is pretty much the same
private int NumberCombinations(int n, int value)
{
if (n == 1)
return map[value];
int total = 0;
int m = value - 4;
for (int i = 1; i <= m; i++)
total += NumberCombinations(n - 1, i);
m = value + 4;
for (int i = 9; i >= m; i--)
total += NumberCombinations(n - 1, i);
return total;
}
Fill the table f[][], so that f[n][a] indicates how many integers of length n that start with digit 'a' satisfy the property.
To calculate f[n][a], sum f[n-1][b] for the allowed values of b.
def count(N):
next_number = {i:[j for j in range(10) if abs(i-j) > 3] for i in range(10)}
f = [[0] * 10 for i in range(N)]
for i in range(10): f[0][i] = 1
for j in range(1, N):
for i in range(10):
f[j][i] = sum([f[j-1][k] for k in next_number[i]])
return sum(f[N-1][j] for j in range(1,10))
Fill the table f[][], so that f[n][a] indicates how many integers of length n that start with digit 'a' satisfy the property.
To calculate f[n][a], sum f[n-1][b] for the allowed values of b.
def count(N):
next_number = {i:[j for j in range(10) if abs(i-j) > 3] for i in range(10)}
f = [[0] * 10 for i in range(N)]
for i in range(10): f[0][i] = 1
for j in range(1, N):
for i in range(10):
f[j][i] = sum([f[j-1][k] for k in next_number[i]])
return sum(f[N-1][j] for j in range(1,10))
Question is similar to the famous "Box Stacking" problem.
int numNumbers4Apart(int N, int previous, int index,
vector<vector<int>>& numbersAtIndex) {
if(index == N) return 1;
if(previous >= 0 && numbersAtIndex[index][previous] != -1)
return numbersAtIndex[index][previous];
int ways = 0;
for(int i=0; i<10; ++i) {
if(promising(i, previous)) {
ways += numNumbers4Apart(N, i, index+1, numbersAtIndex);
}
}
if(previous >= 0) {
numbersAtIndex[index][previous] = ways;
}
return ways;
}
int N = 5;
vector<vector<int> > numbersAtIndex(N, vector<int>(10, -1));
cout << numNumbers4Apart(N, -3, 0, numbersAtIndex) << endl;
Dynamic Programming:
Time Complexity O(100*N) = O(N)
Space Complexity O(20) = O(1)
//Mehrdad AP
int solve(int N)
{
vector<int> dpCur(10,0),dpPrev(10,0);
dpPrev[0]=0;
for (int i=1;i<10;i++)
dpPrev[i]=1;
for (int i=1;i<N;i++){
for (int j=0;j<10;j++)
for (int k=0;k<10;k++)
if (abs(j-k)>=4)
dpCur[j]+=dpPrev[k];
dpPrev=dpCur;
}
int ans=0;
for (int i=0;i<10;i++)
ans+=dpPrev[i];
return ans;
}
Nice idea using the state logic . Here is my implementation
446 void num_problem_util(char A[][6], int i, int c, int n, char *path, int k, int l) {
447 int j;
448
449 if(k==n) {
450 //we print only at the leaves
451 printf("%s ", path);
452 return;;
453 }
454
455 for(j=0;j<c;j++) {
456 if(A[i][j] != 'x') {
457 path[l] = A[i][j];
458 num_problem_util(A, A[i][j]-'0', c, n, path, k+1, l+1);
459 }
460 }
461 }
462 void number_problem() {
463 //maintain the state information, ie for each digit we store the number of permissible next digits
464 char state[][6] = { {'4', '5', '6', '7', '8', '9'}, // digit 0
465 {'5', '6', '7', '8', '9', 'x'}, // digit 1
466 {'6', '7', '8', '9', 'x', 'x'},
467 {'7', '8', '9', 'x', 'x', 'x'},
468 {'0', '8', '9', 'x', 'x', 'x'},
469 {'0', '1', '9', 'x', 'x', 'x'},
470 {'0', '1', '2', 'x', 'x', 'x'},
471 {'0', '1', '2', '3', 'x', 'x'},
472 {'0', '1', '2', '3', '4', 'x'},
473 {'0', '1', '2', '3', '4', '5'} }; // digit 9
474
475 /*
476 * now we create a path array array to store all the valid combination of the arrays
477 * the length of the array will be 6 ( max number of column in state array)
478 */
479
480 char *path = (char*)malloc(sizeof(char)*6);
481 int n;
482 printf("Enter length of digits\n");
483 scanf("%d", &n);
484
485 num_problem_util(state, 1, 6, n, path, 0, 0);
486 }
We can use DP to solve this problem. Define dp[i][j] is the anwer for the first i numbers and the ith number is j, then we have dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + ... + dp[i - 1][j - 4]
int solve(int n) {
vector<vector<int> > dp(n, vector<int>(10, 0));
dp[0][0] = 0;
for (int i = 1; i < 10; ++i)
dp[0][i] = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 10; ++j) {
for (int k = 0; k <= j -4; ++k) {
dp[i][j] += dp[i][k];
}
}
}
int ans = 0;
for (int j = 0; j < 10; ++j)
ans += dp[n - 1][j];
return ans;
}
O(n*k^2) time and O(k) memory where n is the length of the number and k is the size of the digit set. Since k is constant and equal to 10 it is O(n) time and O(1) space.
public static int calcNumberOfNumbers2(int n) {
if (n==1) {
return 9;
}
int[] a = new int[10];
for (int i = 0 ; i < 10; i++) {
a[i] = 1;
}
int[] b = new int[10];
for (int i = 1 ; i < n; i++) {
b[0] = b[4] + a[5] + a[6] + a[7] + a[8] + a[9];
b[1] = a[5] + a[6] + a[7] + a[8] + a[9];
b[2] = a[6] + a[7] + a[8] + a[9];
b[3] = a[7] + a[8] + a[9];
b[4] = a[0] + a[8] + a[9];
b[5] = a[0] + a[1] + a[9];
b[6] = a[0] + a[1] + a[2];
b[7] = a[0] + a[1] + a[2] + a[3];
b[8] = a[0] + a[1] + a[2] + a[3] + a[4];
b[9] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5];
a= b;
}
return b[1] + b[2] + b[3] + b[4] + b[5] + b[6] + b[7] + b[8] + b[9];
}
From the simple recurrence relation we can derive a O(1) time and space solution...
First number must not be 0.
So for f(0) = 9.
Looking at 0-9 the only ones that add 2 are going to be 4 and 5 since 4->(0, 8) and 5->(1, 9).
We also know that it'll only add it every other digit since it needs to go from 4->0->4, 4->8->4 or 5->1->5, 5->9->5.
Every layer though, 0->4, 8->4, and 9->5, 1->5. So again we get 2 extra..
f(1) = 11 => {15, 26, 37, 40, 48, 51, 59, 62, 73, 84, 95}
f(2) = 13 => {151, 159, 262, 374, 404, 484, 515, 595, 626, 737, 840, 848, 951, 959}
...
So 9 + 2*length-1
int countNumsDist4(int length) {
return 9 + 2*(length - 1);
}
public int countNdigitValues(int n)
{
if(n<=1)
{
return 0;
}
int[] ends=new int[10];//store cumulative counts on the number of 2 digit values that end with 0-i(where i>=0 && i<=9)
int[] begins=new int[10];//store cumulative counts on the number of 2 digit values that begin with 0-9 (where i>=0 && i<=9)
for(int i=0;i<ends.length;i++)
{
int digits=countDigitsLess(i)+countDigitsGreater(i);
ends[i]=ends[i-1]+digits;
begins[i]=begins[i-1]+digits;
}
for(int i=3;i<=n;i++)
{
int[] endsUpdate=new int[10];//stores how many i digit values end with each digit using counts for i-1 digits
int[] beginsUpdate=new int[10];//stores how many i digit values begin with each digit using counts for i-1 digits
for(int j=0;j<9;j++)
{
if(j+4<=9)
{
endsUpdate[j]=ends[9]+ends[j+4-1];
beginsUpdate[j]=begins[9]+begins[j+4-1];
}
if(j-4>=0)
{
endsUpdate[j]+=ends[j-4];
beginsUpdate[j]+=begins[j-4];
}
}
ends=endsUpdate;
begins=beginsUpdate;
}
return ends[ends.length-1]+begins[begins.length-1];
}
//Time complexity is O(N), space is O(1)
//Count the number of digits 4 or more units less than k.
private int countDigitsLess(int k)
{
if(k>=4)
{
return(k-4+1);
}
return 0;
}
//Count the number of digits 4 or more units greater then k.
private int countDigitsGreater(int k)
{
if(k<=5)
{
return(9-(k+4)+1)
}
return 0;
}
I was thinking more of a recursive solution:
public class CountOfNumsWithDigitsSeperatedByFour {
public static void main(String[] args)
{
System.out.println(CountOfNums(5));
}
static int CountOfNums(int size)
{
int count = 0;
for(int i = 1; i <= 9; i++)
{
count += CountOfNumsStartingWith(i, size-1, i+"");
}
return count;
}
static int CountOfNumsStartingWith(int i, int size, String s)
{
if (size == 0)
{
System.out.println(s);
return 1;
}
int count = 0;
for(int k = i+4; k <= i+9; k++)
{
if (IsSafe(k))
{
count += CountOfNumsStartingWith(k, size-1, s+k);
}
}
for(int k = i-4; k >= i-9; k--)
{
if (IsSafe(k))
{
count += CountOfNumsStartingWith(k, size-1, s+k);
}
}
return count;
}
static boolean IsSafe(int num)
{
return num >= 0 && num <= 9;
}
}
public class plus4combin {
public static void main(String args[])
{
int array[]=new int[5];
for(int i=1;i<10;i++)
{
array[0]=i;
method(array,1);
}
}
private static void method(int[] array,int index) {
// TODO Auto-generated method stub
if(index==array.length)
{
for(int ch:array)
System.out.print(ch);
System.out.println();
}
else if(index<array.length)
{
for(int k=4;k<10;k++)
{
if(array[index-1]+k < 10)
{array[index]=array[index-1]+k;
method(array,index+1);
}
if(array[index-1]-k>0)
{
array[index]=array[index-1]-k;
method(array,index+1);
}
}
}
}
}
Example in Node.js:
var out = [];
var n = 5;
var result = 0
function combine(start) {
if (out.length == n) {
console.log(out.join(""));
result++;
return;
}
for (var i = 1; i < 10; i++) {
if (Math.abs(out[out.length-1]-i)<4)
continue;
out.push(i);
combine(i+1);
out.pop();
}
}
combine(0);
console.log("Number of possibilities for n = 5: " + result); // 1454
A solution that saves state.
- Andy August 02, 2015