Programming Pearls Chapter 1 Problem 6

What would you recommend to the programmer if, instead of saying that each integer could appear at most once, he told you that each integer could appear at most ten times? How would your solution change as a function of the amount of available storage?

package avdongre.programming.pearls;

/**
 * Programming Pearls Chapter 1 Problem 6 
 * 
 * 6. What would you recommend to the  programmer if, instead of saying that 
 * each integer could appear at most once, he told you that each integer 
 * could appear at most ten times? How would your solution change as a 
 * function of the amount of available storage?
 * 
 * @author adongre
 *
 */

public class SolutionChapterOneProblemSix {

	public void solve(int range, int repetition, int[] array) {
		/*
		 * Since each number can appear at most 'repetition' times Let us have bit-vector
		 * with size equal to range * 10
		 */
		java.util.BitSet storage = new java.util.BitSet(range * repetition);
		for (int i = 0; i < array.length; i++) {
			/*
			 * Find the slot where the new number should be stored in the form
			 * of bit ON or OFF
			 */
			int currentNumber = array[i];
			/* Identify the slot start */
			int slotStart = (currentNumber * range) - range;
			/* iterate over the slot */
			int slotEnds = slotStart + repetition - 1;
			for (int j = slotStart; j < slotEnds; j++) {
				if ( storage.get(j) == false) {
					storage.set(j);
					break;
				}
			}

		}
		for ( int i = 0; i < storage.length(); i++) {
			if ( storage.get(i)) {
				System.out.println((i / range) + 1);
			}
		}
	}

	public static void main(String[] args) {
		SolutionChapterOneProblemSix sol = new SolutionChapterOneProblemSix();
		{
			int [] array = new int [] {1,2,3,4,5,1,2,3,4,5,1,2,3,4,5};		 
			sol.solve(5, 5, array);
		}
	}

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s