Project Euler #152: Writing 1/2 as a sum of inverse squares

Sort by

recency

|

10 Discussions

|

  • + 0 comments

    The key to solve this problem is to properly process multiple of primes. It should be done in reverse order so that for given prime we only take into account those multiples that have only preceeding prime factors and don't have next prime factors. For example for 7 we would have: 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 84 and 98. There is no multiple of 11 and 13. For each prime multiples we calculate all possible sums. In processing those sums we backtrack if the current sum is less then 0 or we can't get rid of this prime in the fraction.

  • + 0 comments

    If this is out of school, totally understand, but thought I would see if anybody could point me in the right direction within the rules of the competition. I've got a working solution in a reasonable amount of time for the base euler 152 problem with the fraction of 1/2 for up to 100, but am still failing most of the test cases. What are some of the corner cases to consider in tracking down the missing combinations?

  • + 1 comment

    What is time/memory constraint for this problem ?

  • + 0 comments

    can anyone help me make this code faster

    class Permutation {

    static int answer = 0;
    static void combinationUtil(int arr[], int n, int r, int index,
                                int data[], int i,int d)
    {
        if (index == r)
        {
            float k =0;
            for (int j=0; j<r; j++)
            {
                k += 1/(Math.pow(data[j],2));
            }
            if((float)1/d == k)
                answer++;
        return;
        }
    
        if (i >= n)
        return;
    
        data[index] = arr[i];
        combinationUtil(arr, n, r, index+1, data, i+1,d);
    
    
        combinationUtil(arr, n, r, index, data, i+1,d);
    }
    
    static void printCombination(int arr[], int n,int d)
    {
        int r=0;
        while(r <= n)
        {
            int data[]=new int[r];
            combinationUtil(arr, n, r, 0, data, 0,d);
            r++;
        }
    }
    
    public static void main (String[] args) {
        Scanner s = new Scanner(System.in);
        int d = s.nextInt();
        int n = s.nextInt();
        int arr[] = new int[n-1];
        for(int i = 2;i <= n;i++)
        {
            arr[i-2] = i;
        }
        printCombination(arr, n-1,d);
        System.out.println(answer);
    }
    

    }

  • + 0 comments

    I didnt get what the question is?