Google Interview Question
Software Engineer / DevelopersCountry: India
These are just the Catalan numbers. It has a simpler and more efficient one-term recurrence (look it up on Wikipedia) which you can use to compute the nth number in O(n) time.
iterative version
public int chords(int n)
{
if(n == 0) return 1;
int[] table = new int[n + 1];
table[0] = 1;
table[1] = 1;
for(int i = 2; i <= n; i++) {
for(int j = 0; j < i; j++) {
table[i] += table[j] * table[i - 1 - j];
}
}
return table[n];
}
Catalon number is the Solution
2 points 1
4 points 2
6 points 5
8 points 14
Catalon number values C1 = 1, C2 = 2, C3= 5, C4 = 14
Cn= (2nCn)/(n+1)
How did u get 2 for 4 points and 5 for 6 points?
if two chords can share a point the it will be 5 for 4 points and if they cannot, answer will always be two if 2n>=4
Only the parallel chords is not the answer. For instance, with 6 points, we can draw a hexagon and select any group of alternate edges, thus drawing 3 non-intersecting chords.
The number can be found using the following recursion I think:
T(n) = 2n x T(n-1)
The logic behind above recursion is that we can choose any two adjacent points, then any non-intersecting set of (n-1) chords on rest 2n-2 points, will form set of n non-intersecting chords with a chord using these two point, hence on 2n points.
The above recursion can be solved to give T(n) = 2^(n-1) x n!
How did you arrive at 5 for 4 points.
I guess you have joined all points to form a Quadrilateral and then made diagonal.
I am not sure if you can have 2 chords starting from the same point.
So for the case of 4 points there can only be 2 chords possible.
How did you arrive at 5 for 4 points.
I guess you have joined all points to form a Quadrilateral and then made diagonal.
I am not sure if you can have 2 chords starting from the same point.
So for the case of 4 points there can only be 2 chords possible.
For 4 points i think you have joined the vertices to form a quadrilateral and then joined a diagonal.
If its not intersecting then i think you cannot have 2 chords fro the same point.
Hence for 4 points only 2 chords are possible
If two chords cannot share a point, then this problem is not at all interesting. Answer will always be 2 if 2n>=4
neen not...
let say there are six points numbered- 1,2,3,4,5,6
one possible way is 1-2,3-4,5-6 or 2-3,4-5,6-1
other can be 1-4,2-3,5-6 and its variations
In order to draw non-intersecting chords, you have draw triangles in the circle with all the triangles sharing one vertex.
Ex: If n = 5, then there are 10 points on the circle.
Start from P0, and draw chords to all other points, P1 - P9.
This will give you 9 lines or (2 * n - 1).
Then join all the points from P1 - P9 to their neighbors. This will give you 7 lines or (2 * (n - 1)).
Adding the two, you will get (4 * n - 3).
#include<iostream>
using namespace std;
int motzkin(int n)
{
if(n%2==1)
return 0;
else if(n==2) return 1;
else
{
int sum=0;
for(int i=2;i<=n;i++)
sum+=motzkin(i-2)+motzkin(n-i);
return sum;
}
}
main()
{
int n;
cout<<"Enter the number of points(n) : ";
cin>>n;
cout<<motzkin(2*n)<<endl;
}
Here is a shot at a different way to see this problem. If you connect any two points, the circle is partitioned into two arcs, each arc has a certain number of points. For the remaining points, you could only connect those that are on the same arc, otherwise, lines will intersect. Take ten points {1,2, …, 10} for an example. For point 1, you could connect it to 9 other points. However, only 5 of them are valid, i.e., points 2, 4, 6, 8, , and 10. If you connect point 1 to 3, then, you are left with two groups of odd number of points, {2} and {4,5,6,7,8, 9,10}, which are invalid. Let f(n) denote the number of ways to draw n non intersecting chords. For n = 10:
f(10) = f(0)*f(8)+f(2)*f(6)+f(4)*f(4)+f(6)*f(2)+f(8)*f(0)
From here, we could derive a recurrence relationship as the one by daidongLY (adding f(0) = 1 as a base case). I included daidongLY's code as follows with minor modifications.
int Cal(int n){
if (n % 2 == 1) return 0;
if (n == 0) return 1;
if (n==2) return 1;
int sum = 0;
for (int i = 0; i < n; i = i+2)
{
sum += Cal(i) * Cal(n-i-2);
}
return sum;
}
Here is my DP code
int countChords(int n)
{
if (n < 0 || n % 2 != 0)
return 0;
int len = n / 2 + 1;
int ways[len];
ways[0] = ways[1] = 1;
for (int i = 2; i < len; ++i)
{
int w = 0;
int cur_len = i*2;
for (int j = 0; j < cur_len; j = j + 2)
w += ways[j/2] * ways[(cur_len-2-j)/2];
ways[i] = w;
}
return ways[len-1];
}
Tested both code and they output the same results.
This is a basic fibonacci sequence, you have 4 different solutions possible... you can use recursion, iterative, golden ratio, or matrix method.
here's my iterative solution:
int current = 1;
int previous = 0;
int total;
for (int i = 2; i <= N; i+=2) {
total = previous + current;
previous = current;
current = total;
}
return current;
even for n=2,4 etc
this solution is wrong.
it gives current=3 when n=6 which is wrong because for n=6, it should give 5. solution is catalon number.
for 2 pts: 1
for 4 pts: 2(clockwise and anti)
for 6 pts: 2+1+1(including diagonals)
for 8 pts: 2+4+4+4
for 10 pts:2+12+12+12+12....and so on
for 2 pts: 1
for 4 pts: 2(clockwise and anti)
for 6 pts: 2+1+1(including diagonals)
for 8 pts: 2+4+4+4
for 10 pts:2+12+12+12+12....and so on
@All
there should be exactly N chords and all are non intersecting
if you take diagonal points they will intersect each other
These are the two cases besides the clock and anti clock:
(considered diagonal above)
....@@@@
..@......./.../..@
@......../.../..../.@
@......./.../.../..@
..@..../.../.../..@
.....@@@@
....@@@@
..@...\....\.....@
@..\...\....\.......@
@...\...\....\.....@
..@..\...\....\...@
.....@@@@
Ans: 2n-3
justification :
we have n points so between every adjacent points we can draw a chord (n chords).
now select any one point form n points nc1 and we can draw n-1 chords to other n-1 points but the two nodes adjacent to that point are already counted so total chords = n-3(n-1 - 2)
total number of chords = n + n-3 = 2n - 3
Ans: 2n-3
justification :
we have n points so between every adjacent points we can draw a chord (n chords).
now select any one point form n points nc1 and we can draw n-1 chords to other n-1 points but the two nodes adjacent to that point are already counted so total chords = n-3(n-1 - 2)
total number of chords = n + n-3 = 2n - 3
It's a recursion problem, but using a table to store the value will make it more efficiently
int dp[100]={0};
int chord(int p)
{
if (p%2==1) return 0; //cant draw chord using all points in this case
else if (p==0) return 1; //return "1", it's still a possible case
else if (p==2) return 1;
else if (dp[p]!=0) return dp[p];
int sum=0;
for (int i=2;i<=p;++i)
{
sum+=(chord(i-2)*chord(p-i));
}
dp[p]=sum;
return sum;
}
If you have 2N points, divide them with an imaginary line such that N points lie on one side of the line and N on another (say left half and right half)
a) you have N chords joining N points on left half and right half
b) you have N - 1 cords joining points on left half
c) you have N - 1 cords joining points on right half
d) you have N - 1 cords joining one point on left half and one point on right half that is immediately below the chord you drew in a)
So answer is a) + b) + c) + d)
N + N - 1 + N - 1 + N - 1 = 4N - 3
Problem statement implies that every point is used in the solution.
remember[n+1] = {0}; // solutions for smaller circles with 2n points
remember[1] = 1;
remember[2] = 2;
int HowMany(int n) {
if (remember[n]) return remember[n]; // efficiency
int i = 0; // i is the distance between the endpoints of our chord
// now test every chord and subdivide
for (i=1; i<2n-1; i+=2) { // cannot connect an even number of points away
inside = i-1; // number of points on one side of the chord
outside = 2n -2 -inside;
count += HowMany (inside/2) + HowMany(outside/2);
}
return count;
}
f(N = 1) => 2 node => 1 line
f(N = 2) => 4 node => 2 line
f(N = 3) => 6 node => 5 line
f(N = 4) => 8 node => 13 line
....
f(N = n) => 2n node => (3 * f(n - 1) - f(n - 2)) line
proof:
consider following tree states:
1- node(i) is connected to node(i + 1) => remaining nodes will form a circle with (2n - 2) => f(n - 1)
2- node(i) is connected to node(i - 1) => same as (1). => f(n - 1). there is no intersection between (1) and (2) as.
3- node(i+1) is connected to node(i + 2) => same as (1) => f(n -1) => this state has no intersection with (1), but has intersection with (3) => some duplicate states in which both of the following are true
3-1 node(i) is connected to node(i - 1)
3- 2 node(i+1) is connected to node(i + 2)
=> the remaining nodes will form a circle with (2n - 4) node => number of duplicates = f(n - 2)
Total = f(n-1) + f(n-1) + f(n-1) - f(n-2) = 3f(n - 1) - f(n - 2)
@All Please note that chords are non intersecting ....
for Eg :
for n=2 ans is 1
for n=4 ans is 2
for n=6 ans is 3
for n=8 ans is 5
for n=10 ans is 8
i think u got the pattern :)
and so on.... so finally i thought it's very simple
int T(int n)
{
if (n==2)
return 1;
if(n==4)
return 2;
else
return ( T(n-2) + T(n-4));
}
I believe it's not a exact Motzkin number. Can get the value through recursion.
- daidongLY February 20, 2012