EXOCODE4 - Editorial

editorial
, , , , ,
1

Problem Link:[EXOCODE4 Problem - CodeChef][1]

Author:[vivek96 | CodeChef User Profile for Vivek Chadha | CodeChef][2]

DIFFICULTY:CakeWalk

PREREQUISITES:Basic Programming,Array

PROBLEM:Chef Purchased an array A having N Integer values,After Playing it for while,he got bored of it and decided to update value of its element.In one second he can increase value of each array element by 1.He wants each array element’s value to become greater than or equal to K.

Please Help Chef to find out the minimum amount of time it will take,for him to do so…

EXPLANATION:Since we can only increase all the elements by 1, the minimum element will take most step to reach K.So we have to find the minimum element in array A and answer will difference between K and minimum element.

One corner case is if K is less than minimum element in the array A

Time Complexity:O(N)

AUTHOR’S AND TESTER’S SOLUTIONS:

![alt text][3]

Note:
We can also use Sorting(Bubble,Quick,etc) to find minimum element in Array, but this will increase time complexity
[1]: EXOCODE4 Problem - CodeChef
[2]: vivek96 | CodeChef User Profile for Vivek Chadha | CodeChef
[3]: https://discuss.codechef.com/upfiles/code_5.png

1 Like
2

Nice algorithm

2 Likes
3

thanks man!

4

Hi @vivek96,

As per problem statement

In one second he can increase value of each array element by 1.He wants each array element’s value to become greater than or equal to K.

Here, chef wants each (not just the minimum) array element value to become greater than or equal to K. The solution proposed in the explanation doesn’t seem to be right. Please clarify if I am missing any key information.

As per my understanding, we need to parse through the input array, check if each element less than K, get the difference and add it to sum (to which you keeps on adding the difference while parsing through the element). if array element is more than K just continue.

Thank you,
Murali Marimekala

5

In one second he can increase the value of each array element by 1.This means here in one second the chef can increment all values of an array by one.
Hence, the maximum seconds required to make all elements in an array will be the difference between k and minimum element in that array.