I got this task:
The builders at a tech company are fixing a computer. This computer stores a special number made by a secret game using two small numbers, firstStep and secondStep. But uh-oh! Some digits (numbers) of the big number got lost!
They still have part of the number called puzzleNumber. It’s like a puzzle — some of the numbers are there, but others are missing. The task is to figure out what the full number might have been before some digits were lost.
Here’s how the game works:
Start with a score of 0.
You can add firstStep or secondStep to the score as many times as you want.
Each time you add, write down only the last digit of the score (that’s called the unit digit, like the 3 in 123).
Keep writing down these digits to make a big number.
Now imagine you did this and got a number, but someone erased some of the digits. What you see now is puzzleNumber.
Now the Task is: Find the smallest possible full number that could have made puzzleNumber by just erasing some digits from it.
If it’s not possible to do that with any number from the game, return "-1".
Example:
puzzleNumber = "27"
firstStep = 2
secondStep = 3
Let's play the game:
Start at 0.
Add 2 → score = 2 → last digit = 2 → full = "2"
Add 2 → score = 4 → last digit = 4 → full = "24"
Add 3 → score = 7 → last digit = 7 → full = "247"
Now look! If you remove the 4 from "247", you get "27" — the same as puzzleNumber!
There could be other numbers too, like "257", but we want the smallest one.
So the answer is: "247"
constrains:
2 <= |puzzleNumber| <= 2*10^5
1 <= firstStep, secondStep <= 9
This is an interview question in hackerrank, and I have come up with below code but it passed 7 test cases out of 15 , one test case failed saying wrong output and remaining failed with time out errors. All the failed test cases are hidden so I don't have details of them.
import java.util.*;
public class Main {
public static String solve(String puzzleNumber, int firstStep, int secondStep) {
Queue<State> queue = new LinkedList<>();
Set<String> seen = new HashSet<>();
queue.offer(new State(0, "", 0)); // cur, sequence, matchedIndex
while (!queue.isEmpty()) {
State curr = queue.poll();
if (curr.matched == puzzleNumber.length()) {
return curr.sequence;
}
String key = (curr.cur % 10) + ":" + curr.matched;
if (seen.contains(key)) continue;
seen.add(key);
// Try adding firstStep
int nextX = curr.cur + firstStep;
int digitX = nextX % 10;
int matchedX = curr.matched;
if (matchedX < puzzleNumber.length() && puzzleNumber.charAt(matchedX) == (char)(digitX + '0')) {
matchedX++;
}
queue.offer(new State(nextX, curr.sequence + digitX, matchedX));
// Try adding secondStep
if (firstStep != secondStep) { // prevent duplicate branches
int nextY = curr.cur + secondStep;
int digitY = nextY % 10;
int matchedY = curr.matched;
if (matchedY < puzzleNumber.length() && puzzleNumber.charAt(matchedY) == (char)(digitY + '0')) {
matchedY++;
}
queue.offer(new State(nextY, curr.sequence + digitY, matchedY));
}
}
return "-1";
}
static class State {
int cur;
String sequence;
int matched;
State(int cur, String sequence, int matched) {
this.cur = cur;
this.sequence = sequence;
this.matched = matched;
}
}
public static void main(String[] args) {
System.out.println(solve("27", 2, 3)); // Expected output: "247"
System.out.println(solve("324", 2, 3)); // Expected: 36924
System.out.println(solve("521", 5, 5)); // Expected: -1
}
}
What is the correct way to solve this problem in less time complexity?
The check whether it is possible to do is pretty easy depending on step sizes:
So if you encounter one of the restrictions you can first check whether it is possible or not before you proceed. The mathematical reason why otherwise all digits can be created is because the gcd of 10 and the 2 step sizes is always 1, except for the combinations mentioned above: gcd(10, 5, 5) = 5 and gcd(10, even, even) = 2. The gcd tells us which digits we can create: all those where digit % gcd = 0.
If both steps are the same we can generate the solution in a straight forward way because there is always only one possibility how the next digit can be reached. The solution size is at most 10 times the input size (if all input digits are 0 and both steps are the same and 1, 3, 7 or 9). This makes 2 million and should be easily doable (use StringBuilder and not string concatenation).
If the step sizes are different it is more complicated, but the solution size is at most 5 times the input size. The difficulty is to know when to add which digit. For this you can create a 10 x 10 array with the dimensions being current digit and difference and the stored value is the step size to take (everything is mod 10). The current digit matters, e.g. steps = 2 and 3, diff = 5, if the current digit is 7, then you want to make step 3 first, otherwise step 2. You can create this array like so:
Initializing everything to 0.
For each current digit set all those values where the difference is one of the step sizes (to the step size).
Go through the array (if both step sizes are even skip odd current number and differences) and if you encounter a 0 you check with both step sizes whether you can reach a populated value from that position.
Repeat 3. until you didn't have to skip a 0 value in 3.1. (at most 5 times). Important to note is that you have to make all the calculations in 3. based on the previous state to ensure not using values that were just populated in the current run of 3. For this it is probably the easiest to create a deep copy of the array at the start of 3. and then check against that clone.
Now you can also create the output for two different step sizes in a straightforward way by looking up next step size in the precalculated array.
Here is an implementation. It uses a slightly different lookup format: current digit, next puzzle number digit and the value is the best next reachable digit (to get to the puzzle number digit). This is because it makes it easier to generate the solution (no more calculation like modulo needed, only a simple lookup), but otherwise the logic is the same as above.
public static String solve(String puzzleNumber, int firstStep, int secondStep) {
int inc = 1; // increment
if (firstStep == 5 && secondStep == 5) {
for (int i = 0; i < puzzleNumber.length(); i++)
if ((puzzleNumber.charAt(i) - '0') % 5 != 0)
return "-1";
} else if (firstStep % 2 == 0 && secondStep % 2 == 0) {
for (int i = 0; i < puzzleNumber.length(); i++)
if ((puzzleNumber.charAt(i) - '0') % 2 != 0)
return "-1";
inc = 2;
}
StringBuilder sb = new StringBuilder();
if (firstStep == secondStep) {
for (int i = 0, d = 0; i < puzzleNumber.length(); i++)
do {
d = (d + firstStep) % 10;
sb.append(d);
} while (d != puzzleNumber.charAt(i) - '0');
} else {
int[][] lookup = new int[10][10];
for (int i = 0; i < 10; i += inc)
for (int j = 0; j < 10; j += inc)
lookup[i][j] = 10;
for (int i = 0; i < 10; i += inc) {
lookup[i][(i + firstStep) % 10] = (i + firstStep) % 10;
lookup[i][(i + secondStep) % 10] = (i + secondStep) % 10;
}
boolean skipped = true;
while (skipped) {
skipped = false;
int[][] backup = new int[10][];
for (int i = 0; i < 10; i += inc)
backup[i] = lookup[i].clone();
for (int cur = 0; cur < 10; cur += inc)
for (int next = 0; next < 10; next += inc)
if (backup[cur][next] == 10) {
int cur1 = (cur + firstStep) % 10;
int cur2 = (cur + secondStep) % 10;
if (backup[cur1][next] + backup[cur2][next] == 20)
skipped = true;
else if (backup[cur2][next] == 10)
lookup[cur][next] = cur1;
else if (backup[cur1][next] == 10)
lookup[cur][next] = cur2;
else
lookup[cur][next] = Math.min(cur1, cur2);
}
}
for (int i = 0, d = 0; i < puzzleNumber.length(); i++)
do {
d = lookup[d][puzzleNumber.charAt(i) - '0'];
sb.append(d);
} while (d != puzzleNumber.charAt(i) - '0');
}
return sb.toString();
}
Time complexity O(n) and additional space is O(1). You can't get better than that complexity-wise. I might not be a "reputable source", but I know hackerrank very well and I'm pretty sure this will pass all the tests easily.