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% [?]
Related posts:
0 Responses to “Project Euler : Pascal Triangle To Find nCr”