Problem from top coder (TCO 14 Round 1A DIV 1) and my solution

Problem:

Problem Statement

Manao is building a new house. He already purchased a rectangular area where he will place the house. The basement of the house should be built on a level ground, so Manao will have to level the entire area. The area is leveled if the difference between the heights of its lowest and highest square meter is at most 1. Manao wants to measure the effort he needs to put into ground leveling.You are given a String[] area. Each character in area denotes the height at the corresponding square meter of Manao’s area. Using 1 unit of effort, Manao can change the height of any square meter on his area by 1 up or down. Return the minimum total effort he needs to put to obtain a leveled area.

Definition

Class: HouseBuilding
Method: getMinimum
Parameters: String[]
Returns: int
Method signature: int getMinimum(String[] area)
(be sure your method is public)

My Code:

public class HouseBuilding
{
public int getMinimum(String[] area)
{
int min = 11;
int max = -1;

int[] c = new int[10];

for(int i = 0; i < area.length; i++)
{
for(int j = 0; j < area[i].length();j++)
{
int val = Integer.parseInt(“” + area[i].charAt(j));
c[val]++;
if(val > max)
max = val;
if(val < min)
min = val;
}
}

if(max – min <= 1)
return 0;

int result = Integer.MAX_VALUE;
for(int i = 0; i < 9; i++)
{
int sum = 0;
for(int j = 0; j < 10; j++)
{
if( j <= i)
{
sum += (i – j) * c[j];
}
else
sum += (j – i -1) * c[j];
}

if(sum < result)
result = sum;
}

for(int i = 0; i < 9; i++)
{
int sum = 0;
for(int j = 0; j < 10; j++)
{
if( j <= i)
{
sum += (i – j) * c[j];
}
else
sum += (j – i) * c[j];
}

if(sum < result)
result = sum;
}

return result;
}
}

One Algorithm Problem and my solution (08/27/2014)

Problem: Given an array of N numbers A[0,…,N-1], output an array M[0, N-1,], so that M[i] is the multiplication of all numbers in A except A[i]. No Division is allowed.

Let’s rephrase this problem: so M[i] = A[0] * A[1] * … * A[i-1] * A[i+1] * A[i+2]*…* A[N-1]

so it consists two parts: one is the multiplication below A[i]:  A[0] * A[1] * … A[i-1]; one is above A[i] : A[i+1] * A[i+2] * … * A[N-1].

Approach 1:

If we know any multiplication from index p to index q, then the problem can be solved by multiplying two parts: index from 0 … i-1 and i+1… N-1.

Let’s assume the input is int A[N], output will be Output[N]

First, create a temp array temp[N][N] and init each value with 1.

Second, calculate the auxiliary array values.

for(int i = 0; i < N-1; i++)

{

temp[i][i] = A[i];

for(int j = i+1; j < N-1; j++)

{

temp[i][j] = temp[i][j-1] * A[j];

}

}

 

Output[0] = temp[1][N-1];

for(int i = 1; i < N-1; i++)

Output[i] = temp[0][i-1]* temp[i+1][N-1];

The space complexity here is O(N^2).

 

Approach 2:

A close look at the above approach would discover that, it is not necessary to create the entire temp[N][N]. Actually if only we can create temp[0][i-1] and temp[i+1][N-1], then we are good to go. so here it is:

int tempBelow[N], tempAbove[N];

init tempBelow[0…N-1] with value 1;

int p = 1;

for(int i = 0; i < N-1; i++)

{

tempBelow[i] = p;

p *= A[i];

}

init tempAbove[0…N-1] with value 1;

p = 1;

for(int i = N-1; i >= 0; i–)

{

tempAbove[i] = p;

p *= A[i];

}

for(int i = 0; i < N; i++)

{

Output[i] = tempBelow[i] * tempAbove[i];

}

The space complexity is: O(N);

 

Approach 3:

In fact, we can also move on without the auxiliary array tempAbove and tempBelow. We can carry on the accumulated multiplications carefully.

 

init Output[0…N-1] with value 1;

int p = 1;

for(int i = 0; i < N; i++)

{

Output[i] = p;

p *= A[i]

}

p = 1;

for(int i = N-1; i >= 0; i–)

{

Output[i] *= p;

p *= A[i];

}

The space complexity is now constant O(1).