IQTest
SRM 327 · 2006-11-22 · by Petr
Problem Statement
You've taken a lot of 'IQ'-style tests, and noticed a common pattern appearing among them. They ask you to continue a given sequence of numbers. Say you're given the numbers 1,2,3,4,5, and are asked: what's the next number? Of course, the answer is 6. A slightly more complicated sequence would be 3,6,12,24,48, where 96 is the answer. Or, if the test is really tough, it might be even 1,4,13,40, where 121 is an answer (the latter follows the rule "multiply by 3 and add 1").
You've decided to write an automatic solver for these problems. It will be based on the following proposition: the rule for generating the sequence is always "multiply by a and add b", where a and b are integer (not necessarily positive) numbers.
You are given a int[] previous containing the first several numbers of the sequence. If this sequence could not be constructed using the above rule, return "BUG". If it could, and you can uniquely determine the next number, return a string containing that number without spaces or extra leading zeroes. If there are several possible next numbers, return "AMBIGUITY" (quotes for clarity only).
Constraints
- previous will contain between 1 and 50 elements, inclusive.
- Each element of previous will be between -100 and 100, inclusive.
{1, 2, 3, 4, 5}
Returns: "6"
{3, 6, 12, 24, 48}
Returns: "96"
{1, 4, 13, 40}
Returns: "121"
{0}
Returns: "AMBIGUITY"
One cannot deduce anything from just one number.
{-1, 2}
Returns: "AMBIGUITY"
There are many possibilities here: "multiply by -2 and add 0" with -4 as the next number, or "multiply by 1 and add 3" with 5, or "multiply by -1 and add 1" with -1, or "multiply by -5 and add -3" with -13, etc.
{57, 57}
Returns: "57"
Sometimes just two numbers are enough to determine the next number. Although there are still many possibilities for a and b like "multiply by 1 and add 0" or "multiply by 2 and add -57", all of them yield 57 as the next number.
{16, -8, 4, -2}
Returns: "BUG"
Here we're multiplying by -0.5, but non-integer multipliers are not allowed.
{6, 5, 4, 3, 1}
Returns: "BUG"
There must have been some misprint.
{-12, 12, -36, 60}
Returns: "-132"
It's "multiply by -2 and add -12".
Submissions are judged against all 179 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IQTest with a public method string nextNumber(vector<int> previous) · 179 test cases · 2 s / 256 MB per case