×

# MIXCOLOR - Editorial

Div1, Div2
Practice

Author: Shivangi Gupta
Tester: Triveni Mahatha

Easy

Sorting

# PROBLEM:

You are given an array with $N$ elements. In one operation you can replace $A[i]$ by $A[i]+A[j]$ where $j \neq i$. Find minimum number of operations required to make each element of array pairwise distinct.

# EXPLANATION:

Lets keep a track on the current maximum of the array. If we add maximum to any element already present in the array, it will give us a new maximum as well as new element that was not present in the array before. We can do this process for all the elements that are repeating. Hence total no. of operation required = $N$ - (total unique elements already present in the array). You can prove this using contradiction if you want to.

Main problem here reduces to finding total number of unique elements present in the array. This task can be solved using sorting and linear traversal of the array.

# Time Complexity:

$O(N.logN)$

# AUTHOR'S AND TESTER'S SOLUTIONS

This question is marked "community wiki".

306719
accept rate: 7%

19.8k350498541

 0 It is showing access denied when trying to view setters/testers solution. answered 13 Mar '18, 15:13 1●1 accept rate: 0%
 0 hello, I had my solution for this problem up and running in the practice section with various test cases being successful, But still it gave SIGSGEV while submitting..Don't know how to improve..where it was running successfully in other online ides. here is my solution https://www.codechef.com/viewsolution/17767577 I know (I have mistakenly put a line which can lead to WA) , But even after removing that I keep getting that SIGSGEV Error. I don't see any wrong in the algorithm(as it ran successfully under various test cases in various online IDEs)..What modification can be done in the code to avoid the SIGSGEV Error?? answered 13 Mar '18, 21:52 1★ayan_19 1●2 accept rate: 0% yes , thats why I used the array size 10^9 once but, it is giving TLE @azad123 (13 Mar '18, 23:04) ayan_191★
 0 You are getting error due to this line vs[(a[j])]+=1 as the value of a[j] can be up to 10^9 and the size of vs array is max+100 which is smaller than 10^9. Also you can create maximum array of 10^6 only So you can not solve it by using this method.You need to sort the elements first and then count the number of duplicates. answered 13 Mar '18, 22:49 4★azad123 21●2 accept rate: 0%
 0 well this is the thing you can traverse only up to 10^6 in 1 sec. answered 13 Mar '18, 23:08 4★azad123 21●2 accept rate: 0%
 0 how will it work in the case when max element of array is already equal to 10^9??@author answered 17 Mar '18, 22:48 3★vicerys 1 accept rate: 0%
 0 I solved it using C++   Theorem: The Number of minimum moves = number of extra color i.e. Total colors- # of distinct colors. Proof: We can get a new color by adding a repeated color with the highest color. This way its just O(N). link My Solution answered 21 Mar '18, 16:47 1●1 accept rate: 0%
 0 simply, we can find the number of unique elements using a set. for those who are using this through array traversal this is definitely going to give NZEC or SIGSEGV as the range is 10^9. check out this solution: https://www.codechef.com/viewsolution/19804820 answered 22 Aug '18, 00:11 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×1,024
×968
×801
×267
×7

question asked: 10 Mar '18, 06:13

question was seen: 1,924 times

last updated: 22 Aug '18, 00:11