Dada una array nums[] de tamaño N , la tarea es verificar si la array dada se puede convertir en una permutación de 1 a N después de realizar las operaciones dadas cualquier cantidad de veces (puede ser 0). Una operación se define como: Elija cualquier elemento de la array, digamos ‘x’ , y reemplácelo con ‘x/2’ .
Nota: En una permutación de 1 a N , todos los números en el rango [1, N] están presentes en cualquier orden y cada número está presente solo una vez.
Ejemplos:
Entrada: N = 4, nums[] = {1, 8, 25, 2}
Salida: verdadero
Explicación: La secuencia de operaciones seguidas se enumera a continuación:
Reemplace 8 con 8/2 = 4, nums[] = {1, 4, 25, 2}
Reemplazar 25 con 25/2 = 12, nums[] = {1, 4, 12, 2}
Reemplazar 12 con 12/2 = 6, nums[] = {1, 4, 6, 2}
Reemplazar 6 con 6/2 = 3, nums[] = {1, 4, 3, 2} (Aquí el elemento del 1 al 4 está presente exactamente una vez)Entrada: N = 4, nums[] = {24, 7, 16, 7}
Salida: falso
Planteamiento: La solución al problema se basa en la clasificación . Cree una frecuencia de array de tipo booleano y tamaño (N+1) para realizar un seguimiento de los números de la permutación deseada. Siga los pasos a continuación:
- Ordenar la array dada.
- Traverse desde la parte posterior de la array y en cada paso:
- Si val es menor que N y freq[val] es falso , márquelo como verdadero.
- Si val es mayor que N o freq[val] es verdadero , entonces divídalo por 2 while (val > 0 && freq[val] == verdadero)
- Por último, compruebe si se consigue o no la permutación deseada.
A continuación se muestra la implementación del enfoque anterior:
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 not
bool 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 Code
int 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 approach
import 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 not def 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 Code if __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 not
function 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 Code
let N = 4;
let nums = [1, 8, 25, 2]
let ans = possibleOrNot(nums, N);
document.write(ans);
// This code is contributed by saurabh_jaiswal.
</script>
true
Complejidad de tiempo : O(N * log(N))
Espacio auxiliar : O(N)