Join Us
Loading Similar Posts
Entering edit mode
Question 1
Click here to Practice
Submit Problem to OJ
The Chemist
Question 2
Click here to Practice
Submit Problem to OJ
Question 3
Click here to Practice
Submit Problem to OJ
Question 4
Click here to Practice
Submit Problem to OJ
You are given an array A[ ] of N integers. You can perform the following operation as many times as you want.
- Select any integer 'x' and add it to each element of the array.
You are also given the integer y. Your task is to return the maximum possible frequency of y after performing the above operation optimally on the array.
Example 1
Input
N = 4, y = 2
A[ ] = {3, 1, 4, 5}
Output
1
Explanation:
Choose x = 1, now the array becomes
A = {4, 2, 5, 6}
Example 2
Input
N = 2, y = -10
A[ ] = {1, 1}
Output
2
Entering edit mode
The Abandoned City :: Simple Approach of variable sliding window
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,target;
cin>>n>>target;
vector<int> nums(n);
for(int i=0;i<n;i++){
cin>>nums[i];
}
int i =0;
int j =0;
int count = INT_MAX;
int sum = 0;
while(j < n){
sum = sum + nums[j];
if(sum < target){
j++;
}
else if(sum == target){
count = min(count,j-i+1);
j++;
}
else{
while(i < n && sum > target){
sum = sum - nums[i];
count = min(count,j-i+1);
i++;
}
if(sum == target){
count = min(count,j-i+1);
}
j++;
}
}
if(count == INT_MAX){
cout<<-1;
}
else{
cout<<count;
}
}
Entering edit mode
Question 4
Overview
- We are given an array of N integers with some value.
- we are not given any constraints for the problem so we assume there can be almost a 10^5 size array and the value of each element can range from
-10^5 to +10^5. - We are given an operation that we can choose any element 'X' and increase that value in every element of the array.
- Also we are given some value Y. we need to find the maximum frequency of Y in the given array by performing the above operation.
Analysis and Solution
- If we look at the test cases and problem statement carefully we can derive the following assumption:
- First, it does matters how many times we can perform any operation.
- Secondly, if we choose any x and increase it we can easily see that that operation affects the whole array not a single element in the array.
- Third, it does not matter the value of y because we are able to make the increase in all the elements with x.
- So the final solution we can derive here is that the maximum frequency of any element in the array is the solution for our answer.
- So we can create a hashmap and traverse the array and find the frequency of every element.
- After that, we can simply run a loop and check the maximum frequency of any element in the array and print the maximum frequency.
- Time Complexity : O(N)
Entering edit mode
Solution for Question 2
Analysis
In the question it is mentioned that we need to partition the array into any number of partitions so as to maximize the special sum defined as P<sub>1</sub> - P<sub>2</sub> + P<sub>3</sub> ... + (-1)<sup>k+1</sup>P<sub>k</sub>, where k is the total number of partitions.
So integers in odd numbered partitions are getting added, and integers in even numbered partitions are getting subtracted.
Let us look at the problem as 2 different cases:
Case 1: First element is positive. In this case we can partition the array such that we only have positive elements in the first partition, then the negative elements in the second partition, positive elements in the third partition and so on. This will ensure that positive elements get added to our sum (since they are in odd numbered partitions), and negative elements get subtracted (since they are in even numbered partitions). So this will basically result in adding the absolute value of all the elements in the array.
Case 2: First element is negative. In this case, the first partition will have a negative element which is the first element of the array. If the second element of the array is negative, we can create a new partition which is the second partition and add this element to that partition, because we want negative elements to be in even numbered partitions. If the second element is positive, we can add them to this partition itself because we want positive numbers in odd numbered partitions. After this everything can be continued like Case 1 itself. So this will basically result in adding the absolute value of all the elements in the array from 2 to n, arr[2...n], but for the first element it needs to be added normally (since it is negative we don't take its absolute value).
Hence, overall the answer is arr[1] + summation from 2 to n, abs(arr[i]), or it can also be written as arr[1] + abs(arr[2]) + abs(arr[3]) + .... abs(arr[n]).
Implementation
int ans = a[0];
for(int i=1;i < n;i++)
ans += abs(a[i]);
Entering edit mode
Q1) The Chemist
D here is the desired_result given in the question
First of all let's suppose we take two elements as a[x] and a[y] then our target is to minimize | a[x] - a[y] -D | and for the corresponding minimum we need to find the maximum value of a[x] + a[y] where x!=y. where | P | represent absolute value of P https://en.wikipedia.org/wiki/Absolute_value Solution:
- Sort the array.
- The expression we need to minimize is | a[x] - a[y] -D | which can be re written as | a[x] - D -a[y] | . Hence we just need to find optimal y for each x
- For each x there are two choices because | (a[x] - D ) - a[y] | opens with two signs.
1. either find optimal y which minimizes a[x] - D - a[y] such that a[x] - D > = a[y] , which it does by find the maximum a[y] < = a[x]+D 2. either find optimal y which minimizes a[y]-(a[x]-D) such that a[y] > = a[x]-D , which it does by finding the minimum a[y] > =a[x]-D - Hence for each x we find optimal y which minimizes the above expression and for each minimizing value find the maximum value of a[x] + a[y] just by updating it with new maximum value
Hence for each x we could find the optimal y either by binary search or by two pointers.1. By Binary Search ---- Since the array is sorted we could find the optimal y by searching for the lower_bound or upper_bound 2. By Two Pointers ---- Let's take two pointer one for x and other for y such that a[y] > = a[x] and y > x (Remember the array is sorted) . let's shift the pointer y until a[y] - a[x] < = D and let's suppose we got optimal (y=Y) for x such that a[y]-a[x] < = D and we know a[y+1]-a[x] > D then we need to just shift the pointer y to right for each {x+1,x+2...} because if we take our pointer y to left it will increase the expression value because it will decrease a[y]-a[x] and increase D-(a[y]-a[x]) . Similarly it can be proved for a[y] - a[x] > D.
Entering edit mode
Solution for Question 3
Analysis
In the question it is mentioned that we need to find the minimum distance we need to travel in order to get at least target number of coins. Also, we can't change our direction while moving, and can only move to the left or to the right. So, say we start from position i and go to position i-x, then that is the same as starting from i-x and going to position i. This is because the sum of the subarray from i to i-x will remain the same, whether we traverse from left to right or right to left. So, we assume that we choose a starting point and always go to the right, without any loss of generality.
Now for each different starting point, we need to find what is the minimum number of steps to the right which are required in order to get at least target number of coins. One method to do this would be for each starting point, traverse the array and find the minimum index at which we are able to get target number of coins. However, this will take O(n^2) time complexity, which is very slow.
An efficient method would be two pointer method. You can read more about it here. In this question, we first keep our left and right pointer at the position 1. Then we move our right pointer to the right, till we get target number of coins. The index at which we stop will be the minimum index for starting point 1. Now, we move are left pointer to the right by 1. In doing so we decrease the number of coins by a1. If the number of coins is still greater than target, then that is also the answer for starting point equal to 2. Otherwise, we move the right pointer to the right till we get target number of coins. We keep on doing this till we traverse the whole array. Since the left and right pointers both move at max n steps (since the length of the array is n), the time complexity of this approach will be O(n).
ll left = 0;
ll right = 0;
ll sum = a[0];
ll ans = LLONG_MAX;
while(right < n)
{
if(sum > = target)
{
ans = min(ans, right-left+1);
sum -= a[left];
left++;
if(left > right)
{
right++;
if(right < n)
sum += a[right];
}
continue;
}
else
{
right++;
if(right < n)
sum += a[right];
}
}
if(ans==LLONG_MAX)
ans = -1;
Entering edit mode
The Chemist Question can be done by 2 approaches 1st is brute i.e O(n^2) 2nd is the sort + binary search.
The 1st approach give the TLE as the constraint is of 10^5 ,So we have to optimised it in O(nlog(n)) for that sorting + binary search
1st Approach
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,res;
cin>>res>>n;
vector<int> nums(n);
for(int i=0;i<n;i++){
cin>>nums[i];
}
int count= INT_MIN;
int ans = INT_MAX;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int x = abs(nums[i] - nums[j]);
if(ans > abs(res - x)){
ans = abs(res - x);
count = (nums[i]+nums[j]);
}
else if(ans == abs(res - x)){
ans = abs(res - x);
count = max(count,nums[i]+nums[j]);
}
}
}
cout<<count;
}
And 2nd Approach is that try to find second element for each first element for this time Complex = traversing every element to get first element and log(n) for finding optimal second element. O(nlog(n)).
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,res;
cin>>res>>n;
vector<int> nums(n);
for(int i=0;i<n;i++){
cin>>nums[i];
}
sort(nums.begin(),nums.end());
int count = 0;
int diff =INT_MAX;
int check_diff = INT_MAX;
for(int i=0;i<n;i++){
int x = nums[i];
int start = i+1;
int end = n-1;
while(start <= end){
int mid = (end - start)/2 + start;
int diff = abs(nums[mid] - x);
if(diff < res){
if(check_diff > res - diff){
check_diff = res - diff;
count = x + nums[mid];
}
start = mid + 1;
}
else if(diff > res){
if(check_diff > diff - res){
check_diff = diff - res;
count = x + nums[mid];
}
end = mid -1;
}
else{
check_diff = 0;
count = x + nums[mid];
break;
}
}
}
cout<<count<<"\n";
}
Entering edit mode
Max Possible Frequency
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
vector<int> ans(n);
for(int i=0;i<n;i++){
cin>>ans[i];
}
map<int ,int> m;
for(int i=0;i<n;i++){
m[ans[i]]++;
}
int count =0;
for(auto it: m){
count = max(count,it.second);
}
cout<<count<<"\n";
}
