Problem Link:
https://practice.geeksforgeeks.org/problems/shop-in-candy-store1145/1#
(It is also the problem of the day for 28-04-2022)
Solution:
Using Arrays.sort and Without additional arraylist:
class Solution{
static ArrayList<Integer> candyStore(int arr[],int n,int k){
ArrayList<Integer>ab=new ArrayList<Integer>();
Arrays.sort(arr);
/*for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
*/
int start=0;
int end=arr.length-1;
int cost=0;
while(start<=end){
cost=cost+arr[start];
start++;
end=end-k;
}
//System.out.println(cost);
start=arr.length-1;
end=0;
int cost2=0;
while(end<=start){
cost2=cost2+arr[start];
//System.out.println(cost2);
end+=k;
start--;
}
// System.out.println(cost2);
ab.add(cost);
ab.add(cost2);
return ab;
}
}
Time Complexity:O(NLOGN)[Arrays.sort() is used][GFG Time:0.55/1.61]
Space Complexity: O(N)[Array is given.]
Auxiliary Space: O(1)
Total Test Cases:62
###################################################################################
Approach 2: Using PriorityQueue and Additional ArrayList
class Solution{
Solution 1:
static ArrayList<Integer> candyStore(int candies[],int n,int k){
PriorityQueue<Integer>pq=new PriorityQueue<Integer>();
ArrayList<Integer>aa=new ArrayList<Integer>();
ArrayList<Integer>ab=new ArrayList<Integer>();
for(int i=0;i<candies.length;i++){
pq.add(candies[i]);
}
while(!pq.isEmpty()){
aa.add(pq.remove());
}
//System.out.println(aa);
int start=0;
int end=aa.size()-1;
int cost=0;
while(start<=end){
cost=cost+aa.get(start);
start++;
end=end-k;
}
//System.out.println(cost);
start=aa.size()-1;
end=0;
int cost2=0;
while(end<=start){
cost2=cost2+aa.get(start);
end+=k;
start--;
}
// System.out.println(cost2);
ab.add(cost);
ab.add(cost2);
return ab;
}
}
Time Complexity: O(N)[PriorirtyQueue is used]GFG Time:0.58/1.61]
Space Complexity: O(N)[Array is given.]
Auxiliary Space: O(N)[ArrayList is used]
Total Test Cases:62
Approach :
In question there are two cases:
1. to find for minimum
2. to find maximum
Step 1: we will sort the array first in increasing order.
Step 2: start pointing to 0 and end at the last index.
Minimum:
1. We will traverse the array from start and simultaneously add on the element value in the cost variable and along with it we will reduce the end pointer by k and increase start by 1 in every iteration.
Maximum:
1. We will traverse the array from the end and simultaneously add on the element value in the cost2 variable and along with it we will increase start by k and decrease-end by 1 in every iteration.
[Variable names explained in the approach and used in code may be different and can have a different meaning.]
Difference:
The difference between both approaches is TIME and MEMORY usage.
In the first approach
Time: O(NLOGN) Auxiliary Space: O(1)
In the second approach :
Time: O(N) Auxiliary Space: O(N)
This is a space-time tradeoff.
=========================================================================
"Thanks For Reading.😇"
"Share Further To Increase knowledge.😊"
Comments
Post a Comment