Given array arr containing N integers. the task is to find the maximum number of unique elements in the array if each element in the array can be changed to its negative i.e. X can be changed to -X in the array.
Example:
Input: arr[] = {-1, 3, 2, 3, 2}
Output: 5
Explanation: Change one 2 to -2 and another 3 to -3 to get the arr[]={-1, 3, 2, -3, -2}, having 5 unique values.Input: arr[] = {1, 2, 2, 2, 3, 3, 3}
Output: 5
Approach: A set can be used in this problem. Follow the below steps to solve:
- Traverse the array from i=0 to i<N, and for each element arr[i]:
- Check if abs(arr[i]) is present in the set or not.
- If it’s not present then insert it in the set.
- Else insert the original value in the set.
- As the set contains only the original values, so the answer will be the size of the set.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of unique elementsint CountUniqueElements(int arr[], int N){ // Set to hold unique values unordered_set<int> s; int i = 0; // Loop to determine and // store all unique values while (i < N) { // Positive value of arr[i] int val1 = abs(arr[i]); // Negative value of arr[i] int val2 = -val1; // Checking if val1 is present or not // If not then insert val1 in the set // Insert val2 in the set if (s.count(val1)) { s.insert(val2); } // Else inserting the original value else { s.insert(val1); } i++; } // Return the count of unique // values in the Array return s.size();}// Driver Codeint main(){ // Declaring Array of size 7 int arr[] = { 1, 2, 2, 2, 3, 3, 3 }; int N = sizeof(arr) / sizeof(int); cout << CountUniqueElements(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to find the number of unique elements static int CountUniqueElements(int arr[], int N) { // Set to hold unique values Set<Integer> s = new HashSet<Integer>(); int i = 0; // Loop to determine and // store all unique values while (i < N) { // Positive value of arr[i] int val1 = Math.abs(arr[i]); // Negative value of arr[i] int val2 = -val1; // Checking if val1 is present or not // If not then insert val1 in the set // Insert val2 in the set if (s.contains(val1)) { s.add(val2); } // Else inserting the original value else { s.add(val1); } i++; } // Return the count of unique // values in the Array return s.size(); } // Driver Code public static void main (String[] args) { // Declaring Array of size 7 int arr[] = { 1, 2, 2, 2, 3, 3, 3 }; int N =arr.length; System.out.print(CountUniqueElements(arr, N)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python 3 program for the above approach# Function to find the number of unique elementsdef CountUniqueElements(arr, N): # Set to hold unique values s = set([]) i = 0 # Loop to determine and # store all unique values while (i < N): # Positive value of arr[i] val1 = abs(arr[i]) # Negative value of arr[i] val2 = -val1 # Checking if val1 is present or not # If not then insert val1 in the set # Insert val2 in the set if (list(s).count(val1)): s.add(val2) # Else inserting the original value else: s.add(val1) i += 1 # Return the count of unique # values in the Array return len(s)# Driver Codeif __name__ == "__main__": # Declaring Array of size 7 arr = [1, 2, 2, 2, 3, 3, 3] N = len(arr) print(CountUniqueElements(arr, N)) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the number of unique elements static int CountUniqueElements(int[] arr, int N) { // Set to hold unique values HashSet<int> s = new HashSet<int>(); int i = 0; // Loop to determine and // store all unique values while (i < N) { // Positive value of arr[i] int val1 = Math.Abs(arr[i]); // Negative value of arr[i] int val2 = -val1; // Checking if val1 is present or not // If not then insert val1 in the set // Insert val2 in the set if (s.Contains(val1)) { s.Add(val2); } // Else inserting the original value else { s.Add(val1); } i++; } // Return the count of unique // values in the Array return s.Count; } // Driver Code public static void Main() { // Declaring Array of size 7 int[] arr = { 1, 2, 2, 2, 3, 3, 3 }; int N = arr.Length; Console.Write(CountUniqueElements(arr, N)); }}// This code is contributed by gfgking |
Javascript
<script> // JavaScript code for the above approach // Function to find the number of unique elements function CountUniqueElements(arr, N) { // Set to hold unique values let s = new Set(); let i = 0; // Loop to determine and // store all unique values while (i < N) { // Positive value of arr[i] let val1 = Math.abs(arr[i]); // Negative value of arr[i] let val2 = -val1; // Checking if val1 is present or not // If not then insert val1 in the set // Insert val2 in the set if (s.has(val1)) { s.add(val2); } // Else inserting the original value else { s.add(val1); } i++; } // Return the count of unique // values in the Array return s.size; } // Driver Code // Declaring Array of size 7 let arr = [1, 2, 2, 2, 3, 3, 3]; let N = arr.length; document.write(CountUniqueElements(arr, N)); // This code is contributed by Potta Lokesh </script> |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Share your thoughts in the comments
