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^5sentence consists of lowercase English letters, digits, ' ' and '$'sentence has no leading or trailing spaces, and words are separated by a single spaceevery price is a positive number without leading zerosevery price has at most 10 digits0 <= discount <= 100
Hints for Apply Discount to Prices
Hint 1
Split the sentence on spaces and treat each word independently.
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.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). Printcents / 100, a dot, andcents % 100padded 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
- Split
sentenceon single spaces. - For each word, check that it is
'$'followed by at least one digit and only digits. - For a price
p, computecents = p · (100 - discount)in 64-bit arithmetic and rewrite the word as'$' + (cents / 100) + '.' + two-digit (cents % 100). - 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.99can 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