UVA Problem 12708 – GCD The Largest Solution in Java

UVA Problem 12708 – GCD The Largest Solution Java Solution:


Click here to go to this problem in uva Online Judge.

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);
        }

    }
}

One thought on “UVA Problem 12708 – GCD The Largest Solution in Java

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s