CareerCup

I think that the easiest thing to do is to go over each vertex( point i ) and draw the line with point i+2(mod n) until going overall the points. By this, we draw the star whether it is odd or even.
For example, the 5 pointed star can be drawn as follows:
- draw a line between point 0 and 2
- draw a line between point 1 and 3
- draw a line between point 2 and 4
- draw a line between point 3 and 0
- draw a line between point 4 and 1

and the 6 pointed star:

- draw a line between point 0 and 2
- draw a line between point 1 and 3
- draw a line between point 2 and 4
- draw a line between point 3 and 5
- draw a line between point 4 and 0
- draw a line between point 5 and 1

This is a very easy problem. Just start from the first point in the array...now move 2 points counter clockwise (i-2)mod N. As you keep moving, join points if they are not visited. If after moving you reach a visited point (you completed a cycle), so you can just move to the next element in the array.

For(n = 5, 7, 9 etc) you never end up moving to a visited point until the whole star is drawn.

For (n=6,8,10 etc.) you do come to a point which is already visited and then you have to move to the next element in the array and repeat.

Actually it is a simple problem only if the star has odd number of points. Here is the code.

//not sure how it works for an even number pointed star
if(n/2 == 0)
return;

for(i = 0; i < n; i++)
{
int j = (i + 2 > n - 1) ? (i + 2) - n : i + 2;
drawLine(i, j);
}

For an even number of points, I think you'll want to do the odd drawing and then repeat starting at 1 instead of at 0.

"SomeCoder" your idea is not clear to me. Only with an odd number of points it is possible all the points will have two edges.

that's stupid. When you have an even number of points, just do the same thing, but jump over two points at a time...

Try n=5.

0%5=0
2%5=2
4%5=4
6%5=1
8%5=3
10%5=0.

Try n=6.
0%6=0.
2%6=2
4%6=4
6%6=0.
1 triangle. Do same, starting at 1, for other triangle. Star of David, my favorite star :o)

Try n=7.
0%7=0
2%7=2
4%7=4
6%7=6
8%7=1
10%7=3
12%7=5
14%7=0. Print.

There seems to be a pattern. When is odd, do modulo iteratively. When n is even, you draw separate triangles. Since the case for odd is easy to do, let's exam even more closely and see what's up...

We know that a triangle has 3 points. Two triangles have a total of 2*3 pts. Three triangles have a total of 3*3 points. Hence if n%3==0, then we draw separate triangles. 8 is even but 8%3 != 0 so let's try n=8...

0%8=0
2%8=2
4%8=4
6%8=6
8%8=0. quadrilateral!

1%8=1
3%8=3
5%8=5
7%8=7
9%8=1. quadrilateral!

Again it seems that odds are easy to draw, but evens are trickier. Based on this evidence, if n%3==0, you can draw separate triangles iteratively. You know how many triangles to draw by n/3. Each triangle's vertex is 1 apart from the prev triangle. Continuing, if n%2==0 and n%3!=0, do the same as for n%3==0 except that you will be different shapes.

assume n >= 3.
n = 4, 6 are special cases.

<pre>

int k = 2;
if( n % 2 == 0){
k = 3;
}

for(i = 0 ; i <= n * k; i += k){
drawLine(i % n , (i + k) % n );
}

</pre>

I think we are forgetting what a star is. look at the five pointed star for an example. You are basically drawing a line from the start to an adjacent point accross from the starting point in some sort of pattern. The basic pattern is (number_points - 1)/2. Now lets look at special cases (6, 10, 14, 18, 22, etc). Each of these special cases would require to stars. The reason is that the number of points is even and the number of points skipped(based on previous equation) are both even. So in these cases we would need to draw two stars. So my algorithm would be to store my number of points to skip: (number_points -1)/2. store my starting point: head_of_star, initialize both points (int indexOne to head_of_star (starting point), int indexTwo ((number_points - 1)/2) ). I then draw the line, check to see if indexTwo is equal to head_of_star, if not set indexOne to indexTwo and indexTwo to indexOne plus my jump value and draw another line.

Once this is done, I check to see if my number of points and my jump value are both even. If so I add one to my head_of_star, reset my indexes and draw the second star. Problem solved and you actually have something that will still look like a star no matter how many points.

code:
given: intNumPoints

int intStartHead = 0;
int intJumpValue = (intNumPoints - 1) /2;
int indexOne = intStartHead;
int indexTwo = indexOne + intJumpValue;

while(indexTwo != intStartHead)
{
drawLine(indexOne, indexTwo);
indexOne = indexTwo;
indexTwo = indexOne + intJumpValue;
}
if (intNumPoints % 2 == 0 && intJumpValue % 2 == 0)
{
intStartHead++;
int indexOne = intStartHead;
int indexTwo = indexOne + intJumpValue;

while(indexTwo != intStartHead)
{
drawLine(indexOne, indexTwo);
indexOne = indexTwo;
indexTwo = indexOne + intJumpValue;
}
}

I believe this should work.

I think we are forgetting what a star is. look at the five pointed star for an example. You are basically drawing a line from the start to an adjacent point accross from the starting point in some sort of pattern. The basic pattern is (number_points - 1)/2. Now lets look at special cases (6, 10, 14, 18, 22, etc). Each of these special cases would require to stars. The reason is that the number of points is even and the number of points skipped(based on previous equation) are both even. So in these cases we would need to draw two stars. So my algorithm would be to store my number of points to skip: (number_points -1)/2. store my starting point: head_of_star, initialize both points (int indexOne to head_of_star (starting point), int indexTwo ((number_points - 1)/2) ). I then draw the line, check to see if indexTwo is equal to head_of_star, if not set indexOne to indexTwo and indexTwo to indexOne plus my jump value and draw another line.

Once this is done, I check to see if my number of points and my jump value are both even. If so I add one to my head_of_star, reset my indexes and draw the second star. Problem solved and you actually have something that will still look like a star no matter how many points.

code:
given: intNumPoints

int intStartHead = 0;
int intJumpValue = (intNumPoints - 1) /2;
int indexOne = intStartHead;
int indexTwo = indexOne + intJumpValue;

while(indexTwo != intStartHead)
{
drawLine(indexOne, indexTwo);
indexOne = indexTwo;
indexTwo = indexOne + intJumpValue;
}
if (intNumPoints % 2 == 0 && intJumpValue % 2 == 0)
{
intStartHead++;
int indexOne = intStartHead;
int indexTwo = indexOne + intJumpValue;

while(indexTwo != intStartHead)
{
drawLine(indexOne, indexTwo);
indexOne = indexTwo;
indexTwo = indexOne + intJumpValue;
}
}

I believe this should work.

Sorry, I do have a small edit to that.

Whenever you are setting your second index it should look like this:

indexTwo = (indexOne + intJumpValue) % intNumPoints;

It's late and I forgot.

the above answer seems to be correct and most likely to be the answer.
(i+2)(mod n)

private void DrawStar(int n)
{
int i = 0;
int[] Points = new int[n];
for(i = 0 ; i <= n-1 ; i ++)
{
if(Points[i] != 2)
{
Console.WriteLine("Draw Line From" + i.ToString() + " To " + ( (i+2) % n));
Points[i]++;
}
}
}

As i understand it:
if we have 2 vertexes than the lines will be:
0 to 1
if we have 4 vertexes than the lines will be:
0 to 2
1 to 3
if we have 6 vertexes than the lines will be:
0 to 3
1 to 4
2 to 5

Meaning, the rule might be (for even n)
0 to n/2
1 to n/2+1
2 to n/2+2
etc.

in case of odd number of edges we will leave the last one unconnected.
Anyway, its a case to deal alone (need to be clarify in the interview). Line takes 2 edges, therefore in case of odd number of edges, you will always get one that is unconnected

the code in that case is:

oddFlg = FALSE;
if ((N%2)==1) than
{
oddFlg = TRUE;
N--;
}

int count = (N-1)/2;
int destIndx;
for (int =0; i<count; i++)
{
destIndx=count+1;
drawLine(index[count],index[destIndx]);
}
if oddFlg connect it as instructed (if any)

Hamza's solution is the most elegant.

Although you don't know what rule a child follows when drawing a five or six point start. Because it is both 1) connecting every 2 vertices and 2) connecting a vertex with j = floor( (n-1) /2 ) away from it. For larger n, any value between 2 and j could possibly work as the distance bewteen two vertices to connect. There is no standard way to form a star. For example, I could form a 8 vertice star by connectiong 0 and 3, 1 and 4 and so on.

if(n<5)
return;
for(i=1;i<=n;i++)
drawLine(i, (i+2)%n);
return;

Hamza's Algo:

void drawStar( int n ){
int index = 0;
while( index < n )
drawline( index, (index+2)%n )
}

Other Algo:

void drawStar( int n ){
int index = 0;
while( index < n ){
for(int i=0; i<n-2; i++)
drawline( index, (index+i+2)%n]
}
}

void DrawStar(int starPt)
{
if (starPt > 5 )
{
throw new invalidOperationException("Need minimum of 5 pts);
}

int placeHolder = 0;

if(!((startPt % 2) == 0))
{
for(int i = 0; i < starPt; i++)
{
drawLine(placeHolder, (placeholder + 2));
placeHolder += 2;
}
}

if((startPt % 2) == 0)
{
placeHolder = 0;
for(int i = 0; i < starPt/2; i++)
{
drawLine(placeHolder, (placeholder + 2));
placeHolder += 2;
}

placeHolder = 1;
for(int i = 0; i < starPt/2; i++)
{
drawLine(placeHolder, (placeholder + 2));
placeHolder += 2;
}
}

}

(i+2)%n

The increment to add to i is a function of n:

int increment = n / 2 + (n + 1) % 2;
for(int i = 0; i < n; i++)
{
drawline(points[i], point[(i + increment) % n];
}

Here's my solution. The goal here is to draw each line without redrawing it. Imagine a three pointed star. Imagine further that all lines from point 0 have been drawn to all other points i.e. (0,1) and (0,2) have been drawn. We are drawing lines from point 1. Therefore, we only need to draw lines to points which are greater than current. Once we hit point 2, we have no points greater so we know all lines have been drawn. Fortunately we don't have to worry about the x,y location of the points. :)

void DrawStar(int howManyPoints)
{
if (howManyPoints < 3)
{
// error, exception, return, whatever
}
for (int i = 0; i < howManyPoints; i++) // outer loop. For each point...
{
for (int j=i+1; j < howManyPoints; j++)
{ // inner loop, for each point > currentPoint, draw line
DrawLine(i, j);
}
}
}

<2 minutes later>

Shoot my answer is wrong, i just realized you don't want to draw lines to any neighboring point.

lets try this instead :)

void DrawStar(int howManyPoints)
{
if (howManyPoints < 5)
{
// error, exception, return, whatever
}
for (int i = 0; i < howManyPoints; i++) // outer loop. For each point...
{
for (int j=i+2; j < howManyPoints; j++)
{ // inner loop, for each point > currentPoint, draw line
DrawLine(i, j);
}
}
}

How can you guys assume that the points are in a clockwise or counter-clockwise order?