## Archive for July, 2012

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime, as only 1 and 5 divide it.

For computing prime numbers we will use Sieve of Eratosthenes algorithm. The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so).

# Algorithm

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime

``` public static void PrimeNumber(int n)
{
int[] numbers = new int[n + 1];
if (n < 0)
{
Console.WriteLine("invalid value");
return;
}
if (n < 3)
{
Console.WriteLine("Prime number is : 2");
return;

}

int p = 0;
for (int i = 2; i <= n; i++)
{
if (numbers[i] == 0)
{
p = i;
for (int j = 2; p * j <= n; j++)
{
numbers[p * j] = 1;
}
}
}

for (int i = 2; i <= n; i++)
{
if (numbers[i] == 0) Console.Write(i + " , ");
}

}```

For reversing the word in a string I used following algorithm

1. Traverse the string and push the characters in stack, until we get space
2. When space is encountered, pop the element from stack and enqueue in queue
3. enqueue the spaces in queue
4. once the traverse is complete add the last word in queue

Stack is used to reverse the characters and queue is used to maintain the order of characters

```   public static void ReverseWordOfString(string s)
{
if (string.IsNullOrEmpty(s))
{
Console.WriteLine("String is empty");
return;
}

Stack<char> charStack = new Stack<char>();
var charArray = s.ToCharArray();
int length = charArray.Length;
Queue<char> result = new Queue<char>();
Console.WriteLine("input string : {0}", s);
for (int i = 0; i < length; i++)
{
if (charArray[i] != ' ')
{
charStack.Push(charArray[i]);
}
else
{
while (charStack.Count > 0)
{
result.Enqueue(charStack.Pop());
}
result.Enqueue(' ');
}
}
while (charStack.Count > 0)
{
result.Enqueue(charStack.Pop());

}

Console.Write("String After reversing the words : ");
Console.Write(result.ToArray());
Console.WriteLine();

}```

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. This is most useful on data that contains many such runs: for example, simple graphic images such as icons, line drawings, and animations. It is not useful with files that don’t have many runs as it could greatly increase the file size.

```  /// <summary>
/// Given AAABBGFF should get an output 3{A} 2{B}1{G}2{F}
/// http://en.wikipedia.org/wiki/Run-length_encoding
/// </summary>
/// <param name="input"></param>
public static void RIL(string input)
{
Console.Write(input + " : " );
StringBuilder output = new StringBuilder();
int charCount = 0;
var inputChars = input.ToCharArray();
char currentChar, nextChar;
currentChar = nextChar = inputChars[0];

for (int i = 0; i < inputChars.Length; i++)
{
currentChar = inputChars[i];
if (i + 1 < inputChars.Length)
{

nextChar = inputChars[i + 1];
}
if (currentChar  != nextChar )
{

output.Append(charCount + 1);
output.Append("{");
output.Append(currentChar);
output.Append("}");
charCount = 0;

}
else {
charCount++;
}
}
output.Append(charCount );
output.Append("{");
output.Append(currentChar);
output.Append("}");

Console.Write(output.ToString());
Console.WriteLine();

}```

Test Cases

1. AAABBGFF : 3{A}2{B}1{G}2{F}
2. WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWW WWWWWWBWWWWWWWWWWWWWW : 12{W}1{B}12{W}3{B}24{W}1{B}14{W}
3. AAABBGGGGGGGGFFXXXXXXTTTTTyyyyyyvvvvv : 3{A}2{B}8{G}2{F}6{X}5{T}6{y}5{v}
4. AAAABBCCCCCCCBBCCCCDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD :

4{A}2{B}7{C}2{B}4{C}38{D}

A method to solve such problems is to consider the rate of change of the angle in degrees per minute. The hour hand of a normal 12-hour analogue clock turns 360° in 12 hours (720 minutes) or 0.5° per minute. The minute hand rotates through 360° in 60 minutes or 6° per minute.

# ΘM= 6M

M= Minute and H = Hour

Angle between Hour and minute handle

# ΘH – ΘM

Co-ordinate of triangle: A(x1, y1), B(x2, y2), C(x3, y3) and Point P (x, y).

## Approach:

1. Calculate the area triangle that is are of triangle ABC. Area A
2. Calculate the area of PAB. Area A1
3. Calculate the area of PBC. Area A2
4. Calculate the area PCA. Area A3
5. If Point P lies outside the triangle than A1+A2+A3 >A.

Area of Triangle: [x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2)]/2

In above approach, we will have precision problem because we are dividing the result by 2. So to handle this issue, by taking off 2 times of triangle are.

sub list of a sorted (ascending order)link list is reversed. correct it.

Input
1->2->3->4->8->7->6->5->9->10->11
Output
1->2->3->4->5->6->7->8->9->10->11

To solve this problem :

1. Find the pointer, from dis order starts say first
2. Find the pointer where dis order ends say last node
3. Setting next of last node to null
4. Reverse the linked list from first to last
6. join the linked list with remaining list

Node Class : Used for Creating Link List

```public class Node<T>
{
private T nodeValue;
private Node<T> nextNode;

public Node()
{
this.nodeValue = default(T);
this.nextNode = null;
}

public Node(T nodeValue)
{
this.nodeValue = nodeValue;
this.nextNode = null;
}

/// <summary>
/// Value of node
/// </summary>
public T NodeValue
{
get { return nodeValue; }
set { this.nodeValue = value; }
}

/// <summary>
/// The node this node links to
/// </summary>
public Node<T> NextNode
{
get { return this.nextNode; }
set { this.nextNode = value; }
}
}```
```    /// <summary>
/// 1--->2--->3--->4--->9--->8-->7--->6--->5--->10--->11--->NULL
/// </summary>
{

{
Console.WriteLine("Empty List");
return;
}

Node<int> first = null;
Node<int> last = null;
Node<int> mark1 = null;

while (current != null && current.NodeValue < current.NextNode.NodeValue)
{
mark1 = current;
current = current.NextNode;
}

first = current; //Pointer to node, LL Disorder starts

while (current != null && current.NodeValue > current.NextNode.NodeValue)
current = current.NextNode;

last = current.NextNode; //Pointer to node, LL Disorder Ends

current.NextNode = null; // Setting next of last node to null

Reverse(ref first);//reverse the sub list that dis order starts to disorder ends

while (first.NextNode != null)
{
first = first.NextNode;
}

first.NextNode = last; // join the merged link list with sorted linklist
Console.WriteLine();
Console.WriteLine("Output");

Console.WriteLine();

}

public static void Reverse(ref Node<int> head)
{

Node<int> first;
Node<int> rest;
rest = first.NextNode;
if (rest == null) return;
Reverse(ref rest);
first.NextNode.NextNode = first;
first.NextNode = null;

}
{
{
}

}```

## Main Program

```      Node<int> a = new Node<int>(1);
Node<int> a1 = new Node<int>(2);
Node<int> a2 = new Node<int>(3);
Node<int> a3 = new Node<int>(4);
Node<int> a4 = new Node<int>(8);
Node<int> a5 = new Node<int>(7);
Node<int> a6 = new Node<int>(6);
Node<int> a7 = new Node<int>(5);
Node<int> a8 = new Node<int>(9);
Node<int> a9 = new Node<int>(10);
Node<int> a10 = new Node<int>(11);

a.NextNode = a1;
a1.NextNode = a2;

a2.NextNode = a3;

a3.NextNode = a4;

a4.NextNode = a5;

a5.NextNode = a6;

a6.NextNode = a7;

a7.NextNode = a8;

a8.NextNode = a9;

a9.NextNode = a10;

a10.NextNode = null;
Console.WriteLine("Input");
Microsoft.PrintList(a);
Microsoft.correctList(a);```

In computational complexity theory, 3SUM is the following computational problem conjectured to require roughly quadratic time:

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

It is possible to solve the algorithm in O(n2) time using simple algorithms, and matching lower bounds are known for some specialized models of computation.

The program mentioned below works only with sorted List

``` public static void SortedList3SumProblem(int[] inputArray)
{
int a, b, c;
int length = inputArray.Length;
for (int i = 0; i < length - 3; i++)
{

a = inputArray[i];
int k = i + 1;
int l = length  - 1;

while (k < l)
{
b = inputArray[k];
c = inputArray[l];
if (a + b + c == 0)
{
Console.WriteLine(a + "," + b + "," + c); ;
break;
}
else if (a + b + c > 0)
l = l - 1;
else
k = k + 1;
}

}
}```

# Input

0, -25, -10, -7, -3, 2, 4, 8, 10

# Output

Input Array

0;-25;-10;-7;-3;2;4;8;10

——————————–

0,-10,10

-10,2,8

-7,-3,10

``` public static void RepeatedEvenTimes(int[] inputArray)
{
Dictionary<int, int> numbers = new Dictionary<int, int>();
int length = inputArray.Length;
int num = -1;
for (int i = 0; i < length; i++)
{
if (numbers.Keys.Contains(inputArray[i]))
{
numbers[inputArray[i]] = numbers[inputArray[i]] + 1;
}
else
{

}
}

Console.Write("input Array ");
Console.WriteLine(string.Join(",", inputArray));

foreach (var item in numbers)
{
if (item.Value % 2 == 0)
{
num = item.Key;
Console.WriteLine("{0} Repeated {1} times ", item.Key, item.Value);
break;
}

}

if (num == -1)
{
Console.WriteLine("No number Repeated even number of times");
}

Console.WriteLine("-----------------------------------------------");
}```
` `

input Array 3,3,3,5,5,5,2,2,2
No number Repeated even number of times
———————————————–
input Array 100,1,1,3,5,3,3
1 Repeated 2 times
———————————————–
input Array 2,2,2,2,2
No number Repeated even number of times
———————————————–

Node Class : For creating LinkList

```public class Node<T>
{
private T nodeValue;
private Node<T> nextNode;

public Node()
{
this.nodeValue = default(T);
this.nextNode = null;
}

public Node(T nodeValue)
{
this.nodeValue = nodeValue;
this.nextNode = null;
}

/// <summary>
/// Value of node
/// </summary>
public T NodeValue
{
get { return nodeValue; }
set { this.nodeValue = value; }
}

/// <summary>
/// The node this node links to
/// </summary>
public Node<T> NextNode
{
get { return this.nextNode; }
set { this.nextNode = value; }
}
}```

```class LinkList
{
public static void Test()
{
Node<int> a1 = new Node<int>();
a1.NodeValue = 10;

Node<int> a2 = new Node<int>();
a2.NodeValue = 11;

Node<int> a5 = new Node<int>();
a5.NodeValue = 12;

Node<int> a3 = new Node<int>();
a3.NodeValue = 13;

Node<int> a4 = new Node<int>();
a4.NodeValue = 14;
a1.NextNode = a2;
a2.NextNode = a3;
a3.NextNode = a4;
a4.NextNode = a5;
a5.NextNode = null;

Console.WriteLine("----------------------------------------------------");
Console.WriteLine("Reverse  List");
Reverse(ref a1);
Console.WriteLine("----------------------------------------------------");

}
public static void Reverse(ref Node<int> head)
{

Node<int> first;
Node<int> rest;
rest = first.NextNode;
if (rest == null) return;
Reverse(ref rest);
first.NextNode.NextNode = first;
first.NextNode = null;

}
{
while (temp != null)
{
Console.Write(temp.NodeValue + "-->"
);
temp = temp.NextNode;

}
Console.WriteLine();

}

}```

Write a Program to Return Excel Sheet Column Header Name if Input is a Number

input

-11
1
26
52
28
702
703

output

input number -11 is invalid
input number 1 , output alphabet A
input number 26 , output alphabet Z
input number 52 , output alphabet AZ
input number 28 , output alphabet AB
input number 702 , output alphabet ZZ
input number 703 , output alphabet AAA

``` public static string ConvertToAlphabet(int number)
{
int temp = number;
char[] alphabets = new char[] { 'A', 'B', 'C', 'D', 'E',
'F', 'G', 'H', 'I', 'J',
'K', 'L', 'M', 'N', 'O',
'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y',
'Z' };
string Alphabet = string.Empty;
int Index = 0;

if (number <= 0)
{

Console.WriteLine("input number {0} is invalid", temp);

return string.Empty;
}

if (number < 27)
{

Console.WriteLine("input number {0} , output alphabet {1}"
, temp, alphabets[number - 1]);

return alphabets[number - 1].ToString();
}
while (number > 0)
{
Index = number % 26;
number = number / 26; ;

if (Index == 0)
{
Index = 26;
number = number - 1;
}
Alphabet = alphabets[Index - 1] + Alphabet;

}

Console.WriteLine("input number {0} , output alphabet {1}"
, temp, Alphabet);
return Alphabet;
}```