java - Longest Subsequence where an integer in the output is 5 times greater than the previous -

-

i'm practicing uva problems , i'm stuck in this. need longest subsequence consecutive integers 5 times greater previous

sample input: 7, 100, 3, 80, 3, 5, 18, 25, 73, 125 output: 3 (5, 25, 125)

i thought of solution take n^n compare integer rest of integers, not ideal. possible faster solution?

if traverse list , build map of values seen far, mapped length sequence ending in number, can solve problem in o(n).

given sample list of 7, 100, 3, 80, 3, 5, 18, 25, 73, 125, resulting map be:

7   → 1    ⇐ not divisible 5, length=1 100 → 1    ⇐ 100 / 5 = 20, 20 hasn't been seen, length=1 3   → 1    ⇐ not divisible 5, length=1 80  → 1    ⇐ 80 / 5 = 16, 16 hasn't been seen, length=1 3          ⇐ skipped since 3 in map 5   → 1    ⇐ 5 / 5 = 1, 1 hasn't been seen, length=1 18  → 1    ⇐ not divisible 5, length=1 25  → 2    ⇐ 25 / 5 = 5, , 5 has length 1, length=2 73  → 1    ⇐ not divisible 5, length=1 125 → 3    ⇐ 125 / 5 = 25, , 25 has length 3, length=3

longest sequence 3, ending in value 125. can build sequence reverse-calculating it: 125 → 25 → 5

here code (not using java 8 features):

private static void printlongesttimesfivesequence(int ... input) {     map<integer, integer> valuelengthmap = new hashmap<>();     int longestlength = 0, longestvalue = 0;     (int value : input) {          // find length of sequence ending in 'value'         int length = 1;         if (value % 5 == 0) {             integer prevlength = valuelengthmap.get(value / 5);             if (prevlength != null)                 length += prevlength;         }          // if length new longest sequence, remember         if (length > longestlength) {             longestlength = length;             longestvalue = value;         }          // remember length of sequence ending in 'value' if first time seen,         // or if longer seen (e.g. 15, 3, 15)         integer currentlength = valuelengthmap.get(value);         if (currentlength == null || currentlength < length)             valuelengthmap.put(value, length);     }      // build sequence ending in value of remembered longest sequence     int[] sequence = new int[longestlength];     (int = longestlength - 1, value = longestvalue; >= 0; i--, value /= 5)         sequence[i] = value;      // print result     system.out.println(longestlength + " " + arrays.tostring(sequence)); }

test

printlongesttimesfivesequence(7, 100, 3, 80, 3, 5, 18, 25, 73, 125); printlongesttimesfivesequence(10, 50, 2); printlongesttimesfivesequence(15, 3, 75, 15, 75); printlongesttimesfivesequence(4, 20, 100, 20, 100); printlongesttimesfivesequence(5, 25, 125, 25, 125); printlongesttimesfivesequence();

output

3 [5, 25, 125] 2 [10, 50] 3 [3, 15, 75] 3 [4, 20, 100] 3 [5, 25, 125] 0 []

Comments

Post a Comment

Popular posts from this blog

mysql - Dreamhost PyCharm Django Python 3 Launching a Site -

-
i'm new python/django , created simple django website using pycharm. site works fine running on computer, i'm lost when comes taking site onto host (dreamhost). i'm able upload files correct directories fine, , believe made correct changes database on mysql. i'm not sure go there though. right now, page shows files rather site. direction appreciated. much! you should not run django application using python manage.py runserver on production. how run application on django depends on server (apache, nginx) want use for apache - https://docs.djangoproject.com/en/1.10/howto/deployment/wsgi/modwsgi/ for nginx - https://www.digitalocean.com/community/tutorials/how-to-serve-django-applications-with-uwsgi-and-nginx-on-ubuntu-14-04 the mysql database should, of course, exist , have correct credentials. or, if choose use sqlite, file should accessible, readable , writable www-user (may different depending on linux distributive)
Read more

java - Sending SMS with SMSLib and Web Services -

-
i have made rest web service send smss using hsdpa usb modem. using smslib in java send smss. every time web service invoked, create gateway start service, send message, stop service , remove gateway. takes 20 seconds each message. found starting service takes lot of time. part of code use send smss service.getinstance().addgateway(gateway); service.getinstance().startservice(); outboundmessage msg = new outboundmessage(phonenumber, message); if (service.getinstance().sendmessage(msg)) { result = "message sent successfully!!"; } else { result = "could not send message."; } service.getinstance().stopservice(); service.getinstance().removegateway(gateway);//remove gateway is there way can start service once if not started , use send message when ever web service invoked? why dont group messages , send in 1 go? service.getinstance().sendmessages(messa...
Read more

java - How to resolve The method toString() in the type Object is not applicable for the arguments (InputStream) -

-
i'm trying read json file local machine. @path("/") public class jsonparsing { file f = new file("file.json"); if (f.exists()){ inputstream = new fileinputstream("file.json"); string jsontxt = ioutils.tostring(is); system.out.println(jsontxt); jsonobject json = new jsonobject(jsontxt); string = json.getstring("1000"); system.out.println(a); } } but i'm getting error in tostring() method. possible read .txt file containing json object local machine? if possible, how done? firstly: whenever ask question- add imports well. secondly: yes possible read .txt file containing json object. steps: 1. add maven dependency in pom.xml - <dependency> <groupid>com.googlecode.json-simple</groupid> <artifactid>json-simple</artifactid> <version>1.1.1</version> </dependency> or add jar of dependency. 2.import...
Read more