PerfectSequences

Member SRM 505 · 2010-11-01 · by vexorian

Member SRM 505 · 2010-11-01 · by vexorian · Math, Simple Search, Iteration

Show categories

Class Name: PerfectSequences

Return Type: String

Method Name: fixIt

Arg Types: (vector<int>)

Problem Statement

A perfect sequence is a sequence such that all of its elements are non-negative integers and the product of all of them is equal to their sum. For example: {2,2}, {1,3,2} and {0,0,0,0} are perfect sequences and {4,5,6} and {0,2,-2} are not perfect sequences (4*5*6 is not equal to 4+5+6, and negative numbers are not allowed by the definition).

You are given a int[] seq. Return "Yes" if it is possible to change exactly one element of seq so that the resulting sequence is perfect. Otherwise, return "No".

Constraints

seq will contain between 1 and 50 elements, inclusive.
Each element of seq will be between 0 and 1000000000 (10^9), inclusive.

Examples

{1,3,4}
Returns: "Yes"

If we change the last element to 2, we have {1,3,2}. 1+3+2 = 1*3*2.

{1,1,1,1,1,1,2}
Returns: "Yes"

Replace a 1 with 7. 7+1+1+1+1+1+2 = 14 = 7*1*1*1*1*1*2.

{1,2,3}
Returns: "No"

This sequence is already perfect and it is not possible to change exactly one of its elements and keep it perfect.

{1,4,2,4,2,4}
Returns: "No"

{1000000,1,1,1,1,2}
Returns: "Yes"

It is possible to replace 1000000 with 6 to make the sequence become perfect.

{8}
Returns: "Yes"

It is possible to change the first element to any non-negative number and the sequence will stay perfect.

{2,0,2}
Returns: "No"

Note that {2,0,-2} is not considered a perfect sequence because negative numbers are not allowed by the definition.

16)

{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4}
Returns: "No"

64 bits overflow.

17)

{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}
Returns: "No"

32 bit overflow

Submissions are judged against all 184 archived test cases, of which 9 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PerfectSequences with a public method string fixIt(vector<int> seq) · 184 test cases · 2 s / 256 MB per case