c - Least cost algorithm -
i came across question in contest , couldn't think of algorithm other brute force method of checking , computing cost every digit in string , outputting least cost.
a string consisting of digits (0-9) given , integer query
given. need make sure of digits in string (0-9) repeated >= query
times. done replacing individual digits in string digit, , cost of operation difference between replaced digit , digit replacing with. find minimum cost make sure @ least 1 digit exists in string >= query
number of times.
is there algorithm this?
you don't need initial string - need number of times each digit met in it. can convert string array of 10 ints- number of times each of digits met in string. there on can use brute force - each digit x, assume want have @ least q(query) x-s. iterate on remaining digits , greedily first convert digits closer x(again in array of counts instead of original string), don't need convert consider number of times given digit met. algorithm end complexity in order of o(10^3 + n) can think.
Comments
Post a Comment