Project Euler, is a wonderful site dedicated to fun around mathematical puzzles and problems. In their own words,
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
A problem is posted every week and many of them require one to write code to solve them. More than the code, it wants the user to go over the internet, read more on the problem and then build an optimal solution. Per their claim, most of the problems can be solved under a few seconds. If not, then a better solution exists.

I came across the project in the first week of this year (2011) and has been working to solve these problems as and when I find time. Today, I solved the 50th problem (they have over 317 as of today) which promotes me to Level 2.

In line with my theory of open-code, I have shared the Java code for all the puzzles under the name of Project Maer, for anyone to look at. Maer, pronounced [mˈɑɛr], is an adjective to represent useful, good or fit in Sindarin, the elvish language. Expect more posts under the labels for now I start to blog on the problem I solve.

Code is freely available at http://jerry.svn.sourceforge.net/viewvc/jerry/maer/ as a downloadable Eclipse project.

Note: A sincere request not to work up the code to just complete the problems. The code can be looked at, and optimized if a better solutions exists.

written by Sandeep Gupta

Tuesday, May 3, 2011 at 4:08 PM

Problem: Given an array consisting of N integers, find the number with the maximum occurrences, majority element, given the assumption that the number occurs more than N/2 times in the array.

Solution: Given the assumption that the element occurs more than N/2 times in the array simplifies the solution a lot. This is so because if more than N/2 elements are the same, it implies that all other elements combined are less than N/2. Hence, the difference between the count of majority element and the count of non-majority numbers will always be positive. This approach can significantly simplify our code to the problem.

In the solution we consider the first element as the majority element and keep the count as 1. Now we compare the second (next) element with this element. If it is the same element we increase the count to 2, else decrease the count to ZERO and keep the first element as the majority element. Check the next element. If it is equal increase the count, else set the majority element to be the given current element and make the count as ONE.

This way, at the end of the traversal of the list, we will have the majority element with us. As comparison between two elements takes constant time, the code will run in O(n) time where n is the number of elements in the list.

/**
 * Copyright (C) 2011, Sandeep Gupta
 * http://www.sangupta.com
 * 
 * The file is licensed under the the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * 
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 */

public class MajorityElement {
 
 public static void main(String[] args) {
  int[] list = new int[] {1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 1, 2, 3, 4, 2, 2, 2};
  
  int count = 1;
  int majorityElement = list[0];
  for(int index = 1; index < list.length; index++) {
   if(majorityElement != list[index]) {
    if(count == 0) {
     majorityElement = list[index];
     count++;
    } else {
     count--;
    }
   } else {
    count++;
   }
  }
  
  System.out.println("Majority Element: " + majorityElement);
 }

}

Hope this helps.

written by Sandeep Gupta

Monday, May 2, 2011 at 1:25 PM

Problem: Find the number of set bits in a given Integer N.

Solution: At the first look the problem looks like a simple AND '&' operation query. Check for each bit whether it is set or not, and then return the value back. For an 2-byte value, it would take 16 operations, and for a 4-byte value 32-operations to find the number of set bits. In other words for any given Integer N, the operation will be O(constant) in terms of time-complexity. Can this time complexity be reduced further?

The answer is YES. The bitwise boolean operations help us in checking if a certain bit is on or not. Say for a given binary number 0010 stored as n, we do n & (-n), it would return us a value of 2 indicating that the current least most bit that is set represents 2 in decimal. For a number like 0110, the first operation will bring us a value of 2. If we subtract 2 from the original number, we get 0100 and now running the same operation results in a value of 4 (the next least set bit).

We can use the same principle along with recursion to find out the number of set bits in a given number. Keep finding the least set bit, subtract from the original number (reducing it every time) and keep counting. This way if a 4-byte number has only 1 bit set, we take only 1 operation to find the same, rather than 32, reducing our time complexity drastically.

/**
 * Copyright (C) 2011, Sandeep Gupta
 * http://www.sangupta.com
 * 
 * The file is licensed under the the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * 
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 */

public class Bits {
 
 public static void main(String[] args) {
  System.out.println(bits(15));
 }
 
 private static int bits(int n) {
  if(n == 0) {
   return 0;
  }
  
  int sub = n & -n;
  return 1 + bits(n - sub);
 }

}

Hope this helps.

written by Sandeep Gupta

at 8:56 AM