Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexities
3.
Frequently Asked Questions
3.1.
How to make all array elements equal with minimal cost?
3.2.
In C, can we compare two arrays? 
3.3.
In Python, how do you equalize two arrays?
3.4.
What is the best way to compare two array elements?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Making elements of two arrays identical with minimum increment/decrement

Author Palak Mishra
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this article, we'll look at how to find the smallest number of moves to equalize array elements. We'll compare elements from two arrays to see if they're equal. Both arrays must have the same number of elements as a pre-condition, i.e., both arrays must be the same length.

Also See, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

We need to transform the first array into the second array with the fewest possible operations given two identical arrays. We can either increase or decrease the value of an element by one in a function. It's worth noting that the sequence in which elements appear does not have to match.

We can add or subtract 1 from any number to convert it to another.

Sample Examples

Example 1:

Input:

 A= { 5, 3, 3 }, B= { 3, 4, 4 }

 

Output: 

 2

 

Explanation: We can turn any 3 into a 4 with a single operation and 3 into 4 with a single decrement operation. As a result, A[] becomes (4, 4, 3) a permutation of B[].

 

Example 2 

Input : 

P= { 1, 1, 3},  Q= { 2, 2, 1 }

 

Output : 

2

 

Explanation: We can convert any 1 to 2 with a single operation, and 3 to 2 with a single decrement operation. As a result, P[] becomes 2, 2, 1 (a permutation of P[]).

Approach

We will use Equalising the elements of the Array as an efficient approach for the problem of making elements of two arrays identical with minimum increment or decrement.

Algorithm

  1.  Both arrays are sorted in ascending order.
     
  2. Save the final result as a variable.
     
  3. After sorting both arrays, each array is now in ascending order. As a result, we'll now compare each array element and increment or decrement the value of array b[] depending on the value.

    The implementation of the above strategy is shown below.

Implementation

// operations to make array elements same.
#include <bits/stdc++.h>
using namespace std;
 
int MinimumOpera(int p[], int q[], int m)
{
    //Both arrays are sorted in ascending order
    sort(p, p + m);
    sort(q, q + m);
 
    // to save the final result as a variable
    int result = 0;
 
    // Following the sorting of both arrays, 
    //Each array is now in ascending order. 
    //As a result, we'll now compare each 
    //element of the array and increment or decrement 
    //the value of array b[] depending on the value.
   
    for (int i = 0; i < m; ++i) {
        result = result + abs(p[i] - q[i]);
    }
 
    return result;
}
 
// Driver code
int main()
{
    int p[] = { 3, 1, 1 };
    int q[] = { 1, 2, 2 };
    int m = sizeof(p) / sizeof(p[0]);
    cout << MinimumOpera(p, q, m);
    return 0;
}

Output: 

2

Complexities

Time Complexity

Here in the implementation, we are using the sorting algorithm which has time complexity O(n log n). So, the overall time complexity of our algorithm is O(n log n). Where n is the no of elements in the given array.

Space Complexity

The space complexity of our algorithm is O(1). Since we are not using any extra space.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

How to make all array elements equal with minimal cost?

This is how we approach it: 

  • Sorts the sequence of integers in ascending order.
  • Now, to equalize all elements with less cost. 
  • If A [i] the element of K - A [I].If A [i]> K, decrease the element of A [i] - K. 
  • Update the cost of each operation performed.

In C, can we compare two arrays? 

arr1 and arr2 should be sorted in ascending or descending order. Compare arr1[i] and arr2[i] to see if they are equal for each index I in the array. Return False if the condition fails at any point. Otherwise, return True after the comparison.

In Python, how do you equalize two arrays?

Array equal(a1, a2, equal nan=False) takes two arrays as input and returns True if the shape and elements of both arrays are the same and False otherwise. The equal nan= keyword argument's default value is False, and it must be set to True if we want the method to treat two NaN values as similar.

What is the best way to compare two array elements?

Running a loop and comparing elements one at a time is a simple method. Java directly uses Arrays.equals() to compare two arrays. The Arrays class contains a list of equals() methods for various primitive types (int, char, etc.) as well as one for the Object type (which is the base of all classes in Java).

Conclusion

As discussed in this article, in the problem "Making the elements of two arrays the same with the smallest increment/decrement possible," we sort both the arrays according to the non-decreasing we'll now compare each element of the array and increment or decrement based on the value of array b[].

We hope that this article has helped you enhance your knowledge regarding the subject of the array and minimum increment/decrement.

After reading about the operations of arrays, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. You can learn more about array sorting algorithms, First missing positive , and K largest element. Also, see time complexity and Complexity Analysis.

You can also practice some relevant problems at Coding Ninjas Studio such as:

  1. Sliding Window
  2. Find the Number Occurring Odd Number of Times
  3. Next Permutation
  4. Searching and Sorting in Rotated Sorted Array
     

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

 

Previous article
Move All Negative Elements to the End in Order With Extra Space Allowed
Next article
Largest Number Formed From an Array
Live masterclass