This is the same approach i came with bro this seems to be easy to crack with some observation until we realise we can pick any i and j and there is no contidition such that i
and we can sort both the arrays since we can change a[i] and a[j] how ever we want. the optimal approach can be using nextgreater and next smaller element
1. calculate prefix sum of sorted array B 2. find sum of array A 2.a. if sum(A) > sum(B) ans = n - 1 // here n is the size of array 2.b. if sum(A) == sum(B) ans = n 2.c. if Sum(A) < Sum(B) ans = upper_bound(pref.begin(), pref.end(), Sum(A)) // pref stores the prefix sum of array B assuming 0th index following sir ( @Kumar K ) please check if this approach is correct Intuation of approach:- as we allowed as many operations we want in array A, so first of all, we will make n - 1 indexes of Array A 0, and take all the sum to the last index then we will sort array B and try to make elements of array A equal to array B eg :- A = [1, 2, 4] B = [1, 3, 1] op1 :- A = [0, 2, 5] op2 :- [0, 1, 6] op3 :- [0, 0, 7] sort Array B:- [1, 1, 3] now trying to make elements equal to B's elements from the smallest to largest elements op4:- [1, 0, 6] op5:- [1, 1, 5] Ans :- 2
Can someone tell, is this code correct: int maxSimilarity(const vector& inv1, const vector& inv2) { int n = inv1.size(); vector diff(n); // Calculate the difference between corresponding elements for (int i = 0; i < n; ++i) { diff[i] = inv2[i] - inv1[i]; } // Sort the difference array in ascending order sort(diff.begin(), diff.end()); int positiveSum = 0, operations = 0; for (int i = 0; i < n; ++i) { if (diff[i] > 0) { if (positiveSum > 0) { positiveSum--; } else { operations++; } } else { positiveSum += diff[i]; } } return operations; }
So I'm writing this comment before seeing the solution. So what I'm getting intution that We can simply get the subtract the 1st array from 2nd get the net sum if the sum is odd then n-1 element can be equal. otherwise all n elements can be equal. Let me know if I'm thinking in correct manner?
![Kumar K [Amazon]](http://yt3.ggpht.com/AC31qZhXcWFgj2sgT3X0p-b0zXqCPQ5pl10tdyr72yXkk4-MwpcMg59JZO-TySohn1QkziGf57Y=s48-c-k-c0x00ffffff-no-rj)
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/mqdefault.jpg)
We can calculate the sum(A) and from sorted(B), start from the left and decrement the value B[i] from sum(A) until B[i] 0 and i == len(A)].
This is the same approach i came with bro this seems to be easy to crack with some observation until we realise we can pick any i and j and there is no contidition such that i
Mind Blowing Approach 😍😍😍😍
Love you
On Diwali also u r working for us
The Time Complexity is not O(2N) but O(NlogN ) because we are sorting the array.
and we can sort both the arrays since we can change a[i] and a[j] how ever we want. the optimal approach can be using nextgreater and next smaller element
brilliant and intuitive solution
Sir is never off duty🔥🔥
Great approach sir ❤
Happy diwali sir ❤🎉
Amazing explanation sir👏👏
Love you
Brilliant kumar K sir🎉🎉🎉🎉❤❤
Thankyou very much ❤
nice
very nice explanation sir
Please also provide code
1. calculate prefix sum of sorted array B
2. find sum of array A
2.a. if sum(A) > sum(B) ans = n - 1 // here n is the size of array
2.b. if sum(A) == sum(B) ans = n
2.c. if Sum(A) < Sum(B) ans = upper_bound(pref.begin(), pref.end(), Sum(A)) // pref stores the prefix sum of array B assuming 0th index following
sir ( @Kumar K ) please check if this approach is correct
Intuation of approach:-
as we allowed as many operations we want in array A, so first of all, we will make n - 1 indexes of Array A 0, and take all the sum to the last index
then we will sort array B and try to make elements of array A equal to array B
eg :- A = [1, 2, 4] B = [1, 3, 1]
op1 :- A = [0, 2, 5]
op2 :- [0, 1, 6]
op3 :- [0, 0, 7]
sort Array B:- [1, 1, 3]
now trying to make elements equal to B's elements from the smallest to largest elements
op4:- [1, 0, 6]
op5:- [1, 1, 5]
Ans :- 2
i think this feels write
But iska answer to 1 hoga shayad!!!!!
@@phanibhusan6538 why 1?
@@phanibhusan6538 yeah I stopped after 5th step you can continue 2 steps more to get array A as 1 3 3
Maybe you are correct :)
Can someone tell, is this code correct:
int maxSimilarity(const vector& inv1, const vector& inv2) {
int n = inv1.size();
vector diff(n);
// Calculate the difference between corresponding elements
for (int i = 0; i < n; ++i) {
diff[i] = inv2[i] - inv1[i];
}
// Sort the difference array in ascending order
sort(diff.begin(), diff.end());
int positiveSum = 0, operations = 0;
for (int i = 0; i < n; ++i) {
if (diff[i] > 0) {
if (positiveSum > 0) {
positiveSum--;
} else {
operations++;
}
} else {
positiveSum += diff[i];
}
}
return operations;
}
I think its correct
wow
So I'm writing this comment before seeing the solution. So what I'm getting intution that We can simply get the subtract the 1st array from 2nd get the net sum if the sum is odd then n-1 element can be equal. otherwise all n elements can be equal. Let me know if I'm thinking in correct manner?
Maybe you are correct :)
How can the maximum answer can be N???
When elements of both the arrays match.