Output mistake but cant find where the error is..


  • 2
    Q

    The logic is quite simply. For every two points, either they can form a line represented by kx+m=y or they can be seen as x=k (where k and m are constant), then find how many points that meet each function and return the max number. But there is a wrong test case:

    Input: [(0,9),(138,429),(115,359),(115,359),(-30,-102),(230,709),(-150,-686),(-135,-613),(-60,-248),(-161,-481),(207,639),(23,79),(-230,-691),(-115,-341),(92,289),(60,336),(-105,-467),(135,701),(-90,-394),(-184,-551),(150,774)]

    Output: 11

    Expected: 12

    public int maxPoints(Point[] points) {

        //length of the points
        int length=points.length;
        //one point and two points cases
        if(length==0){
            return 0;
        }
        if(length==1){
            return 1;
        }
        
        double k=0;
        double m=0;
        int max=0;
        int counter=0;
        //for every two points
        for(int i=0;i<length;i++){
            for(int j=i+1;j<length;j++){
                //if the line is like x=m, which means the x values of two points are the same
                if(points[j].x-points[i].x==0){
                    //for each points if it got the same x
                    for(int p=0;p<length;p++){
                        if(points[p].x==points[j].x){
                            counter++;
                        }
                    }
                    
                    if(counter>max)max=counter;
                    
                }
                //the line is like y=kx+m
                else{
                    k=(double)(points[j].y-points[i].y)/(points[j].x-points[i].x);
                    m=(double)(points[j].y*(points[j].x-points[i].x)-points[j].x*(points[j].y-points[i].y))/(points[j].x-points[i].x);
                    //for each point, if they meet the function y=kx+m
                    for(int q=0;q<length;q++){
                        if(k*points[q].x+m==points[q].y){
                            counter++;
                        }
                    }
                    if(counter>max){
                        max=counter;
                    }
                }
                counter=0;
            }
        }
        
        return max;
    }
    

    I've got other answers but I just cant figure out what the problem is with this one. Could anyone help me please?


  • 0
    S

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


  • 0
    Q
        //i guess the problem is causing by double division
        //i use divide int to avoid dividing double number by a double number
        private boolean judge(Point p1, Point p2, Point p3) {
            if(p2.x == p1.x){
                return p3.x == p1.x;
            }else{
         	    //y-y1 = (y2-y1)*(x-x1)/(x2-x1)
    		    int left = p3.y - p1.y;
    		
    		    int right_1 = (p2.y - p1.y)*(p3.x - p1.x);
    		    int right_2 = p2.x - p1.x;
    		
    		    int right = right_1 / right_2;
    		    int right_mod =  right_1 % right_2;
    		
    		    return left == right & right_mod == 0;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.