CareerCup

The first digit can be anything from 1..9, the next digit can be previous, previous-1 or previous+1, and so on. There are O(9*3^(n-1)) jumbled numbers (lines of output), how should one produce this amount of output with a O(n) or O(lg(n)) algo? Was maybe the question to return how many jumbled number exist?

Looking at the problem,may be this is what the interviewer meant??
The outer while loop in O(n).
The inner for loop is dependent on the 'n', where the loop would be for -
9*1, 9*2-1, (9*2-1)*2-2, ... times.
The total iterations would be [9*1] + [9*2-1] + [(9*2-1)*2-2] + ...n
This is constant K*n.
Total complexity = n + K*n..
please check if I am going wrong somewhere...

The code -

/**
output - 
1 2 3 4 5 6 7 8 9 
11 12 22 23 33 34 44 45 55 56 66 67 77 78 88 89 99 
111 112 122 123 222 223 233 234 333 334 344 345 444 445 455 456 555 556 566 567 666 667 677 678 777 778 788 789 888 889 899 999 
*/

public static void main(String args[]) {
        countandprint(3);
    }
    
    public static void countandprint(int n){
        int count = 9;
        int[] arr = new int[count];
        for(int i = 0; i < arr.length; i++)
            arr[i] = i+1;
        int k = 0;
        while(n > 0){
            count = count*2-1-k;
            int[] arrh = new int[count]; 
            
            int j = 0;
            for(int i = 0; i < arr.length; i++){
                System.out.print(String.valueOf(arr[i]) + " ");
                
                String no = String.valueOf(arr[i]);
                int post = arr[i]%10;
                    
                if(j < count){
                    arrh[j] = Integer.parseInt(no + String.valueOf(post));
                    j++;
                }
                if(j+1 < count && (post+1) < 10){
                    arrh[j] = Integer.parseInt(no + String.valueOf(post+1));
                    j++;
                }
            }
            System.out.println();
            arr = new int[count];
            arr = Arrays.copyOf(arrh, arrh.length);
            n--;
            k++;
        }
    }

@studip.innovates:
my thoughts on your documented output:
- 1 is not of n=3 digits unless you interpret it as 100, but then 2 as 200 would violate the "1" difference between 2 and 0
- if it should be 001, a general question is, if "001" is of three or one digit, and "002" would have the same issue as "200"
- "101" is missing, as well as "121", "132", etc..

... it seems we have a different understanding of the problem.

here some code with sample output to keep it less virtual, the exponential nature is obvious.

#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> getJumbledNumbers(int n)
{ // n beeing the number of digits
	vector<vector<int>> results;
	if (n == 0) return results;
	for (int i = 1; i < 10; ++i) {
		results.push_back({ i }); 
	}
	for (size_t i = 1; i < n; ++i) {
		size_t lastResultCount = results.size();
		for (size_t j = 0; j < lastResultCount; ++j) {			
			int previous = results[j].back();
			results[j].push_back(previous);  // 1,1
			if (previous < 9) { // 1,2 .. 8,9
				vector<int> new_res(results[j]); 
				new_res.back()++;
				results.push_back(move(new_res));
			}
			if (previous > 0) { //1,0 .. 9,8
				vector<int> new_res(results[j]); 
				new_res.back()--;
				results.push_back(move(new_res));
			}
		}
	}
	return results;
}

// helper to print 
void printJumbledNumbers(int n) {
	auto results = getJumbledNumbers(n);
	cout << results.size() << " jumbled numbers with " << n << " digits";
	if (results.size() < 90) {
		cout << ": ";
		for (auto& result : results) {
			for (auto& digit : result) {
				cout << digit;
			}
			cout << " ";
		}
	}
	cout << endl << endl;
}


int main()
{
	for (int i = 1; i < 10; ++i) {		
		printJumbledNumbers(i);
	}
}

/* output
9 jumbled numbers with 1 digits: 1 2 3 4 5 6 7 8 9

26 jumbled numbers with 2 digits: 11 22 33 44 55 66 77 88 99 12 10 23 21 34 32 45 43 
56 54 67 65 78 76 89 87 98

75 jumbled numbers with 3 digits: 111 222 333 444 555 666 777 888 999 122 100 233 211 
344 322 455 433 566 544 677 655 788 766 899 877 988 112 110 223 221 334 332 445 443 556 
554 667 665 778 776 889 887 998 123 121 101 234 232 212 210 345 343 323 321 456 454 434 
432 567 565 545 543 678 676 656 654 789 787 767 765 898 878 876 989 987

217 jumbled numbers with 4 digits

629 jumbled numbers with 5 digits

1826 jumbled numbers with 6 digits

5307 jumbled numbers with 7 digits

15438 jumbled numbers with 8 digits

44941 jumbled numbers with 9 digits
*/

@ChrisK.. yes for the sample output in the question... seemed to me that -1 is not getting considered.. only 0&-1.. if -1 needs to be considered.. then definitely 121, 132 would be an option....

@chrisK, @sudip.innovates
how are you guys getting to that conclusion? please look at the same output:
100
_101_
_110_
111
_121_

101 has last digit as 1 and 2nd last digit as 0.
0-1 = -1. etc.
i've added the updated the word 'difference' with '_absolute_ difference' incase its not clear to any one :)

@mani0119 considering ma abs diff as 1. Here is the updated code -

/**
output - 
1 2 3 4 5 6 7 8 9 
10 11 12 21 22 23 32 33 34 43 44 45 54 55 56 65 66 67 76 77 78 87 88 89 98 99 
100 101 110 111 112 121 122 123 210 211 212 221 222 223 232 233 234 321 322 323 332 333 334 343 344 345 432 433 434 443 444 445 454 455 456 543 544 545 554 555 556 565 566 567 654 655 656 665 666 667 676 677 678 765 766 767 776 777 778 787 788 789 876 877 878 887 888 889 898 899 987 988 989 998 999 
*/
public static void main(String args[]) {
        countandprint(3);
    }
    
    public static void countandprint(int n){
        int count = 9;
        int[] arr = new int[count];
        for(int i = 0; i < arr.length; i++)
            arr[i] = i+1;
        int k = 0;
        while(n > 0){
            count = count*3-1-k;
            int[] arrh = new int[count]; 
            
            int j = 0;
            for(int i = 0; i < arr.length; i++){
                System.out.print(String.valueOf(arr[i]) + " ");
                
                String no = String.valueOf(arr[i]);
                int post = arr[i]%10;
                
                if(j < count && (post-1) >= 0){
                    arrh[j] = Integer.parseInt(no + String.valueOf(post-1));
                    j++;
                }
                
                if(j < count){
                    arrh[j] = Integer.parseInt(no + String.valueOf(post));
                    j++;
                }
                if(j < count && (post+1) < 10){
                    arrh[j] = Integer.parseInt(no + String.valueOf(post+1));
                    j++;
                }
            }
            System.out.println();
            arr = new int[count];
            arr = Arrays.copyOf(arrh, arrh.length);
            n--;
            k += 2;
        }
    }

@mani0119:You didn't see the values, probably due to non-ascending order...

But since we are now clear on the problem, there's no linear solution, it's clearly exponential, with an upper bound (not thigh though) of O(3^n). There must be a misunderstanding or interviewer tested you on some behavior thing, maybe?

def jumbledNumbers(n,i):  #n digit jumbled numbers that end with i
	if i<0 or i>9:
		return []
        if n==1:
		return [str(i)]

	nums=[]
	nums.append(jumbledNumbers(n-1,i-1)).append(jumbledNumbers(n-1,i)).append(jumbledNumbers(n-1,i+1))	
	return appendToEachElement(nums,str(i))



def appendToEachElement(ll,s):
	out = []
	for num in ll:
		out.append(num+s)
	return out

I really can't decide what is the big O for this answer, however I'm pretty sure it is less than O(n^2)

public static void main(String args[]) {
		method(4, 0);
	}

	public static void method(int n, int counter) {
        if(counter<Math.pow(10, n-1)) method(n,(int)Math.pow(10, n-1));
        else if (counter >= Math.pow(10, n)) {
			return;
		} else {
			boolean flag = true;
			for (int i = 1; i <= n; i++) {
				int current, before, after;
				current = getNumber(counter, i);
				before = i == n ? current : getNumber(counter, i + 1);
				after =  i == 1 ? current : getNumber(counter, i - 1);
				if (!(Math.abs(current - before) <= 1 && Math.abs(current - after) <= 1))
					flag = false;
			}
			if (flag == true)
				System.out.println(counter);
			method(n, ++counter);
		}
	}

	public static int getNumber(int number, int position) {
		int n = (int) (number % Math.pow(10, position));
		n = (int) (n / Math.pow(10, position - 1));
		return n;

}

Not sure what is the best and worst case here. Also just printing a list of numbers is more than O(n) and should be around 9*3^(n-1) so it's O(3^n).

And calculating the number of jumbled numbers should be O(1) although I'm too lazy to figure out the exact formula

vector<vector<int>> JumbledNumbers(int n)
{
	vector<vector<int>> out;
	if (n > 0) {
		vector<int> a;
		a.resize(n, 0);
		a[0] = 1;
		while (a[0] <= 9) {
			out.push_back(a);
			int i = n - 1;
			for (; i >= 0; --i) {
				++a[i];
				if (i == 0 ||
					(a[i] <= a[i - 1] + 1 && a[i] <= 9))
				{
					break;
				}
			}
			for (i = i + 1; i < n; ++i) {
				a[i] = (a[i - 1] == 0) ? 0 : a[i - 1] - 1;
			}
		}
	}
	return out;
}

public static void main(String args[]) {
countandprint(3);
}

public static void countandprint(int n){
int count = 9;
int[] arr = new int[count];
for(int i = 0; i < arr.length; i++)
arr[i] = i+1;
int k = 0;
while(n > 0){
count = count*2-1-k;
int[] arrh = new int[count];

int j = 0;
for(int i = 0; i < arr.length; i++){
System.out.print(String.valueOf(arr[i]) + " ");

String no = String.valueOf(arr[i]);
int post = arr[i]%10;

if(j < count){
arrh[j] = Integer.parseInt(no + String.valueOf(post));
j++;
}
if(j+1 < count && (post+1) < 10){
arrh[j] = Integer.parseInt(no + String.valueOf(post+1));
j++;
}
}
System.out.println();
arr = new int[count];
arr = Arrays.copyOf(arrh, arrh.length);
n--;
k++;
}
}

I think there may be a dynamic programming solution having O(N) time complexity.

The idea behind this is to start from the base numbers {1-9} and add following numbers that follow the rule. IE (1 -> 10,11,12) Then stopping when it reaches N digits.
It is O(logK) where K = 10^(N+1) since the solution is around size 10*3^(N). The big O is log base 3 of 10^N.

{{
static void jumbleNumbers(int n) {
Queue<Long> prev = new ArrayDeque<>(LongStream.rangeClosed(1,9)
.mapToObj(i -> i)
.collect(Collectors.toList()));
long remainder, temp;
double stop;
for(int i = 0; i < n-1; i++){
stop = Math.pow(10, i+1);
while(prev.peek() < stop){
temp = prev.poll();
remainder = temp % 10;
temp = (temp*10) + remainder;
if(remainder -1 >= 0){
prev.add(temp-1);
}
if(remainder+1 <= 9){
prev.add(temp+1);
}
prev.add(remainder + temp);
}
}
System.out.println("Number of Jumble Numbers:\t" + prev.size());
System.out.println(prev);
}
}}