首页 > itarticle > greatest common divisor

greatest common divisor

admin 11月 12, 2020 0

GCD of 2 integer

recursive call: put smaller number first

1
2
3
4
5
 
public int (int a, int b){
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

example:

gcd(12,18)=> gcd(6,12)=>gcd(0,6)=>6

gcd(8,2)=>gcd(2,8)=>gcd(0,2)=>2

GCD of an int array

1
2
3
 
gcd(a, b, c) = gcd(a, gcd(b, c)) 
             = gcd(gcd(a, b), c) 
             = gcd(gcd(a, c), b)

assume valid input, no 0s

1
2
3
4
5
6
 
public int (int[] nums) {
	int result = nums[0];
	for (int i = 1; i < nums.length; ++i)
		result = gcd(result, nums[i]);
	return result;
}

Question:

can reach:

Given 2 points (x1,y1), (x2,y2), determine whether point1 can move to point2.

Assume

Rules: (x1,y1) => (x1+y1,y1) or (x1,y1) => (x1,y1+x1)

first thought (TLE)

1
2
3
4
5
6
7
 
public boolean canReach(int x1,int y1,int x2,int y2) {
	if(x1 > x2 || y1 > y2)
		return false;
	if(x1 == x2 && y1 == y2)
		return true;
	return canReach(x1+y1, y1, x2, y2) || canReach(x1, y1+x1, x2, y2);
}

from point2 to point1 would be better

1
2
3
4
5
6
7
 
public boolean canReach(int x1,int y1,int x2,int y2) {
	if(x1 > x2 || y1 > y2)
		return false;
	if(x1 == x2 && y1 == y2)
		return true;
	return canReach(x1, y1, x2-y2, y2) || canReach(x1, y1, x2, y2-x2);
}

optimize in path

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
public boolean canReach(int x1, int y1, int x2, int y2) {
	if (x1 > x2 || y1 > y2)
		return false;
	if (x1 == x2 && y1 == y2)
		return true;
	if (x1 == x2 || y1 == y2) {
		if (x1 == x2 && (y2 - y1) % x1 == 0)
			return true;
		else if (y1 == y2 && (x2 - x1) % y1 == 0)
			return true;
		else
			return false;
	}
	return canReach(x1, y1, x2 - y2, y2) || canReach(x1, y1, x2, y2 - x2);
}

GCD

According to the definition of Greatest Common Divisior, if m is any integer, then gcd(a + m * b, b) = gcd(a, b). Therefore, the gcd of (a + b, b), (a, a + b), (a - b, b) and (a, a - b) will be the same as the gcd of (a, b). Therefore, in order to move to the target point, the gcd of the target point should be equal to the gcd of the starting point.

1
2
3
 
public boolean canReach(int x1, int y1, int x2, int y2) {
	return gcd(x1, y1)== gcd(x2, y2); 
}

Leetcode 149. Max points on a line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 

 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public int maxPoints(Point[] points) {
        // use O(n^2) to find all pair, store slope as key
        if(points == null)
            return 0;
        int result = 0;
        // map: slope as key, count as val
        Map<String,Integer> map = new HashMap<>();
        // loop over all points
        for(int i=0; i<points.length; ++i){
            // check all lines with i and j
            // find max point on a line except i and overlap
            int max = 0, overlap = 0;
            map.clear();
            for(int j=i+1; j<points.length; ++j){
                // x,y pair as slope
                int x = points[j].x - points[i].x;
                int y = points[j].y - points[i].y;
                if(x == 0 && y == 0){   // points overlap
                    overlap ++;
                    continue;
                }
                int gcd = getGCD(x,y);
                // vertical and horizontal covered
                x /= gcd;
                y /= gcd;
                String key = x + "," + y;
                if(map.containsKey(key))
                    map.put(key,map.get(key)+1);
                else
                    map.put(key,1);
                // max for one start point
                max = Math.max(max,map.get(key));
            }
            // start point + other point on line + same as start
            result = Math.max(result,max+overlap+1);
        }
        return result;
    }
    private int getGCD(int a,int b){
        return a == 0 ? b : getGCD(b%a,a);
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能