Apply Discount to Prices

Medium
1756.

Apply Discount to Prices

Apply Discount to Prices is a medium coding problem on strings, asked in Amazon interviews.

A sentence is a list of words separated by single spaces. A word is a price if it is a dollar sign '$' followed by one or more digits and nothing else — "$100", "$23" and "$6" are prices, while "100", "$", "$$5" and "$1e5" are not.

Given sentence and an integer discount (a percentage), apply the discount to every price: replace it with the discounted price written with exactly two digits after the decimal point. Leave every other word unchanged and return the new sentence.

Example 1

Input
sentence = "pay $250 for 2 kai items $$9", discount = 20
Output
pay $200.00 for 2 kai items $$9
Explanation
Only `$250` is a price; `$$9` has two dollar signs.

Example 2

Input
sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100
Output
1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$

Example 3

Input
sentence = "$9999999999 off", discount = 1
Output
$9899999999.01 off
Explanation
Prices can have ten digits, more than a 32-bit integer holds.

Constraints

  • 1 <= sentence.length <= 10^5
  • sentence consists of lowercase English letters, digits, ' ' and '$'
  • sentence has no leading or trailing spaces, and words are separated by a single space
  • every price is a positive number without leading zeros
  • every price has at most 10 digits
  • 0 <= discount <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} sentence
 * @param {number} discount
 * @return {string}
 */
var discountPrices = function(sentence, discount) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Apply Discount to Prices — Solution in Python, Java & C++

Apply Discount to Prices solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings.

Apply Discount to Prices is a medium coding problem on strings, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Strings
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A sentence is a list of words separated by single spaces. A word is a price if it is a dollar sign '$' followed by one or more digits and nothing else — "$100", "$23" and "$6" are prices, while "100", "$", "$$5" and "$1e5" are not.

Given sentence and an integer discount (a percentage), apply the discount to every price: replace it with the discounted price written with exactly two digits after the decimal point. Leave every other word unchanged and return the new sentence.

Example 1

Input: sentence = "pay $250 for 2 kai items $$9", discount = 20
Output: pay $200.00 for 2 kai items $$9
Explanation: Only `$250` is a price; `$$9` has two dollar signs.

Example 2

Input: sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100
Output: 1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$

Example 3

Input: sentence = "$9999999999 off", discount = 1
Output: $9899999999.01 off
Explanation: Prices can have ten digits, more than a 32-bit integer holds.

Constraints

  • 1 <= sentence.length <= 10^5
  • sentence consists of lowercase English letters, digits, ' ' and '$'
  • sentence has no leading or trailing spaces, and words are separated by a single space
  • every price is a positive number without leading zeros
  • every price has at most 10 digits
  • 0 <= discount <= 100

Hints for Apply Discount to Prices

  1. Hint 1

    Split the sentence on spaces and treat each word independently.

  2. Hint 2

    A word is a price only if its first character is '$', it has at least one more character, and every remaining character is a digit.

  3. Hint 3

    Avoid floating point: price · (100 - discount) is the new price in cents, an exact integer (up to about 10^12, so use 64 bits). Print cents / 100, a dot, and cents % 100 padded to two digits.

How to solve Apply Discount to Prices

Recognise prices word by word, and compute the discounted price exactly as an integer number of cents so formatting with two decimals never suffers rounding error.

Approach

  1. Split sentence on single spaces.
  2. For each word, check that it is '$' followed by at least one digit and only digits.
  3. For a price p, compute cents = p · (100 - discount) in 64-bit arithmetic and rewrite the word as '$' + (cents / 100) + '.' + two-digit (cents % 100).
  4. Join the words back with single spaces.

Why it works

p · (100 - discount) / 100 dollars equals p · (100 - discount) cents exactly, because both factors are integers — so the two decimals are exact and need no rounding.

Complexity

  • Time — O(|sentence|)
  • Space — O(|sentence|)

Pitfalls

  • A ten-digit price overflows a 32-bit integer; with a discount it reaches about 10^12 cents.
  • Floating-point multiplication such as 9999999999 * 0.99 can print the wrong last digit.
  • "$" on its own, "$$5", "5$" and "$1a" are not prices.

Reference solution

Python

def discountPrices(sentence: str, discount: int) -> str:
    words = sentence.split(" ")
    for i, w in enumerate(words):
        if len(w) >= 2 and w[0] == "$" and w[1:].isdigit():
            cents = int(w[1:]) * (100 - discount)
            words[i] = "$%d.%02d" % (cents // 100, cents % 100)
    return " ".join(words)

Java

public static String discountPrices(String sentence, int discount) {
    String[] words = sentence.split(" ");
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < words.length; i++) {
        if (i > 0) sb.append(' ');
        String w = words[i];
        boolean price = w.length() >= 2 && w.charAt(0) == '$';
        for (int j = 1; j < w.length() && price; j++) if (!Character.isDigit(w.charAt(j))) price = false;
        if (!price) {
            sb.append(w);
            continue;
        }
        long cents = Long.parseLong(w.substring(1)) * (100 - discount);
        sb.append(String.format("$%d.%02d", cents / 100, cents % 100));
    }
    return sb.toString();
}

C++

string discountPrices(string sentence, int discount) {
    stringstream ss(sentence);
    string w, out;
    bool first = true;
    while (ss >> w) {
        if (!first) out += ' ';
        first = false;
        bool price = w.size() >= 2 && w[0] == '$';
        for (size_t j = 1; j < w.size() && price; j++) if (!isdigit((unsigned char) w[j])) price = false;
        if (!price) {
            out += w;
            continue;
        }
        long long cents = stoll(w.substr(1)) * (100 - discount);
        char buf[32];
        snprintf(buf, sizeof(buf), "$%lld.%02lld", cents / 100, cents % 100);
        out += buf;
    }
    return out;
}

JavaScript

var discountPrices = function(sentence, discount) {
    var words = sentence.split(" ");
    for (var i = 0; i < words.length; i++) {
        var w = words[i];
        if (w.length < 2 || w[0] !== "$") continue;
        var digits = true;
        for (var j = 1; j < w.length; j++) {
            if (w[j] < "0" || w[j] > "9") { digits = false; break; }
        }
        if (!digits) continue;
        // At most 10^10 * 100 = 10^12 cents: exact in a double.
        var cents = Number(w.substring(1)) * (100 - discount);
        var frac = cents % 100;
        words[i] = "$" + ((cents - frac) / 100) + "." + (frac < 10 ? "0" : "") + frac;
    }
    return words.join(" ");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings