Checks whether the given array can form a permutation from 1 to N by halving the elements

Our goal is to determine whether performing multiple divisions on each item contained in the array creates a list of integers from 1 to N without any duplicates. The success of this effort will mean that our investigative goals have been successfully achieved. Essentially, determining whether cutting all elements provided in a given array by two would result in a permutation consisting entirely of non-repeating values ​​between 1 and N is the main focus of our work. Once confirmed, evaluating our paper would be the next logical step.

grammar

Before delving into our proposed solution, it is important to have a rough understanding of the syntax of the method we are about to implement.

bool canBePermutation(vector<int>& arr)
{
   // Implementation goes here
}
</int>

algorithm

To solve this problem, let’s proceed step by step using the algorithm outlined below -

• To pay close attention to the observed components in an array, start by starting a collection or hash set. Then, iterate over each element present in that array.

• To get an integer between 1 and N, each element needs to be divided by 2 multiple times.

• Check whether the result value already exists in the collection. If so, returns false because there cannot be duplicates in the arrangement.

• In order for the array to be a valid arrangement, each element must meet the above conditions. Assuming this criterion is fully met, confirming its eligibility by providing a true return value can be considered an appropriate course of action.

method

In order to effectively solve this problem. It may be helpful to explore different strategies. I will suggest two possible approaches -

Method 1: Set-based method

Creating an efficient approach requires the use of meticulous techniques, such as implementing a tracking system using collections created to record the components encountered throughout the process. It involves iteratively evaluating each component through a division process, ensuring that its resulting value falls between 1 and N range values, then checking our trace set for validation before appending the newly observed item, and then returning if there are any anomalies false, otherwise returns true once all values ​​have passed the evaluation checks required by Constellation.

Example

#include <iostream>
#include <vector>
#include <unordered_set>

bool canBePermutation(std::vector<int>& arr) {
   std::unordered_set<int> seen;
   
   for (int num : arr) {
      while (num > 0 && num != 1) {
         if (seen.find(num) != seen.end())
            return false;
         
         seen.insert(num);
         num /= 2;
      }
      
      if (num == 0)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

Output

The given array cannot be transformed into a permutation.

illustrate

The initial steps of method 1 involve setting up an unordered set to keep track of the elements present in the array. This coding method then continues to iterate through each element in the same array, dividing them by 2 each time, repeatedly reducing them to an integer between 1 and N. During these iterations, a check is made to see if an item that appears to have been created has already been created in the same collection; thereby trying to avoid duplicate permutations simply due to duplication. When a duplicate resulting from these repeating permutations is detected, false is returned, as when everything is checked without a duplicate being completed - passed as true - effectively indicating whether the given set can be moved into its respective permutation , while minimizing its components by halving them.

Method 2: Sorting method

Ascending sorting helps detect whether each array item can present itself as a matching value in the sorted list. If none of the items meet this criterion, our output will produce false; however, if all items pass this test, it will return true.

Example

#include <iostream>
#include <vector>
#include <algorithm>

bool canBePermutation(std::vector<int>& arr) {
   std::sort(arr.begin(), arr.end());

   for (int i = 0; i < arr.size(); i++) {
      int expected = i + 1;
      while (arr[i] > 0 && arr[i] != expected)
         arr[i] /= 2;

      if (arr[i] != expected)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

Output

The given array can be transformed into a permutation.

illustrate

According to method 2 (sorting method), we first sort the original input array in ascending order before further checking the code routine. The code then runs various iterations on each individual element of the above array while checking whether they are divisible by two until they reach a specified and assumed value established based on their position within the newly sorted range of index value positions. If there are any cases in such an iteration that do not meet these predefined key conditions, then our code describes the result as "False", which means that it is not possible to convert this array into the corresponding sequential arrangement. At the same time, conversely, each compliant element produces a "true" result, providing a feasible positive direction for our array reorganization goals.

in conclusion

In this article, we delve into the challenge of verifying whether a given array can be transformed into a permutation containing numbers in the range 1 to N by halving its elements. We provide the reader with the outline, syntax, and algorithmic procedures for efficiently solving this problem. Additionally, we provide two possible approaches along with complete C executable code examples. By applying the set-based techniques or sorting strategies highlighted in this article, the reader can determine to his or her satisfaction whether any given array meets all the necessary conditions for a legal arrangement.

The above is the detailed content of Checks whether the given array can form a permutation from 1 to N by halving the elements. For more information, please follow other related articles on the PHP Chinese website!