The Min Missing Natural Number – Another Solution
4 Comments Published February 13th, 2015 in DevelopmentI came across this interesting problem on typeocaml.com web site:
Given a unordered list of distinct natural numbers, find out the minimum natural number that is not in the list.
For example, if the list is [8; 2; 3; 0; 12; 4; 1; 6], then 5 is the minimum natural number that is missing.
O(n) solution is desired.
The solution provided on the web page has a complexity of O(n) in the average case as mentioned in the article. However the worst case complexity is O(n^2) if the randomly picked number is always the next smallest (or largest) number.
Here I describe my solution with a similar (?) complexity. My algorithm generates a list of ranges as the numbers are read. Every range has a minimum and a maximum value of the contiguous numbers that were not seen so far at the input. The list of ranges is updated and kept sorted for each input element. The solution is the lower bound in the first range element after all inputs are consumed.
First step is to initialize the range list with a single range element with lower bound being zero and upper bound being the first input less one. If the input array contains only one element, then the list contains one range, and the solution is the lower bound in that range, i.e zero.
For the rest of the input, if the next element e is:
- equal to the upper bound of an existing range (l, u), update that range with (l, e-1).
- equal to the lower bound of an existing range (l, u), update that range with (e+1, u).
- equal to an existing range with identical upper and lower bounds (e,e), remove the range from the list.
- inside an existing range (l, u), split that range into two: (l, e-1) and (e+1, u)
- larger than the entire range list, add a new range (e, e) at the end of the list.
Here is how the algorithm works on the input array {8, 2, 3, 0, 12, 4, 1, 6} mentioned in the article:
e L
8 (0,7) Initialize the list
2 (0,1) (3,7) e in 1st range, split
3 (0,1) (4,7) e in 2nd range, update lower bound
0 (1,1) (4,7) e in 1st range, update lower bound
12 (1,1) (4,7) (12,12) e larger than list, add range
4 (1,1) (5,7) (12,12) e in 2nd range, update lower bound
1 (5,7) (12,12) e equal to 1st range, remove
6 (5,5) (7,7) (12,12) e in 1st range, split
The answer is the lower bound of the first range, i.e. 5.
At every step a new range can be added, removed or the list size doesn’t change. On the average the number of the ranges is nearly constant which gives a complexity of O(n).
In the worst case a new range is added at each step which gives a complexity of O(n^2).
A detailed complexity analysis or any type of comment is greatly appreciated.
When you hit run, you get following message:
[2009-04-25 01:00:24 – Emulator] emulator: ERROR: unknown virtual device name: ‘my_avd’
[2009-04-25 01:00:24 – Emulator] emulator: could not find virtual device named ‘my_avd’
Solution:
Create a system variable called ANDROID_SDK_HOME and point it to users folder. Ex: C\Users\UserName\
Solving the Motorcycle Madness Upgrade Problem
7 Comments Published May 28th, 2009 in Entertainment, tips&tricksProblem definition:
Given your balance, pick a subset of upgrades such that summation of Power, Traction and Aerodynamics are maximized and summation of costs doesn’t exceed balance. Problem can be found on this page: http://apps.facebook.com/motorcycle_madness/upgrade.php
Solution:
We will use linear programming method. Let’s use an example here. For the initial problem:
Balance: $73,845
Upgrades available: Continue reading ‘Solving the Motorcycle Madness Upgrade Problem’
MySDL-02: All-in-one solution for SDL with Windows Mobile 5.0 Pocket PC SDK (ARMV4I)
7 Comments Published May 6th, 2009 in DevelopmentFinally I could pack this up and second version is ready.
This is a all-in-one solution for those who are tired or scared of downloading/compiling/fixing SDL and SDL libraries for Pocket PC. I have gathered some handy libraries into a VS2008 solution and all files you need are compiled without any pain. I also provide binaries too. Hope this helps.
The answer from Apple on why should I spend more on a Mac doesn’t make sense:
When you compare the cost of a PC and factor in the additional software, memory, and other extras you have to buy to go along with it, the difference in price between a Mac and PC isn’t as great as most people believe.
Windows Live Messenger unable to connect with error code 80040200 – solution Vista
2 Comments Published March 19th, 2009 in tips&tricksI have tried the method in this article and it worked like charm. Only catch was, when I tried to rename Windows Live Contacts folder, access denied. So I had to use Unlocker to stop processes accessing it. Thanks Robin!
MySDL: All-in-one solution for SDL with Windows Mobile 5.0 Pocket PC SDK (ARMV4I)
10 Comments Published January 3rd, 2009 in DevelopmentEdit: This post is obselete now. Please see MySDL-02.
This is a all-in-one solution for those who are tired or scared of downloading/compiling/fixing SDL and SDL libraries for Pocket PC. I have gathered some handy libraries into a VS2008 solution and all files you need are compiled without any pain. I also provide binaries too. Hope this helps.
Continue reading ‘MySDL: All-in-one solution for SDL with Windows Mobile 5.0 Pocket PC SDK (ARMV4I)’
SDL PocketPC development hints & problems & solutions
4 Comments Published January 3rd, 2009 in Development, tips&tricksNOTE: Using VC2008 compiler, SDL and Windows Mobile 5.0 Pocket PC SDK
Project Configurations
There is ONLY one configuration: Windows Mobile 5.0 Pocket PC SDK (ARMV4I).
I choose WM5 because PPC2003 is enough old and WM6 is too new-there are still many devices with WM5. Thus WM5.0 keeps a balance between portability and new technology. I also think that there is no need to use latest WM SDK for a SDL project, as it doesn’t use OS functions, though.
Continue reading ‘SDL PocketPC development hints & problems & solutions’
Solution: Management console not working in Vista
2 Comments Published September 14th, 2008 in tips&tricksFor some time till today, whenever I right click on My Computer and select Manage, nothing was happenning. I have fixed it up now but while browsing around, I haven’t seen a solid and a complete solution, so here is a sum up what I have done for the fix.
Symptom: Right click on My Computer, select Manage OR hit Start->Run, type compmgmt.msc and click Ok will NOT open up Computer Management Console on a Vista computer.
Continue reading ‘Solution: Management console not working in Vista’
Shadows and Shadow Mapping
Shadows has remained as a big challenge for years in computer graphics. There are many ways to achieve “shadows”, some methods require special data structures and coding, and some has quality and speed falloffs. Continue reading ‘Shadow Mapping and Back-face Culling’