Monday, June 27, 2022
HomeSoftware DevelopmentDepend quantity in given vary generated by concatenating two Array components

# Depend quantity in given vary generated by concatenating two Array components

Given an array arr[] of size N and integers L and R defining the given range, the task is to find the number of elements in the given range that can be generated by concatenating any two elements of the array.

Examples:

Input:  N = 2, L = 10, R = 52, arr = {2, 5}
Output:  3
Explanation: All pairs available
(2, 2) => 22 (10 ≤ 22 ≤ 52)
(2, 5) => 25 (10 ≤ 25 ≤ 52)
(5, 2) => 52 (10 ≤ 52 ≤ 52)
(5, 5) => 55 (10 ≤ 55 > 52) invalid
Hence output is 3.

Input:  N = 3, L = 100, R = 1000, arr = {28, 5, 100}
Output:  2
Explanation: The only valid pairs available
(28, 5) => 285 (100 ≤ 285 ≤ 1000)
(5, 28) => 528 (100 ≤ 528 ≤ 1000)
Rest other pairs either fall short or higher then given range
Hence output is 2.

Approach: The idea to solve the problem is based on the following observation:

Observations:

• The length of the valid pair is crucial as it can help us to distinguish right pairs.
• If length is permissible we need to check whether every element is in the boundary or not.
• Similarily

Follow the below steps to implement the above approach:

• First sort the given array.
• Find the length of the first element of the pair
• For any pair {x, y}, x * 10len(y) + y gives the value of “xy” when they are concatenated.
• Then, simply iterate j from 1 to N
• Use the above condition to find the range where the other value (say x) will lie.
• Use binary search to find how many possible array elements are there in the range which can assume the value x.
• Increment the count by that much.
• The final count is the required answer.

Below is the implementation for the above approach:

## C++

 ` `  `#include ` `using` `namespace` `std;` ` `  `int` `ValidPair(``int` `a[], ``int` `n, ``int` `l, ``int` `r)` `{` `    ` `    ``sort(a, a + n);` ` `  `    ` `    ` `    ``vector<``int``> pow10(17, 1);` `    ``for` `(``int` `i = 1; i <= 16; i++) {` `        ``pow10[i] = pow10[i - 1] * 10;` `    ``}` ` `  `    ``int` `ans = 0;` `    ``for` `(``int` `j = 0; j < n; j++) {` ` `  `        ` `        ``int` `len = 0;` `        ``int` `cur = a[j];` `        ``while` `(cur) {` `            ``cur /= 10;` `            ``len++;` `        ``}` ` `  `        ` `        ``int` `right = (r - a[j]) / pow10[len];` `        ``int` `left = (l - a[j] + pow10[len] - 1) / pow10[len];` ` `  `        ` `        ` `        ``if` `(left <= right)` `            ``ans += (upper_bound(a, a + n, right)` `                    ``- lower_bound(a, a + n, left));` `    ``}` `    ``return` `ans;` `}` ` `  `int` `main()` `{` `    ``int` `N = 2;` `    ``int` `L = 10, R = 52;` `    ``int` `arr[2] = { 2, 5 };` `    ``cout << ValidPair(arr, N, L, R) << endl;` `    ``return` `0;` `}`

Time Complexity: O(N * logN)
Auxiliary Space: O(1)

RELATED ARTICLES