Wealth and Magic

#1

Given an array of coins each having some value.Array size is N. You can change the value of any any coin except the first and last coin. You can change the value of ith coin to half of sum of value of (i-1)th and (i+1)th coin but for doing so, two condition needs to be satisfied.

(1) value of both (i-1)th and (i+1)th coin should be even and

(2) if jth coin’s value is changed after ith coin’s value then j should be greater than i

Now your task is to maximize the absolute difference between the sum of values of 1st half of coins of array and values of 2nd half of the coins of array. If array size is odd ignore middle element.

Can anyone suggest me the algo to find the answer.

The task is to find the maximum absolute diffeerence.

My algo: 1. find sums of left half and right half 2. if left half> right half maximize left half by making operations given and minize left half but i am not geting correct answer.

PS: I attended one interview one week before. It was asked there I could not figure out the approach.

1 Like
#2

hello @mr.dheeraj000
pls refer this thread-> link

1 Like
#3

@aman212yadav I tried but getting wrong answer for this case 5,6,5,2,1,7,9,7,2,5.
I am getting 12 as answer instead of 20.
here is link to my solution https://ide.codingblocks.com/s/362454

1 Like
#4

@mr.dheeraj000
do u have link for this problem?

1 Like
#5

No I have photos of the question.

WhatsApp Image 2020-10-25 at 4.02.30 PM (1)
WhatsApp Image 2020-10-25 at 4.02.30 PM (1)1040×585 36.6 KB
WhatsApp Image 2020-10-25 at 4.02.30 PM
WhatsApp Image 2020-10-25 at 4.02.30 PM1040×585 74.6 KB

#6

check value of n in the constraints section (its very less).
just go with the brute force no optimisation needed

#7

Please send solution of your approach. I tried my best :sweat_smile:

#8

i dont have code bro.this is the first time i have seen this question.

here the brute force approach->
a)find all possible sum of first half by making all valid changes
b) find all possible sum of second by making all valid changes.

now for each sum u get in first half compute its abs difference with all the sum of second half.
and update ur overall maximum difference.

or

do valid changes on whole array and compute the abs difference of first and second half and keep track of overall maximum
a) at each index i u have two options
-> either u update it
-> or u dont update it.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#10

Does anyone have solution for this problem ?