Problem

Given a set S of digits [0-9] and a number n. Find the smallest integer larger than n (ceiling) using only digits from the given set S. You can use a value as many times you want.

Examples

Example 1:

1
2

Input: digits= [1, 2, 4, 8], num = 8753
Output: 8811

Example 2:

1
2

Input: digits = [0, 1, 8, 3], num = 8821
Output: 8830

Example 3:

1
2

Input: digits = [0, 1, 8, 3], num = 8310
Output: 8831

Similar Problems

In a way, it relates to: Next Greater Element 3 - Find smallest number larger than given number using same digits but not same.

Solution

Method 1 - Sorting

Two numbers are identical if their corresponding digits match. To find the smallest number larger than a given number num, we increase at least one digit and ensure subsequent digits are the smallest available.

Given the array digits=[0, 1, 8, 3] and num=8821, digits match up to [88] when compared from most to least significant. When we encounter a digit not present in digits, like 2 at the second to last position in num, we substitute it with the smallest digit in digits that’s greater, which is 3 here. Any remaining less significant digits are set to the lowest digit in digits, so the answer is 8830.

To find the immediate higher digit, sort digits and apply binary search to find the least digit in digits that’s greater than or equal to the current digit. If num includes only digits from digits, it might replicate itself as the next larger number. To avert this, if no higher digits appear upon scanning, replace the least significant digit in num with the next smallest digit in digits that’s strictly bigger than the current one.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

// dry run with digits=[1, 2, 4, 8] and num=8753
public int[] nextHigherWithDigits(int[] digits, int num) {
	// Get the target digits sorted
	int[] sortedDigits = Arrays.copyOf(digits, digits.length);
	Arrays.sort(sortedDigits);

	// Get the digits of the num from LSB to MSB order
	ArrayList<Integer> digitsOfNum = new ArrayList<>();
	// [3, 5, 7, 8]
	while (num > 0) {
		digitsOfNum.add(num % 10);
		num /= 10;
	}

	// Reverse to get the digits in MSB to LSB order
	Collections.reverse(digitsOfNum); // [8, 7, 5, 3]
	
	boolean higherAdded = false;
	int[] ans = new int[digitsOfNum.size()];
	int idx = 0;

	// For each digit in the num, find the next higher in the sorted target digits
	for (int digit: digitsOfNum) {
		// If a higher digit was already found in previous steps then use the smallest digit
		if (higherAdded) {
			ans[idx++] = sortedDigits[0];
			continue;
		}

		// Otherwise, find the next higher (or equal) digit
		int nextHigher = binarySearchCeiling(sortedDigits, 0, sortedDigits.length - 1, digit);
		// If no such higher digit is found, return null as there is no solution
		if (nextHigher == -1) {
			return null;
		}
		//otherwise if the digit is indeed higher then all subsequent digits should be smallest, so mark this event
		else if (sortedDigits[nextHigher] > digit) {
			higherAdded = true;
		}

		// Add the next higher (or equal) digit to ans
		ans[idx++] = sortedDigits[nextHigher];
	}

	//If we didn;t find any higher digit, which is only possible when we found all equal digits
	//then set the LSB to the next strictly higher number (not equal)
	if (!higherAdded) {
		int nextHigher = binarySearchCeiling(sortedDigits, 0, sortedDigits.length - 1, ans[idx - 1] + 1);

		// Check if there is a strictly higher digit available
		if (nextHigher == -1) {
			return null;
		}

		ans[idx - 1] = sortedDigits[nextHigher];
	}

	return ans;
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public static int binarySearchCeiling(int A[], int l, int h, int key) {
	int mid = (l + h) / 2;

	if (A[l] >= key) {
		return l;
	}

	if (A[h]<key) {
		return -1;
	}

	if (A[mid] == key) {
		return mid;
	}
	//mid is greater than key, so either mid is the ceil or it exists in A[l..mid-1]
	else if (A[mid] > key) {
		if (mid - 1 >= l && A[mid - 1]  < = key) {
			return mid;
		} else {
			return binarySearchCeiling(A, l, mid - 1, key);
		}
	}
	//mid is less than the key, so either mid+1 is the ceil or it exists in A[mid+1...h]
	else {
		if (mid + 1 <= h && A[mid + 1] >= key) {
			return mid + 1;
		} else {
			return binarySearchCeiling(A, mid + 1, h, key);
		}
	}
}

Complexity

  • ⏰ Time complexity: O(n + d log d), where n is number of digits in number and d is number of digits in digits
  • 🧺 Space complexity: O(1)