Project Euler #148: Exploring Pascal's triangle.

Sort by

recency

|

13 Discussions

|

  • + 0 comments

    To beat all test cases I had convert row and column values to base 7 and count all triangles in Sierpinski triangle in every cell. My algorithm has 0(log7)^3 complexity. I had wrong answers due to special case for row or column = 0. So keep in mind this special case.

  • + 0 comments

    I have tried sum of all natural number ie for 8th row no of elements is S(8) for 8 row and 5 col it is S(8) - S( 8 - 5)

    similerly there is some pattern in no divisible by 7 since number for row 14 = S(14) - S( 14 - 14) - (S(14/7) * S(6))

  • + 1 comment
    import math
    f=math.factorial
    result=[]
    tc=int(raw_input())
    for i in range(tc):
    	n_row,n_col=raw_input().split(' ')
    	count=0
    	for r in range(int(n_row)):
    		c=0
    		while c<int(n_col) and c<r+1:
    			value=(f(r)/(f(c)*f(r-c)))
    			if value%7!=0:
    					count=count+1	
    			c=c+1	
    	result.append(count)
    
    for i in result:
    	print i
    

    I'm getting timed out!

  • + 0 comments

    Is anyone getting the same answer as I got? my output: 12 3842 2852 for input: 3 5 3 100 100 100 50; As per the best of my knowledge I have written correct logic for program. So can you tell me whether my second and third output number is wrong or right?why?

      -
  • + 0 comments

    Got it for N == R. But not getting it right when R < N. Need to work on it. Any clue?

    private static long pascal(int N, int R) { long count = 0; long div71 = 0; // divisible by 7 forming big pattern starting after row 49 long div72 = 0; // divisible by 7 forming small pattern starting after row 7 long div7 = 0; // Divisible by 7 long total = 0; int i = 0;

        long n = N;
        i = 0;
        while (n >= 49) {                
            div71 = div71 + i * (48 * 49)/2;
            div72 = div72 + (i+1) * (6 * 7)/2 * (6 * 7)/2;
            i++;
            n = n - 49;
        }
    
        if(N > 7 || n > 0) {
            if(N >= 49) 
                div71 = div71 + i*(48*49/2) - i*(48-n)*(49-n)/2;
            else if(n > 7) {
                i = 0;
                while(n > 7) {
                    div72 = div72 + (i)*(6*7)/2;
                    n = n - 7;
                    i++;
                }
    
                if(n > 0) {
                    div72 = div72 + (i)*(6*7)/2 - (i)*(6-n)*(7-n)/2;
                }
            }
        }
    
        if(R >= N)
            total = N * (N+1)/2;
        else {
            total = R*(R+1)/2 + (N-R)*R;
        }
    
        div7 = div71 + div72;
    
        count = total - div7;
    
        System.out.println("N: " + N + " R: " + R + " Total: " + total + " Count: " + count);
    
        return count;
    }