TopCoder problem "TransformingArray" used in TCHS SRM 49 (Division I Level Two)



Problem Statement

    You are given a int[] a. Perform the following transformation operation N times: replace each element a[i] with the product of all the elements of a except a[i]. All products are calculated using the values of a at the beginning of the operation. For example, if a = {1, 2, 3}, a single transformation would result in a = {2*3, 1*3, 1*2}. Return the 0-based index of the smallest element in a after all the transformations.
 

Definition

    
Class:TransformingArray
Method:minimalElement
Parameters:int[], int
Returns:int
Method signature:int minimalElement(int[] a, int N)
(be sure your method is public)
    
 

Constraints

-N will be between 0 and 100000, inclusive.
-a will contain between 1 and 50 elements, inclusive.
-Each element of a will be between 1 and 10000, inclusive.
-All elements of a will be distinct.
 

Examples

0)
    
{1,2,3,4}
1
Returns: 3
The transformation will result in a = {2*3*4, 1*3*4, 1*2*4, 1*2*3} = {24, 12, 8, 6}. The last element is the smallest.
1)
    
{3,17,1,10}
2
Returns: 2
2)
    
{650,9511,4746,3187}
4
Returns: 0
3)
    
{8684,3214}
100000
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8279

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10809&pm=8279

Writer:

Nickolas

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Simple Math, Simple Search, Iteration