UVA Problem 12708 – GCD The Largest Solution in Java

UVA Problem 12708 – GCD The Largest Solution Java Solution:

Solving Technique:

I have already solved this problem in c and cpp in this post 12708 – GCD The Largest Solution in c and c++. There I used obvious shortcut technique to solve the problem. Here I will elaborate on a better approach to think this problem. For some reason it was giving wrong answer with buffered string tokenizer with and without BigInteger I couldn’t figure out the problem so, I may later update this with a better java solution.

What is GCD ( Greatest Common Divisor )?

For this problem we are to find the Greatest common divisor for all pairs of number between 1 to N. Where if a number if p. We exclude GCD between (p,p) pair. Because other than the reason it is omitted at the table, the main reason is GCD of (p,p) is also p.

So if whatever the input was that will always be the output.

Explanation:

Here, two inputs given in the problem 2 and 5. Lets use 5.

Let, p = 5
GCD(p,p) = GCD(5,5) = 5

That is certainly wrong and doesn’t match the answer this input.

To generate the matrix of GCD we will require $O(n^2)$ space of which less than $( \frac {n^2}{2} )$ or, exactly $( \frac {n^2}{2} - \frac{n}{2} )$ cells will be filled. Since whatever we calculate the upper or the lower half both will have mirror values.

Idea:

We know for a number n in a n * n matrix there exist all pairs of number between 1 to n.
Say if input is 3. All pairs of number between 1 and 3 are,

(1,1),(1,2),(1,3),
(2,1),(2,2),(2,3),
(3,1),(3,2),(3,3)

It can be easily that these can be represented in n by n matrix where n = 3.

Generating a larger GCD board to get an idea:

 1 2 3 4 5 6 7 8 1 2 1 3 1 1 4 1 2 1 5 1 1 1 1 6 1 2 3 2 1 7 1 1 1 1 1 1 8 1 2 1 4 1 2 1

Extra useless information:

From the table it is clearly visible if for a cell the row number can be divided by column number then the column number is the value of that cell otherwise calculate the GCD.

How the table is filled:

From the board, lets take row: 8 and column: 4 for example.

Since (8,4) is number between all pair of number from 1 to 8.

8 = 1 * 8
= 2 * 4

The divisors of 8 are,
1, 2, 4, 8
4 = 1 * 4
= 2 * 2

The divisors of 8 are,
1, 2, 4

The biggest common number between their divisors are 4.
So,

GCD(8,4) = 4

In the ( 8 * 8 ) board the biggest number between all pairs from 1 to 8 is 4. Similarly we can take any two pair of number and get their GCD.

Similarly the answer is calculated for other inputs. From this we see the pattern is that the answer is always floor of half of the input.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Input:

2
2
5

Output:

1
2

Java Code:

/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: 12708 - GCD The Largest java
*/

import java.util.Scanner;

class Main {
public static void main(String[] args) {
Scanner k = new Scanner(System.in);

int count = k.nextInt() + 1;

while (--count > 0) {
System.out.println( k.nextLong() >> 1);
}

}
}


Managerial Accounting: Break Even Point Analysis

Break Even Point:

The point where Total Revenue becomes equal to Total Cost. So at that point there is neither profit nor loss.

Methods of BEP (Break Even Point) Analysis:

(i) Graphical Method.
(ii) Equation Method.
(iii) Formula Method.

The equation and formula method are more accurate. Using equation and formula methods we can get a good graphical representation. Hand plotting graphical method won’t be that accurate.

Below are equation and formula method calculation formula. We can use any one of these methods to get same result.

 Point Equation Method Formula Method BEPQuantity $\text{Total Revenue - Total Cost}$ $\frac{\text{Fixed Cost}}{\text{Contribution Margin Ratio}}$ BEPsales $\text{(CM Ratio x Sales) - Fixed Cost}$ $\frac{\text{Fixed Cost}}{\text{Contribution Margin Ratio}}$ Contribution Margin (CM) $\text{CM = Sales - Variable Cost}$ $\text{CM = Sales - Variable Cost}$ CM Ratio $\frac{\text{CM}}{\text{Sales}} \times 100$ $\frac{\text{CM}}{\text{Sales}} \times 100$

A coffee shop owner sales per cup of coffee with a selling price of $10 and whose variable expense is$5. The owner’s monthly fixed cost is $500. Find the Break even point. Solution : It can be solved in many ways. We can directly plot the graph or use equation method to get the equation and then plot the graph. BEP can be found using formulas above. To draw the graph we know that, $\text{fixed cost + variable cost = Total cost}$ Also at BEP, $\text{Total Revenue - Total cost = 0}$ And, $Total \ Revenue - Total \ Cost = \begin{cases} Profit & \quad \text{if} > 0 \\ Loss & \quad \text{if} < 0 \end{cases}$ Let, x be the number of coffee’s sold. Then, Revenue for 1 cup$10.
Revenue for x cup $10x. variable cost for 1 cup$5.

Question:

ABC company distributes a single product with selling price $16 and whose variable expense is per unit$11. The company’s fixed expense is $16000 monthly. (i) Prepare profit graph for company up to sales level of$ 4000 units.
(ii) Estimate company’s BEP in unit sales using the profit graph.

Solution:

In 4000 units,

Total revenue = 16 * 4000
= 64000
Total Cost = fixed cost + variable cost
= 16000 + 11 * 4000
= 60000
Profit = T.R - T.C
= 64000 - 60000
= 4000

In 4000 units BEP,

$BEP = \frac{F.C}{Sales - V.C} = \frac{16000}{16 - 11} = 3200 \ units$

$BEP \ sales = 3200 \times 16 = 51200$

Managerial Accounting: Cost Sheet Preparation

Application:
Cost Calculation Software.

Question:

Prepare cost sheet for ABC Corporation for last year,
(i) Determine cost of goods manufactured.
(ii) Determine cost of goods sold.
(iii) Prepare an income statement.

 Selling expenses 140000 Raw materials Inventories, January 1 90000 Raw materials Inventories, December 31 60000 Direct Labor Cost 150000 Purchase of raw materials 750000 Sales 2500000 Administrative expenses 270000 Manufacturing overhead 640000 Work in process inventory, January 1 180000 Work in process inventory, January 1 100000 Finished goods inventory, January 1 260000 Finished goods inventory, December 31 210000

Solution:

ABC Corporation Statement of cost of goods sold
 Particulars Amount ($) Amount ($) Direct Materials: Raw materials, January 1 90000 Add: Purchase of raw materials 750000 * Raw Materials Available for use 840000 Deduct: Raw Materials, December 31 (60000) * Raw Materials used / consumed 780000 Add: Direct Labor cost 150000 * Prime cost 930000 Add: Manufacturing overhead 640000 * Total manufacturing cost 1570000 Add: Work in process, January 1 180000 Less: Work in process, January 1 (100000) (i) Cost of goods manufactured 1650000 Add: Finished goods Inventory, January 1 260000 * Finished goods available for sale 1910000 Less: Finished goods Inventory, December 31 (210000) (ii) Cost of goods sold 1700000
Note:

Statement of cost of goods sold has both cost of goods manufactured and cost of goods sold. So calculating the Statement of cost of goods sold we can get both.

Income Statement:

ABC Corporation Income statement For the year ended December 31
 Particulars Amount ($) Amount ($) Sales 2500000 Less: Cost of goods sold (1700000) * Gross Profit 800000 Less: Operating Expenses Selling Expenses (140000) Administrative Expenses (270000) * Operating Income 390000
Note:

Only manufacturing cost are shown in COGS statement. Non manufacturing cost such as selling, administrative costs are shown in income statement.