Sum Of Unique Elements LeetCode
Approach Explained:
Here first we will add all the numbers in the ArrayList 1 . After that we will traverse the ArrayList1 and then add all the duplicates in the ArrayList 2 . We are doing sum simultaneously for both ArrayList. Then, we will have sum of the original ArrayList (the input array) and duplicate elements sum2. We will then subtract sum2 from sum1 which is ultimately the sum of all unique elements.
First Way:
TIME O(N) [LeetCode Time 3 ms]
SPACE O(N) [Using of Two ArrayLists][LeetCode Memory Uasge : 36.8MB less than 34.90%]
class Solution {
public int sumOfUnique(int[] nums) {
int sum=0;
int sum2=0;
ArrayList<Integer> aa=new ArrayList<Integer>();
ArrayList<Integer> ab=new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
aa.add(nums[i]);
sum=sum+aa.get(i);
}
for(int i=0;i<aa.size();i++){
if(Collections.frequency(aa,aa.get(i))>1){
ab.add(nums[i]);
sum2=sum2+nums[i];
}
}
return sum-sum2;
}
}
=========================================================================
Approach Explained:
Here first we will add all the numbers in the ArrayList 1 . After that we will traverse the ArrayList1 and then add all the duplicates in the ArrayList 2 . Then we will traverse the list separately and have sum of both lists. Then, we will have sum of the original ArrayList (the input array) and duplicate elements sum2. We will then subtract sum2 from sum1 which is ultimately the sum of all unique elements.
Second Way:
TIME O(N) [LeetCode Time 3 ms]
SPACE O(N) [Using of Two ArrayLists][LeetCode Memory Uasge : 36.7MB less than 45.45%]
class Solution {
public int sumOfUnique(int[] nums) {
int sum=0;
int sum2=0;
ArrayList<Integer> aa=new ArrayList<Integer>();
ArrayList<Integer> ab=new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
aa.add(nums[i]);
}
for(int i=0;i<aa.size();i++){
sum=sum+aa.get(i);
}
for(int i=0;i<aa.size();i++){
if(Collections.frequency(aa,aa.get(i))>1){
ab.add(nums[i]);
}
}
for(int i=0;i<ab.size();i++){
sum2=sum2+ab.get(i);
}
return sum-sum2;
}
}
=========================================================================
Approach 3: Using One ArrayList
Time: O(N) [LeetCode Time : 2 ms]
Space: O(N) [LeetCode Memory: 36.6MB less than 58.27%]
class Solution {
public int sumOfUnique(int[] nums) {
int sum2=0;
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
sum2=sum2+nums[i];
}
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
map.put(nums[i],map.get(nums[i])+1);
}
else
map.put(nums[i],1);
}
int sum=0;
for (Map.Entry<Integer, Integer> set :map.entrySet()) {
if(set.getValue()>1){
sum=sum+set.getKey()*set.getValue();
}
}
return (sum2-sum);
}
}
=========================================================================
Approach 4: Using HashMap
Store all the elements as the key and their frequencies as values in the hashmap. Find out the sum of all elements present in the given array. Then multiply key with the value see for all the elements which have frequency more than 1 (ie all the duplicates) and keep on adding their sum.
Subtract sum2 from sum1 and that will be our desired answer.
Actually, we find out the sum of all the duplicates and reduce it from the sum of all elements, and hence we will get the final result as the sum of unique elements only.
TIME: O(N) [Iterating whole array][LeetCode Time : 1ms]
SPACE:O(N) [Using HashMap] [LeetCode Memory: 36.4 Mb less than 90.62%]
class Solution {
public int sumOfUnique(int[] nums) {
int sum2=0;
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
sum2=sum2+nums[i];
}
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
map.put(nums[i],map.get(nums[i])+1);
}
else
map.put(nums[i],1);
}
int sum=0;
for (Map.Entry<Integer, Integer> set :map.entrySet()) {
if(set.getValue()>1){
sum=sum+set.getKey()*set.getValue();
}
}
return (sum2-sum);
}
}
Thanks for Reading.
Knowledge grows by sharing not by saving 😇.
Comments
Post a Comment