Tag Archive for 'combination'

Problem 53 required one to find all the generated numbers of nCr, 1 <= n <= 100, which are greater than a million. And the solution was all too simple – Pascal Triangle.

Each row of the Pascal Triangle is a series of nCr. So all that was needed to be done was to generate a triangle to a depth of 100, and find all the large numbers.

One small modification that I could have done is – not all numbers needed to be calculated. Once a number greater than a million is found, all successive number in that series till the halfway mark will be greater than million. Remembering just the smallest number greater than a million should have sufficed.

public class Problem_53 {
	public static int solve() {
		int count = 0;

		Map<Settings, Object> settings = new HashMap<Settings, Object>();
		settings.put(Settings.ONLY_RIGHT_HALF_GENERATION, true);

		PascalTriangle pascalTriangle = new PascalTriangle(settings);
		for (int i = 1; i <= 100; i++) {
			int sum = 0;
			for (double num : pascalTriangle.constructNextLevel()) {
				if (num < 1000000)
					break;
				sum++;
			}
			count += sum > 0 ? (i % 2 == 0 ? 2 * sum - 1 : 2 * sum) : 0;
		}

		return count;
	}

	public static void main(String[] args) {
		System.out.println(Problem_53.solve());
	}
}

The Pascal Triangle Generator

public class PascalTriangle {
	private List<List<Double>> m_triangle;
	private int m_currentLevel;
	private boolean m_onlyRightHalfGeneration;

	public PascalTriangle(Map<Settings, Object> settings) {
		m_currentLevel = 0;
		initTree();
		m_onlyRightHalfGeneration = isOnlyRightHandGenerationEnabled(settings);
	}

	/**
	 * Create a new tree and initialize the Level 0
	 */
	private void initTree() {
		m_triangle = new ArrayList<List<Double>>();
		List<Double> levelZero = new ArrayList<Double>();
		levelZero.add(new Double(1));
		m_triangle.add(levelZero);
	}

	/**
	 * Check if the property ONLY_RIGHT_HALF_GENERATION is enabled by the user
	 *
	 * @param settings The settings provided by the user
	 * @return true if the ONLY_RIGHT_HALF_GENERATION is set to true
	 */
	private boolean isOnlyRightHandGenerationEnabled(Map<Settings, Object> settings) {
		return !settings.containsKey(Settings.ONLY_RIGHT_HALF_GENERATION) ? false : (Boolean) settings
		        .get(Settings.ONLY_RIGHT_HALF_GENERATION);
	}

	/**
	 * Construct the next level of the Pascal Triangle.
	 *
	 * @return the new level added to the Pascal Triangle
	 */
	public List<Double> constructNextLevel() {
		return m_onlyRightHalfGeneration ? constructRightHaflTreeNextLevel() : constructLeftHaflTreeNextLevel();
	}

	/**
	 * Construct the left half of the tree
	 */
	private List<Double> constructLeftHaflTreeNextLevel() {
		List<Double> nextLevel = new ArrayList<Double>();
		Double prevNum = new Double(0);
		for (Double num : m_triangle.get(m_currentLevel)) {
			nextLevel.add(prevNum + num);
			prevNum = num;
		}
		if (m_currentLevel % 2 != 0)
			nextLevel.add(2 * prevNum);

		m_triangle.add(nextLevel);
		m_currentLevel++;

		return nextLevel;
	}

	/**
	 * Construct the right half of the tree
	 */
	private List<Double> constructRightHaflTreeNextLevel() {
		List<Double> prevLevel = m_triangle.get(m_currentLevel);
		List<Double> nextLevel = new ArrayList<Double>();

		Double prevNum = prevLevel.get(0);
		if (m_currentLevel % 2 != 0)
			nextLevel.add(2 * prevNum);

		for (int i = 1; i < prevLevel.size(); i++) {
			Double num = prevLevel.get(i);
			nextLevel.add(prevNum + num);
			prevNum = num;
		}
		nextLevel.add(new Double(1));

		m_triangle.add(nextLevel);
		m_currentLevel++;

		return nextLevel;
	}

	/**
	 * Settings for the Pascal Triangle Generator
	 *
	 * @author AnuvratSingh
	 */
	public enum Settings {
		ONLY_RIGHT_HALF_GENERATION
	}
}

Popularity: 9% [?]