VolVo
BAN USERIdea is simple start filling from end of array B. Take two pointers one pointing A's last element and other pointing B's last element(not including extra space left in B).
Now compare them and put which is bigger at the end of B. Now forward the pointer which ever the number was larger.Compare again and Keep doing. Finally both array will get merged.
No extra space needed and complexity will be O(B.length).
Its simple problem if you can you know how to find whether a list have loop or not.
Algorithm :- Take two pointers p1 and p2. Start both from head. Loop until p1 and p2 meet again. But p1 will incre one step i.e. p1 = p1-> next and p2 will two steps i.e. p2= p2->next->next.Once they meet. Do following step.
Now make p1=head and start increment one step by one for both p1 and p2. When they meet again will be the starting point of the cycle.
Simple start from max denomination coin. And keep subtracting from the sum until sum becomes zero.
C# code for this problem is : Program returning each coin denomination, and count of coin needed to form the sum.
static int[,] MinCoin(int[] coin_den, int sum)
{
int[,] count_each_coin = new int[coin_den.Length, 2];
for (int i = 0; i < coin_den.Length; i++)
{
count_each_coin[i, 0] = coin_den[i];
}
for (int i = 0; i < coin_den.Length; i++)
{
count_each_coin[i, 1] = 0;
}
for (int i = coin_den.Length-1; i >= 0; i--)
{
while (sum - coin_den[i] >= 0)
{
count_each_coin[i, 1] += 1;
sum -= coin_den[i];
}
}
return count_each_coin;
}
This code is working correct. Code is in C#. To verify just run it.
namespace MaxSumKxKMatrixInNxNMatrix
{
class Program
{
static void Main(string[] args)
{
int[,] abc= new int[5,6]{{6,4,7,2,-9,12} , {8, -2,5,3,1,9}, {9,3,1,8,5, -2}, {-2,4,6,8,10,12} , {1,3,5,7,-9,11} };
int[] ans = MaxKxKMatrix(abc, 5, 6, 3);
foreach (int item in ans)
{
Console.WriteLine(item);
}
Console.ReadLine();
}
static int[] MaxKxKMatrix(int[,] matrix, int n, int m, int k)
{
int[] max_mat_index = new int[3];
int max_sum = 0;
for (int i = 0; i <= n-k; i++)
{
for (int x = 0; x <= m - k; x++)
{
int row=0, col=0;
int this_matrix_sum = 0;
for (int j = i; j <= i+ k-1; j++)
{
for (int y = x; y <= x+k-1; y++)
{
this_matrix_sum = this_matrix_sum + matrix[j, y];
col = y;
}
row = j;
}
if (this_matrix_sum > max_sum)
{
max_sum = this_matrix_sum;
max_mat_index[0] = row;
max_mat_index[1] = col;
max_mat_index[2] = this_matrix_sum;
}
}
}
max_mat_index[0] = max_mat_index[0] - 2;
max_mat_index[1] = max_mat_index[1] - 2;
return max_mat_index;
}
}
}
Its simple !!!
- VolVo September 13, 2012Algo :- Keep two pointers one pointing to head and other at tail of Linked list. Now traverse the list from head if you encounter any node with value 0 then remove from that position and add at the head and updated the head ptr to the newly added node.
If you encounter 2 then remove that node and add that node at the tail of linked list and update the tail ptr to the new node added.