Hello Everyone, Hope you all are doing well!
Problem: 2149A - Be Positive I was trying to solve this problem but got completely stuck. Then I looked at other people's submissions.
Submission: 340371416 I found this solution, and according to my understanding, it runs in 31ms. Most other solutions follow a similar idea, but I’m a bit confused about one part:
cout << z + ((on % 2) * 2) << endl;
I understand that z counts the number of zeros in the array and on counts the number of negative numbers. What I don’t understand is how this formula calculates the minimum number of positive 1s needed to make the product of all array elements positive.
Could someone please explain the logic behind z + ((on % 2) * 2) in simple words? It would help me a lot.
Thanks a lot for your time and help! Have a great day!
Negative times Negative is positive hence you only need to increase a negative -1 if it does not pair with any other -1. You calculate the number of negative ones(on) and (on % 2 ) gives you if there is any -1 that has not been paired and you have to increase that particular -1 twice. Hence Zero + (on % 2)*2.
When multiplying numbers: A negative number multiplied by a negative number gives a positive result. Therefore, if the count of negative numbers is odd, the product will be negative. To make it positive, we need to adjust by adding 2
If the count of negative numbers is even, their product is already positive, so no adjustment is needed.
Btw, since any number multiplied by 0 is always 0, we must convert all 0s to 1. That’s why the answer is always: num_of_zeros + (num_of_negatives % 2) * 2
All 0's need to be made 1's.
If even no. of -1's, no worry. Else, take any one -1 number and make it 1 using 2 operations.