Given an array nums[] of size N, the task is to check whether the given array can be converted into a permutation of 1 to N after performing given operations any number of times (may be 0). An operation is defined as: Pick any element of the array say ‘x’, and replace it with ‘x/2’.
Note: In a permutation of 1 to N all the numbers in range [1, N] are present in any order and each number is present only once.
Examples:
Input: N = 4, nums[] = {1, 8, 25, 2}
Output: true
Explanation: Sequence of operations followed are listed below:
Replace 8 with 8/2 = 4, nums[] = {1, 4, 25, 2}
Replace 25 with 25/2 = 12, nums[] = {1, 4, 12, 2}
Replace 12 with 12/2 = 6, nums[] = {1, 4, 6, 2}
Replace 6 with 6/2 = 3, nums[] = {1, 4, 3, 2} (Here element from 1 to 4 is present exactly once)Input: N = 4, nums[] = {24, 7, 16, 7}
Output: false
Approach: The solution to the problem is based on sorting. Create an array freq of type boolean and size (N+1) to keep track of the numbers of the desired permutation. Follow the below steps:
- Sort the given array.
- Traverse from the back of the array and at each step:
- If val is less than N and freq[val] is false then mark it as true.
- If val is greater than N or freq[val] is true then divide it by 2 while (val > 0 && freq[val] == true)
- At last, check if the desired permutation is achieved or not.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to check is it possible// to make array or notbool possibleOrNot(vector<int>& nums, int N){ // Sorting array sort(nums.begin(), nums.end()); // Initializing freq[] array which // keeps track of elements from 1 to N vector<bool> freq(N + 1, 0); // Iterating from backwards for (int i = N - 1; i >= 0; i--) { int val = nums[i]; // Dividing val by 2 while // it is greater than N // or freq[val] is true while (val > N || (freq[val] && val >= 1)) { val /= 2; } // Updating freq array if (val != 0) freq[val] = true; } // Checking if every element from // 1 to N is present or not for (int i = 1; i < freq.size(); i++) if (!freq[i]) { return false; } return true;}// Driver Codeint main(){ int N = 4; vector<int> nums = { 1, 8, 25, 2 }; bool ans = possibleOrNot(nums, N); cout << (ans); return 0;} // This code is contributed by rakeshsahni |
Java
// Java code to implement the above approachimport java.util.*;class GFG { // Driver Code public static void main(String[] args) { int N = 4; int[] nums = { 1, 8, 25, 2 }; boolean ans = possibleOrNot(nums, N); System.out.println(ans); } // Function to check is it possible // to make array or not public static boolean possibleOrNot(int[] nums, int N) { // Sorting array Arrays.sort(nums); // Initializing freq[] array which // keeps track of elements from 1 to N boolean[] freq = new boolean[N + 1]; // Iterating from backwards for (int i = N - 1; i >= 0; i--) { int val = nums[i]; // Dividing val by 2 while // it is greater than N // or freq[val] is true while (val > N || (freq[val] && val >= 1)) { val /= 2; } // Updating freq array if (val != 0) freq[val] = true; } // Checking if every element from // 1 to N is present or not for (int i = 1; i < freq.length; i++) if (!freq[i]) { return false; } return true; }} |
Python3
# python3 code to implement the above approach# Function to check is it possible# to make array or notdef possibleOrNot(nums, N): # Sorting array nums.sort() # Initializing freq[] array which # keeps track of elements from 1 to N freq = [0 for _ in range(N + 1)] # Iterating from backwards for i in range(N - 1, -1, -1): val = nums[i] # Dividing val by 2 while # it is greater than N # or freq[val] is true while (val > N or (freq[val] and val >= 1)): val //= 2 # Updating freq array if (val != 0): freq[val] = True # Checking if every element from # 1 to N is present or not for i in range(1, len(freq)): if (not freq[i]): return False return True# Driver Codeif __name__ == "__main__": N = 4 nums = [1, 8, 25, 2] ans = possibleOrNot(nums, N) print(ans) # This code is contributed by rakeshsahni |
C#
using System;public class GFG{ // Function to check is it possible // to make array or not static bool possibleOrNot(int[] nums, int N) { // Sorting array Array.Sort(nums); // Initializing freq[] array which // keeps track of elements from 1 to N bool[] freq = new bool[N + 1]; // Iterating from backwards for (int i = N - 1; i >= 0; i--) { int val = nums[i]; // Dividing val by 2 while // it is greater than N // or freq[val] is true while (val > N || (freq[val] && val >= 1)) { val /= 2; } // Updating freq array if (val != 0) freq[val] = true; } // Checking if every element from // 1 to N is present or not for (int i = 1; i < freq.Length; i++) if (!freq[i]) { return false; } return true; } // Driver Code static public void Main (){ int N = 4; int[] nums = { 1, 8, 25, 2 }; bool ans = possibleOrNot(nums, N); if(ans == true) Console.WriteLine(1); else Console.WriteLine(0); }}// This code is contributed by hrithikgrg03188. |
Javascript
<script>// Javascript code to implement the above approach// Function to check is it possible// to make array or notfunction possibleOrNot(nums, N){ // Sorting array nums.sort((a, b) => a - b); // Initializing freq[] array which // keeps track of elements from 1 to N let freq = new Array(N + 1).fill(0) // Iterating from backwards for (let i = N - 1; i >= 0; i--) { let val = nums[i]; // Dividing val by 2 while // it is greater than N // or freq[val] is true while (val > N || (freq[val] && val >= 1)) { val = Math.floor(val / 2); } // Updating freq array if (val != 0) freq[val] = true; } // Checking if every element from // 1 to N is present or not for (let i = 1; i < freq.length; i++) if (!freq[i]) { return false; } return true;}// Driver Codelet N = 4;let nums = [1, 8, 25, 2]let ans = possibleOrNot(nums, N);document.write(ans);// This code is contributed by saurabh_jaiswal.</script> |
Output
true
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments