Welcome to our first edition of the Badoo Coding Challenge! Below, you will find all the relevant information about the challenge. We hope participants will enjoy solving the problems as much as we enjoyed designing them.

Badoo Tech

Winners and prizes

  • Finalists - There will 25 finalists where each one will receive a goodie bag.
  • Winners - Out of the 25 finalists 5 winners will be chosen. Each winner will get £1000 and the chance to for a 1 day visit in London in Badoo HQ.
  • Overall winner - Out of the 5 winners one will be declared as the overall winner. On top of the “Winners” prize they will get a handset of their choice with a value of up to £700.

How does it work?

Challenge problems


For each problem you will have to submit a solution. The solution can be written in any language they chose. Given a certain input that we will provide, your solution must generate the correct output. Each problem has a description, and an example of an input and output.

Getting to work: Each problem has two phases. The test phase and the final submission:

  1. The test phase will help you to check if your code works correctly with a simple input. You will be able to download a test input, run it through your solution and upload your output. We will let you know if this output is correct or not. If it’s not you should change your code until its output is correct. You can repeat this step as many times as you want until you upload a correct output which is a mandatory step to progress to the next phase. The output file should be a plain text file.

  2. In the final submission you will download a more complex test input. You should then apply it to your solution and submit the output and the solution. Notice that unlike the test phase you will not be notified of the correctness of the output.

You will be able to proceed to the next problem only if you have successfully completed the two phases of the current problem.


Let’s practice…

The Euclidean algorithm

The Euclidean algorithm, or Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in Euclid’s Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest numerical algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. [source: Wikipedia]

Can you write a program that implements it?

Input

First line will contain the number of test cases T. T blocks will follow with: One line containing three integers: A that indicates the first integer. B that indicates the second integer. G that indicates a tentative greatest common divisor (GCD) of A and B.

Output

The program should output one line per test case with OK if the provided GCD is right or the real GCD if it’s different.

Limits

T <= 10

A, B, G <= 100

A, B, G > 0

Sample input

3
54 32 2
33 55 5
42 7 7

Sample output

OK
11
OK

There’s still time for you to register and create your profile. Don’t miss your chance and hope to see you during the challenge!

Badoo Tech Team