Given a positive integer N, the task is to find the length of largest set that can be generated such that if i is present, then i/2 will not be present and 1<=i<=N.
Note: For multiple solutions, print anyone satisfying the condition.
Examples:
Input: N = 2
Output: 1
Explanation: There are two possible values 1 and 2. If 2 is present, 1 can not be present since 2/2=1. So only possibilities are 1 or 2. Both 1 and 2 separately can be the answers.Input: N = 10
Output: 1 3 4 5 7 9
Explanation: In the output, there are no i for which i/2 exists.
Approach: Create a map for easy storing and searching and a vector to store the final set. Run a loop from 1 to N (say i) If i is odd then add i to the answer vector and as a key in the map. Else if i is even, search i/2 as key in the map. If i/2 is absent in the map then add i to the answer vector and as a key in the map. Follow the steps below to solve the problem:
- Initialize the map<int, bool> mp[].
- Initialize the vector<int> ans[] to store the result.
- Iterate over the range [, N] using the variable i and perform the following tasks:
- If i is odd, then push i into the vector ans[] and insert {i, 1} into the map mp[].
- Else if i/2 does not exist in the map mp[] then push i into the vector ans[] and insert {i, 1} into the map mp[].
- After performing the above steps, print the values of the vector ans[] as the answer.
Below is the implementation of the above approach.
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to get the largest setvector<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 Codeint main(){ int n = 10, i; vector<int> ans; ans = reqsubarray(n); for (i = 0; i < ans.size(); i++) cout << ans[i] << " "; return 0;} |
Java
// Java program for the above approachimport 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 |
Python3
# Python 3 program for the above approach# Function to get the largest setdef 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 Codeif __name__ == "__main__": n = 10 ans = reqsubarray(n) for i in range(len(ans)): print(ans[i], end=" ") # This code is contributed by ukasp. |
C#
// C# program for the above approachusing 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. |
Javascript
<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
Time Complexity: O(N)
Auxiliary Space: O(N)
