El mayor conjunto de números hasta N tal que está presente i o i/2

Dado un entero positivo N , la tarea es encontrar la longitud del conjunto más grande que se puede generar de manera que si i está presente, entonces i/2 no estará presente y 1<=i<=N .

Nota: Para soluciones múltiples, imprima cualquiera que satisfaga la condición.

Ejemplos:

Entrada: N = 2
Salida: 1
Explicación: Hay dos valores posibles 1 y 2. Si 2 está presente, 1 no puede estar presente ya que 2/2=1. Entonces, solo las posibilidades son 1 o 2. Tanto 1 como 2 por separado pueden ser las respuestas.

Entrada: N = 10
Salida: 1 3 4 5 7 9
Explicación: En la salida, no hay i para los que exista i/2.

Enfoque: Cree un mapa para almacenar y buscar fácilmente y un vector para almacenar el conjunto final. Ejecute un ciclo de 1 a N (digamos i ). Si i es impar, agregue i al vector de respuesta y como una clave en el mapa. De lo contrario, si i es par, busque i/2 como clave en el mapa. Si i/2 está ausente en el mapa, agregue i al vector de respuesta y como clave en el mapa. Siga los pasos a continuación para resolver el problema:

• Inicialice el mapa <int, bool> mp[].
• Inicialice vector<int> ans[] para almacenar el resultado.
• Itere sobre el rango [, N] usando la variable i y realice las siguientes tareas:
  • Si i es impar, introduzca i en el vector ans[] e inserte {i, 1} en el mapa mp[].
  • De lo contrario, si i/2 no existe en el mapa mp[] , inserte i en el vector ans[] e inserte {i, 1} en el mapa mp[].
• Después de realizar los pasos anteriores, imprima los valores del vector ans[] como respuesta.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to get the largest set
vector<int> reqsubarray(int& n)
{
 
    // Initialize the map
    unordered_map<int, bool> mp;
 
    // Vector to store the answer
    vector<int> ans;
    int i;
 
    // Traverse the range
    for (i = 1; i <= n; i++) {
        if (i & 1) {
            ans.push_back(i);
            mp.insert({ i, 1 });
        }
        else if (!mp[i/2]) {
            ans.push_back(i);
            mp.insert({ i, 1 });
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    int n = 10, i;
 
    vector<int> ans;
 
    ans = reqsubarray(n);
 
    for (i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
 
    return 0;
}

// Java program for the above approach
import java.util.ArrayList;
import java.util.HashMap;
 
class GFG
{
 
  // Function to get the largest set
  static ArrayList<Integer> reqsubarray(int n)
  {
 
    // Initialize the map
    HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
 
    // Vector to store the answer
    ArrayList<Integer> ans = new ArrayList<Integer>();
    int i;
 
    // Traverse the range
    for (i = 1; i <= n; i++) {
      if ((i & 1) == 1) {
        ans.add(i);
        mp.put(i, 1);
      }
      else if (!mp.containsKey(i / 2)) {
        ans.add(i);
        mp.put(i, 1);
      }
    }
 
    // Return the answer
    return ans;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int n = 10, i;
 
    ArrayList<Integer> ans = reqsubarray(n);
 
    for (i = 0; i < ans.size(); i++)
      System.out.print(ans.get(i) + " ");
 
  }
}
 
// This code is contributed by Saurabh Jaiswal

# Python 3 program for the above approach
 
# Function to get the largest set
def reqsubarray(n):
 
    # Initialize the map
    mp = {}
 
    # Vector to store the answer
    ans = []
 
    # Traverse the range
    for i in range(1, n + 1):
        if (i & 1):
            ans.append(i)
            mp[i]= 1
 
        elif ((i // 2) not in mp):
            ans.append(i)
            mp[i] = 1
 
    # Return the answer
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    n = 10
 
    ans = reqsubarray(n)
 
    for i in range(len(ans)):
        print(ans[i], end=" ")
 
        # This code is contributed by ukasp.

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to get the largest set
  static ArrayList reqsubarray(int n)
  {
 
    // Initialize the map
    Dictionary<int, int> mp =
      new Dictionary<int, int>();
 
    // Vector to store the answer
    ArrayList ans = new ArrayList();
    int i;
 
    // Traverse the range
    for (i = 1; i <= n; i++) {
      if ((i & 1) == 1) {
        ans.Add(i);
        mp.Add(i, 1);
      }
      else if (!mp.ContainsKey(i / 2)) {
        ans.Add(i);
        mp.Add(i, 1);
      }
    }
 
    // Return the answer
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    int n = 10, i;
 
    ArrayList ans = reqsubarray(n);
 
    for (i = 0; i < ans.Count; i++)
      Console.Write(ans[i] + " ");
 
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to get the largest set
       function reqsubarray(n) {
 
           // Initialize the map
           let mp = new Map();
 
           // Vector to store the answer
           let ans = [];
           let i;
 
           // Traverse the range
           for (i = 1; i <= n; i++) {
               if (i & 1) {
                   ans.push(i);
                   mp.set(i, 1);
               }
               else if (!mp.has(Math.floor(i / 2))) {
                   ans.push(i);
                   mp.set(i, 1);
               }
           }
 
           // Return the answer
           return ans;
       }
 
       // Driver Code
       let n = 10;
       let ans;
       ans = reqsubarray(n);
       for (let i = 0; i < ans.length; i++)
           document.write(ans[i] + " ");
 
 // This code is contributed by Potta Lokesh
   </script>

1 3 4 5 7 9 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)