Round 1
Questions:
Given a string org_code
of size n representing the digits in decimal notation and integer k, find a string new_code
representing the digits in decimal notation, which satisfies org_code <= new_code
, and which is also attractive, given that there are no leading zeroes in the code.
A string S of size n representing the digits in decimal notation is lexicographically less than string P of length m if one of the two statements is correct:
- n < m, and S is the beginning (prefix) of string P.
- S[1] = P[1], S[2] = P[2], ..., S[k-1] = P[k-1], S[k] < P[k] for some k (1 <= k <= min(n, m)), here characters in strings are numbered starting from 1.
Example:
org_code = 1234
k = 2
Given org_code
= 1234
, where org_code / n = 4
, and k = 2
, the task is to find the smallest new_code
such that it is greater than or equal to org_code
and satisfies the attractiveness condition, meaning digits repeat every k positions.
First, take the first k digits from org_code
(12
) and repeat them to form the candidate new_code
= 1212
. Since 1212
is smaller than 1234
, we increment the first two digits, resulting in 13
, and repeat it to get new_code
= 1313
.
This new code is attractive because b[0] = b[2] = 1 and b[1] = b[3] = 3, and it also satisfies org_code <= new_code
(as 1313 >= 1234
). Thus, 1313
is the required new_code
.
Input Format for Custom Testing:
- The first line contains a string
old_code
. - The second line contains an integer k.
Sample Case 0:
Input:
41242 4
Output:
41244
Explanation:
We need to find a new product code new_code
greater than or equal to 41242
and attractive with k = 4. This means the first digit must be the same as the fifth digit (because 4 + 0 = 4).
We can change the last digit of 41242
from 2
to 4
, resulting in 41244
. This new code is still greater than 41242
and meets the attractiveness condition, as the first digit 4
matches the fifth digit 4
.
Hence, 41244
is the smallest attractive integer new_code
.
public String findSmallestAppealing(String old_code, int k) { if (k > old_code.length()) { return ""; } String firstKChars = old_code.substring(0, k); StringBuilder result = new StringBuilder(); while (result.length() < old_code.length()) { result.append(firstKChars); } result.setLength(old_code.length()); if (result.toString().compareTo(old_code) >= 0) { return result.toString(); } BigInteger firstKNum = new BigInteger(firstKChars); BigInteger incrementedNum = firstKNum.add(BigInteger.ONE); String newFirstKChars = String.format("%0" + k + "d", incrementedNum); if (newFirstKChars.length() > k) { result = new StringBuilder(); while (result.length() < old_code.length()) { result.append(newFirstKChars.substring(0, k)); } } else { result = new StringBuilder(); while (result.length() < old_code.length()) { result.append(newFirstKChars); } } result.setLength(old_code.length()); return result.toString(); }
Candidate's Approach
The candidate first checks if k is greater than the length of old_code, returning an empty string if true. They extract the first k characters from old_code and repeat them to form a candidate new_code. If this candidate is greater than or equal to old_code, it is returned. If not, the candidate is incremented, and the process is repeated to ensure the new_code is attractive.
Interviewer's Feedback
No feedback provided.