Below solution divides the problem into sub problems of size y/2 and call the sub problems recursively

public static UInt64 Power(UInt64 x, UInt64 n)
{
if (n == 0)
return 1;
else if (n % 2 == 0)
return Power(x, n / 2) * Power(x, n / 2);
else
return x * Power(x, n / 2) * Power(x, n / 2);

}

Test Case

UInt64 x = 0;
UInt64 n = 0;
x = 2; n = 2;
Console.WriteLine(string.Format("{0}^{1} ={2}", x, n, Power(x, n)));
x = 2; n = 3;
Console.WriteLine(string.Format("{0}^{1} ={2}", x, n, Power(x, n)));
x = 10; n = 2;
Console.WriteLine(string.Format("{0}^{1} ={2}", x, n, Power(x, n)));
x = 12; n = 18;
Console.WriteLine(string.Format("{0}^{1} ={2}", x, n, Power(x, n)));

Output

2^2 =4
2^3 =8
10^2 =100
12^18 =8176589207175692288

A palindrome is a word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction.

public static bool IsPalindrome(this string input)
{
bool result = true;
input = input.Trim();
try
{

if (string.IsNullOrEmpty(input))
{
return result = false;
}

var inputArray = input.ToCharArray();

if (inputArray.Length == 1)
{
return result = true;
}

int length = inputArray.Length – 1;

for (int i = 0; i <= length / 2; i++)
{
if (inputArray[i] != inputArray[length – i])
{
return result == false;
}
}
}
catch (Exception)
{

result = false;
}
return result;

}
Test Case

string s = "";
Console.WriteLine(string.Format("String {0} IsPalindrome {1}", s, s.IsPalindrome()));
s = "AJAY";
Console.WriteLine(string.Format("String {0} IsPalindrome {1}", s, s.IsPalindrome()));
s = "ABBA";
Console.WriteLine(string.Format("String {0} IsPalindrome {1}", s, s.IsPalindrome()));
s = "ABBa";
Console.WriteLine(string.Format("String {0} IsPalindrome {1}", s, s.IsPalindrome()));
s = "palindrome";
Console.WriteLine(string.Format("String {0} IsPalindrome {1}", s, s.IsPalindrome()));

Output:

String  IsPalindrome False
String AJAY IsPalindrome False
String ABBA IsPalindrome True
String ABBa IsPalindrome False
String palindrome IsPalindrome False

`        public static long ReverseNumber(this long number)`
`        {`
`            long reversedNumber = 0;`
`            bool isNegative = false;`
` `
`            if (number < 0)`
`            {`
`                isNegative = true;`
`            }`
`            if (number < 10 && number >= 0)`
`            {`
`                reversedNumber = number;`
`                return reversedNumber;`
`            }`
` `
`            number = Math.Abs(number);`
` `
`            while (number > 0)`
`            {`
`                reversedNumber = _base * reversedNumber + number % _base;`
`                number = number / _base;`
`            }`
` `
`            if (isNegative)`
`            {`
`                reversedNumber = reversedNumber * -1;`
`            }`
`            return reversedNumber;`
`        }`

Test Case

Number 1234567890 is reversed to 987654321

Number -123456 is reversed to -654321

Number 9 is reversed to 9

Number 545 is reversed to 545

Number 123454321 is reversed to 123454321

Number -123454321 is reversed to -123454321

```        public static long Length(this long number)
{

long length = 0;

if (number < 10 && number >= 0)
{
length = 1;
return length;
}

number = Math.Abs(number);

while (number > 0)
{
length += 1;
number = number / _base;
}

return length;
}```

Test Case

Length of number 123 is  3

Length of number 1234567890 is  10

Length of number -123456 is  6

Length of number 9 is  1

Length of number 545 is  3

Length of number 123454321 is  9

Length of number -123454321 is  9

We have already have post on various tree traversal in recursive way. Today we will cover how we can traverse a tree in iterative way.

Iterative Pre order tree traversal : For this we will be using stack to keep track of the traversed nodes

```        public void iterativePreorder(TreeNode node)
{

bool done = false;
Stack<TreeNode> parentStack = new Stack<TreeNode>();
while (!done)
{
if (node == null && parentStack.Count() == 0)
{
done = true;
return;
}
if (node != null)
{
Console.Write(node.Data + " >");
parentStack.Push(node.Right);
node = node.Left;
}
else
{
node = parentStack.Pop();
}

}
}```

We have already have post on various tree traversal in recursive way. Today we will cover how we can traverse a tree in iterative way.

Iterative in order tree traversal : For this we will be using stack to keep track of the traversed nodes.

```        public void IterativeInorder(TreeNode node)
{
Stack<TreeNode> parentStack = new Stack<TreeNode>();

bool done = false;
while (!done)
{
if (node == null && parentStack.Count() == 0)
{
done = true;
return;
}
if (node != null)
{
parentStack.Push(node);
node = node.Left;
}
else
{
var temp = parentStack.Pop();
Console.Write(temp.Data + " >");
node = temp.Right;
}
}
Console.WriteLine();
}```

public class TreeNode
{
public int Data { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
}

In-Order

public void Inorder(TreeNode node)
{
if (node == null)
{
return;
}
Inorder(node.Left);
Console.Write(node.Data + " >");
Inorder(node.Right);
}

Pre-Order

public void Preorder(TreeNode node)
{
if (node == null)
{
return;
}
Console.Write(node.Data + " >");
Preorder(node.Left);
Preorder(node.Right);
}

Post-Order

public void Postorder(TreeNode node)
{
if (node == null)
{
return;
}

Postorder(node.Left);
Postorder(node.Right);
Console.Write(node.Data + " >");
}

Given Matrix :

`[1   14    25   35] [2   16    28   38] [5   20    28   40] [16  22    38   41]   `

``` ```

`search for 38. `

public static void FindElementinSortedMatrix(int n)
{

int[,] myArray = {
{ 1, 14, 25, 35 },
{ 2, 16, 28, 38 },
{ 5, 20, 28, 40 },
{ 16, 22, 38, 41 }
};

int i = 0;
int j = myArray.GetLength(0) – 1;
while (i < n && j >= 0)
{
if (myArray[i, j] == n)
{
Console.WriteLine(string.Format("element Found at {0},{1}", i, j));
return;
}
else if (myArray[i, j] > n)
{
j = j – 1;
}
else
{
i = i + 1;
}

}
}

`Test Results `

Element 38 Found at 1,3

Input : Number of Rows

Output :

1
22
333
4444
55555

Code

```        public static void PrintNumberPattern4(int rows)
{
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= i; j++)
{
Console.Write(i);
}
Console.WriteLine("");
}
}```

Today we have to write a program for finding the balance index in a given array. This problem can be solved on O( n ) time.

Approach 1

1. Loop Through the array and calculate the sum ,let’s assume sum is equal to arraySum.
2. Now again again iterate over array elements
1. Calculate the sum of element say it is leftsum
2. calculate the difference between arraySum and current Element in arraySum
3. if arraySum is equal to leftSum, then current array index is the balance index.
3. Otherwise return –1, means balance index is not present in the array.

Code:

```        public static int BalanceIndex(int[] input)
{
int arraySum = 0;
int leftSum = 0;
int balnaceIndex = -1;
//Calculate the sum of all elements
for (int i = 0; i < input.Length; i++)
{
arraySum = arraySum + input[i];
}

Console.WriteLine("Sum of Array Elements : " + arraySum);

for (int i = 0; i < input.Length; i++)
{
leftSum = leftSum + input[i];
arraySum = arraySum - input[i];
if (arraySum == leftSum)
{
balnaceIndex = i;
return balnaceIndex;
}
}

if (leftSum != arraySum)
{
return -1;
}
return balnaceIndex;
}```

Test Case

private static void BalanceIndexTest()

{

int[] arr = new int[] { -7, 1, 5, 2, -4, 3, 0,8 };

Console.WriteLine("Balance index for " + string.Join(",", arr) + " is : " + ArrayProblems.BalanceIndex(arr));

int[] arr1 = new int[] { 1, 3, 4, 6, 7, 2, 5, 9, 1, 11, 9, 6, 5, 8, 9, 1 };

Console.WriteLine("Balance index for " + string.Join(",", arr1) + " is : " + ArrayProblems.BalanceIndex(arr1));

int[] arr2 = new int[] { -7, 1, 5, 2, -4, 3, 0};

Console.WriteLine("Balance index for " + string.Join(",", arr2) + " is : " + ArrayProblems.BalanceIndex(arr2));

int[] arr3 = new int[] { -7 };

Console.WriteLine("Balance index for " + string.Join(",", arr3) + " is : " + ArrayProblems.BalanceIndex(arr));

}

Output

Sum of Array Elements : 8

Balance index for -7,1,5,2,-4,3,0,8 is : –1

Sum of Array Elements : 87

Balance index for 1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1 is : –1

Sum of Array Elements : 0

Balance index for -7,1,5,2,-4,3,0 is : 5

Sum of Array Elements : -7

Balance index for -7 is : -1