Sudhanshu_Kumar's blog

By Sudhanshu_Kumar, history, 4 years ago, In English

Found this interesting problem:

Two integer arrays A and B are given. We need to convert array A to array B using some operation. Operation is defined as follows: Select any element from A decrease its value by 1 and add it to one of the two neighbours.

The array given is circular, meaning the last element can give its value to the first element.

Find the minimum cost to convert array A to array B, where cost id defined as the distance between them, distance between any consecutive element is 1.

Constraints: A,B<=100.

ex: A=[2,3,1,5] B=[2,2,1,6] We need to convert A to B, subtract 1 from index 1 of A i.e. element 3 and give it to 1 making it 2, now he array A is [2,2,2,5]. Now remove 1 from index 2(element 2) and give it to element 5 making it 6, now the array becomes [2,2,1,6], so total cost is 2.

Any suggestion to proceed to this problem.

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By Sudhanshu_Kumar, history, 4 years ago, In English

Given an array with n strings and an integer k. White and watson are playing a game. White gets to start game first always. Game follows as: White first picks any string among first k strings.Watson can next pick any string that starts with last character of string picked which from next k strings (next to where white picked). This goes on until a player can choose a string from given k strings. If at any point, a player is unable to choose, he loses. Both the players select strings optimally.If there is a way White can win always, output “Yes” and the string he must choose as first string else output “No” and string watson must choose as first string, that guarantee his win(in this case assume, white selects first string always).

Suggest some approach!!

Full text and comments »

  • Vote: I like it
  • -17
  • Vote: I do not like it

By Sudhanshu_Kumar, history, 4 years ago, In English

How to divide a circular array into k group of contiguous element such that difference between maximum sum and minimum sum is minimum. Each group have contiguous element of array. For e.g If the array is as follow. [6 13 10 2] and k=2 then o/p should be 18(6+10+2)-13=5. As array is circular 6,10,2 are contiguous element of array.

For e.g If the array is as follow. [100 92 133 201 34 34 34 94 108] and k=4 then group as follow 208(108,100), 225(92,133), (201), 196(34,34,34,94) so 225-196=29

I was thinking of binary search similar to painter's partition problem, please clarify if the approach is correct.

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it