I 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\

Problem 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’

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.

Continue reading ‘Why should I spend more money on a Mac?’

From http://www.robinmajumdar.com/2009/01/28/windows-live-messenger-unable-to-connect-with-error-code-80040200-solution-in-windows-7/

I 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!

Continue reading ‘Windows Live Messenger unable to connect with error code 80040200 – solution Vista’

Edit: 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)’

NOTE: 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’

For 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’