## Google Interview Question for Software Developers

• 2

Country: United States

Comment hidden because of low score. Click to expand.
5
of 5 vote

A solution that saves state.

``````public class NumberProblem
{
// for length two, we know the answer.

private int[][] lengthTwoResults =
{{ 4,5,6,7,8,9 },
{ 5,6,7,8,9},
{ 6,7,8,9 },
{ 7,8,9 },
{ 0,8,9 },
{ 0,1,9 },
{ 0,1,2 },
{ 0,1,2,3 },
{ 0,1,2,3,4 },
{ 0,1,2,3,4,5 }
};

private int[][] countState; // Store state.

public void main(String args[])
{
int count = 0;
int n = 5;
countState = new int[n-1][];
for (int i = 0; i < n-1; i++)
{
// Set up matrix
countState[i] = new int[10];
}
// Loop through possible start numbers (1-9).  So number starting with 0 not allowed.
for (int i = 1; i < 9; i++)
{
count += getCount(i, n-1);
}
System.out.println("Count is " + count);
}

/**
* Recursively go through possible numbers after a prefix.
**/
public int getCount(int prefixNumber, int n)
{
/* Bottom layer of recursion.  We’ve got one more number to go.
* Check the above array. */
if (n == 1)
{
return lengthTwoResults[prefixNumber].length;
}
// Check to see if we’ve calculated this result before.
if (countState[n-1][prefixNumber] != 0)
{
// If so, return it.
return countState[n-1][prefixNumber];
}
int count = 0;
// Else, loop through all of the possible next-numbers.
for (int nextPossibleNumber: lengthTwoResults[prefixNumber])
{
// Have we calculated those results before?
if (countState[n-2][nextPossibleNumber] != 0)
{
// Yes, just add to count.
count += countState[n-2][nextPossibleNumber];
} else {
int subCount = getCount(nextPossibleNumber, n-1);
// Save result in matrix for next time.
countState[n-2][nextPossibleNumber] = subCount;
count += subCount;
}

}
// Save result of this value of n and prefix for next time.
countState[n-1][prefixNumber] = count;
return count;
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````// 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);
}
}``````

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

someone please explain what is the question saying, did not get it

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

someone please explain the question, I really do not get what it says

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

can you please explain the question a bit more? not completely get it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

can you please explain the question a bit more, not completely get it

Comment hidden because of low score. Click to expand.
0
of 0 vote

my native language is not english, I dont quite get the questions, could some one rephrase it for me please. Thanks.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

# 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:

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:

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.
##``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

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;
}

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

}

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]);

}``````

Comment hidden because of low score. Click to expand.
0

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);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;``````

Comment hidden because of low score. Click to expand.
0

Apparently you can't edit your solution...I forgot the 'promising' function

bool promising(int candidate, int previous) {
return abs(candidate - previous) >= 4;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 }``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}
}

}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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``````

Comment hidden because of low score. Click to expand.
0

Doesn't seem correct. 3224 looks as a right answer here. The solution doesn't consider 0 at all, does it?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.