java - Given a stock of integers 0-9, what is the last number I can write before I run out of some integer? -


as title says, given stock of integers 0-9, last number can write before run out of integer?

so if i'm given stock of, 10 every number 0 9, last number can write before run out of number. example, stock of 2 can write numbers 1 ... 10:

1 2 3 4 5 6 7 8 9 10

at point stock ones 0, , cannot write 11. note if given stock of 3, still write numbers 1 ... 10, because 11 cost me 2 ones, leave stock ones @ -1.

what have come far:

public class numbers {  public static int numbers(int stock) {     int[] t = new int[10];     (int k = 1; ; k++) {          int x = k;         while (x > 0) {              if (t[x % 10] == stock) return k-1;             t[x % 10]++;             x /= 10;          }      } }  public static void main(string[] args) {     system.out.println(numbers(4));  }  }

with can correct answer big stock sizes. stock size of 10^6 code completes in ~2 seconds, , stock of 10^7 numbers takes whole 27 seconds. not enough, since i'm looking solution can handle stock sizes of big 10^16, need o(log(n)) solution.

this homework assignment, didn't come here without wrestling pickle quite time. have failed come similiar googling, , wolfram alpha doesn't recognize kind of pattern gives.

what have concluded far ones allways run out first. have no proof, so.

can come piece of advice? lot.

edit:

i have come , implemented efficient way of finding cost of numbers 1...n btilly's pointers (see post , comments below. marked solution). elaborate further after have implemented binary search finding last number can write given stock later today.

edit 2: solution

i had forgotten post, apologies not editing in solution earlier. won't copy actual implementation, though.

my code finding cost of number following:

first, let choose number, e.g. 9999. cost summing cost of each tens of digits so:

9 9 9 9 ^ ^ ^ ^ ^ ^ ^ roof(9999 / 10^1) * 10^0 = 1000 ^ ^ roof(9999 / 10^2) * 10^1 = 1000 ^ roof(9999 / 10^3) * 10^2 = 1000 roof(9999 / 10^4) * 10^3 = 1000

thus cost 9999 4000.

the same 256:

2 5 6 ^ ^ ^ ^ ^ roof(256 / 10^1) * 10^0 = 26 ^ roof(256 / 10^2) * 10^1 = 30 roof(256 / 10^3) * 10^2 = 100

thus cost 256 156.

implementing idea make program work numbers have no digits 1 or 0, why further logic needed. let's call method explained above c(n, d), n number getting cost for, , d d'th digit n working with. let's define method d(n, d) return d'th digit n. apply following logic:

sum = c(n, d)  if d(n, d) 1:     each k < d, k >= 0 :         sum -= ( 9 - d(n, k) ) * 10^(k-1);  else if d(n, d) 0:     sum -= 10^(d-1)

with program calculate correct cost number efficiently. after apply binary search finding number correct cost.

step 1. write efficient function calculate how stock needs used write of numbers n. (hint: calculate used write out numbers in last digit formula, , use recursion calculate used in other digits.)

step 2. binary search find last number can write amount of stock.


Comments

Post a Comment

Popular posts from this blog

javascript - RequestAnimationFrame not working when exiting fullscreen switching space on Safari -

request animation frame stops working when exiting fullscreen clicking on original space's safari window. fine if fullscreen mode canceled escape key or calling cancelfullscreen(). steps reproduce: open https://dl.dropboxusercontent.com/u/769042/prezi/safari-fullscreen.html click "draw raf", kittie appears click "fullscreen", go fullscreen click "draw raf", kittie appears go space original safari was, showing "click exit fullscreen mode", click anywhere, out fullscreen click "draw raf", nothing happens what handling click calling: window.requestanimationframe(draw); which draws on canvas context: function draw() { ctx.drawimage(img, math.random()*500|0, math.random()*400|0, 100, 100); } i checked .hidden , .visibilitystate, updated correctly. tested on osx 10.9.3, safari 7.0.4 (9537.76.4). has workaround/solution other switching old settimeout? this sounds webkit bug 88940 : using reque...
Read more

jsf - How to ajax update an item in the footer of a PrimeFaces dataTable? -

this visual of table have: +---------+------------+-------------------+ | header1 | header2 | header3 | +---------+------------+-------------------+ | row | input | calc'ed output | | row b | input b | calc'ed output b | | etc.. | etc.. | etc.. | +---------+------------+-------------------+ | total: total calc'ed output | +------------------------------------------+ and stripped-down code: <p:datatable id="mytable" value="#{mybean.somelist}" var="currentitem"> <p:column headertext="header1"> <h:outputtext value="#{currentitem.name}" /> </p:column> <p:column headertext="header2"> <pe:inputnumber value="#{currentitem.inputval}"> <p:ajax event="change" listener="#{mybean.changelistener}" update="outputval outputtotal...
Read more

jquery - Keeping Kendo Datepicker in min/max range -

when user types type in date outside of range, we're trying ensure date gets changed closest min/max. text displayed in date picker not change though thought script changing value() @(html.kendo() .datepickerfor(x => x.dob) .max(new datetime(datetime.now.addyears(-18).year, datetime.now.addyears(-18).month, datetime.now.addyears(-18).day)) .min(new datetime(datetime.now.addyears(-70).year, datetime.now.addyears(-70).month, datetime.now.addyears(-70).day)) .events(e=>e.change("ondobchange")) .htmlattributes(new { required = "required", ng_model = "model.dob" })) <p ng-show="validatestate.submitted && frmmain.dob.$invalid" class="help-block">please select</p> <script> function ondobchange(e) { var d...
Read more