FastPrep
Problem · String

Find Smallest Appealing

Learn this problem
● HardAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

Note - Amazon is likely to make a typo here. All the old_code should be old_code as the later makes more sense with new_code. So..."org" has been modified to "old"

A manager at Amazon is responsible for organizing a thrilling online shopping event for a tech festival, and they have come up with an exciting concept. In this game, users are presented with a sequence of digits representing a product code. The challenge is to find a new product code that is equally attractive or even more attractive than the original one.

Let's call an integer, represented in its decimal notation in order from left to right, b[1], b[2], b[3], ... b[n] attractive if b[i]=b[i+k], for each i such that 1 ≤ i ≤ n-k, where n and k are positive integers. For example, if k = 2, "252525" is attractive but "245254" is not.

Your task is to generate a new product code, represented by string new_code such that it is greater than or equal to the original product code old_code.

Formally, Given a string old_code of size n representing the digits in the decimal notation and integer k, find a string new_code, representing the digits in decimal notation, which satisfies old_code ≤ new_code and which also is attractive, given that there are no leading zeros in old_code and new_code.

A string s of size n representing the digits in the decimal notation is lexicographically less than string t 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], and 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.

    • Function

    findSmallestAppealing(old_code: String, k: int) → String

    Complete the function findSmallestAppealing in the editor below.

    findSmallestAppealing has the following parameters:

    • 1. string old_code: integer old_code represented as a string decimal notation
    • 2. int k: a positive integer such that k < n

    Returns

    string: smallest attractive integer new_code, such that old_code ≤ new_code, in decimal notation.

    : 𓏲🐋 ๋࣭All credit goes to Nachos and spike! ࣪ ˖✩࿐࿔ 🌊

    Examples

    Example 1

    old_code = "41242"k = 4return = "41244"

    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'.

    Now b[i] = b[i+4] for 1 ≤ i ≤ n-k.

    Hence, b = "41244" is the smallest attractive integer new_code, such as old_code ≤ new_code.

    Example 2

    old_code = "353"k = 2return = "353"
    :)

    Example 3

    old_code = "1234"k = 2return = "1313"
    Given old_code = "1234", where |old_code| = n = 4, and k = 2, the task is to find the smallest new_code such that it is greater than or equal to old_code and stisfies the attractiveness codition, meaning digits repeat every k positions. First, take the first k digits from old_code("12") and repeat them to form the candidate new_code = "1212". Since "1212" is smaller than "1234", we increment the first 2 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 old_code <= new_code (as "1313" > "1234"). Thus, "1313" is the required new_code.

    Constraints

  • 1 ≤ n ≤ 2*10^5
  • 1 ≤ k < n
  • 0 ≤ old_code[i] ≤ 9 for 0 ≤ i < n, and s[0] ≠ 0

    • More Amazon problems

    drafts saved locally
    public String findSmallestAppealing(String old_code, int k) {
  // write your code here
}
    old_code"41242"
    k4
    expected"41244"
    checking account