Problem 24: Lexicographic permutations

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Solution:
One of the most easiest problems till now, All you've to do is take the numbers into a string, generate all possible permutations, store them in an array, and sort the array, and then find the permutation stored at the millionth position.

The java code:

import java.util.ArrayList;
import java.util.Collections;

public class Prob24 {
static ArrayList<Long≫ numPermutations = new ArrayList<Long≫();

public static void main(String args[]) {
System.out.println();
permutation("","0123456789");
Collections.sort(numPermutations);
System.out.println(numPermutations.get(1000000-1)); 
}


private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) 
    {
     numPermutations.add(Long.parseLong(prefix));
    }
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}
 
 
}

Problem 23: Non-Abundant Sums

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Solution:
I'm returning back to java and projecteuler after a long long time, been busy with work and life, not in college anymore :( 

Now to cut the crap, I used brute-force for this, first made a list of all abundant numbers, than using two loops, found numbers which can be created using summing two Abundant numbers, now since we know that all numbers above this limit are sum of two or more abundant numbers, I created a boolean array till this number and marked all the indexes which I could get as a sum of two abundant numbers, I added all the unmarked indexes and eureka! I had my answer.

As usual, java code below:

package euler;
import java.util.ArrayList;

public class Prob23 {

 
 public static void main(String[] args) 
 {
  
  ArrayList <Integer> AbundantStore = new ArrayList<Integer>();
  for( int i =12 ; i <= 28123; i++ )
  {
   if(abundant_Checker(i))
   {
    AbundantStore.add(i);
   }
  }
  
  boolean  nonAbundantNumberMark[] = new boolean[28124];
  for(int i = 0 ; i < AbundantStore.size(); i++)
  {
   for(int j= i; j < AbundantStore.size(); j++)
   { 
    int abundantNumberSum = (AbundantStore.get(i)+AbundantStore.get(j));
    if(abundantNumberSum <= 28123)
     nonAbundantNumberMark[abundantNumberSum] = true;
   }
  }
  
  int nonAbundantNumberSum = 0;
  for( int i = 0 ; i <= 28123; i++ )
  { if(!nonAbundantNumberMark[i])
   {
    nonAbundantNumberSum += i;
   }
   
  }
  System.out.println(nonAbundantNumberSum);
 }

 

 
 public static boolean abundant_Checker(int num)
 {
  if(sum_of_factor(num)> num)
  return true;
  else
  return false;
 }
 
 
 
 
 public static int sum_of_factor(int num)
 {
  int sum =0;
  for(int i= 1 ; i<=num/2 ; i++ )
  {
   if(num%i ==0)
    sum +=i;
  }

 return sum;
 }

}