ASU SoDA Coding Challenge VI Easy Question #1

On Sunday, November 24, 2019, I participated in the ASU SoDA Coding Challenge VI. The ASU Software Developer’s Association (SoDA) is a club that is dedicated to teaching aspiring programmers how to solve complex problems that will prepare them for industry. The club runs recruiting events, Hackathons, Interview Prep sessions, and other activities that I have personally found invaluable during my first semester at ASU. I would strongly recommend anyone with a remote interest in computer science to join the club.

The SoDA Coding Challenge had 15 questions which were divided into three categories of three questions based on their respective difficulty levels. The Easy Questions, the Medium Questions, and the Hard Questions were made available to the contestants through Google Forms, and participants would have proctors manually check their code to make sure their programs worked.

Easy Question #1 concerns updating a list of integers to make the product of the list equal to 1. The question reads:

ASU SoDA Coding Challenge VI Easy Question 1: Make the Product One

Say you are given n numbers, a1 a2 ….an . With the cost of 1 point you can add or subtract 1 from each number. 
You can apply this operation to the same number any number of times.
Our goal is to make the product of the numbers equal 1.
For example, for n=3 and numbers [1,−3,0] we can make product equal to 1 in 3 points: add 1 to the second element, add 1 to second element again, subtract 1 from third element, so that array becomes [1,−1,−1]. And 1⋅(−1)⋅(−1)=1.
What is the minimum cost we will have to pay to do that?

Input:
The input is an array of integers a1,a2,…,an a1,a2,…,an (−10^9≤ai≤10^9) — the numbers.
Output: 
Output a single number — the minimal number of coins you need to pay to make the product equal to 1.

Test Cases:
input
-1 1
output
2
input
0 0 0 0
output
4
input
-5 -3 5 3 0
output
13

This problem was a great warm up for the later questions in the competition. Here’s my solution:

Solution #1: O(n) Approach

We can observe that the list will only have a product of 1 if all of the elements are either 1 or -1 and the number of -1’s in the list is even. Thus, it suffices to iterate through the array. For each negative entry e, the total cost to update it to -1 will be (-1 – e). For each positive entry e, the total cost to update it to 1 will be (e – 1). For any 0 entry, the total cost to update it to either 1 or -1 will be 1. With this iteration, it is possible to find the total cost to update every entry to either 1 or -1.

To ensure that the product is 1 and not -1, it suffices to count the number of negative elements while iterating through the array. If the number of negative elements is odd, the product will be -1. In cases where there are no 0 elements in the list, this would require an additional cost of 2, because one of the -1 elements would need to be updated to +1. However, when there is a 0 element, this would not change the total cost, because the 0 element could just be updated to a +1 instead of a -1. All of this can be done while iterating through the array once, so this solution runs with O(n) time complexity. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 SoDA Coding Challenge VI Easy Problem #1
 https://docs.google.com/document/d/1E_8BtPkGH5iQSBVOxr_lZpjrS5pToaWtDBS1WEZTxWw/edit
 '''
 
 import sys
 import time
 
 for x in sys.stdin:
     myInput = map(int,x.split())
 
 def minimumCost(myList):
     tn = 0
     total = 0
     z = 0
     for x in myList:
         if(x<0):
             total+=(-1-x)
             tn+=1
         elif(x==0):
             total+=1
             z+=1
         else:
             total+=(x-1)
     if(tn%2==1):
         if(z>0):
             return total
         return total+2
     return total
 
 start = time.time()
 print minimumCost(myInput)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 1001006
 --- 1.00135803223e-05 seconds ---
 
 for input of myInput = [0,0,0,0,0,0,0,0,0,0,999,999999]
 ''' 

And with that, we’re done. I like this problem. It is approachable for anyone with basic experience with arrays, and it is not too difficult for people with no USACO experience to solve. At the same time, it is not completely trivial, as handling the relationship between negative elements and zero elements requires some thought.

Thanks for reading! See you tomorrow.