Given an integer N, the task is to generate an array arr[] having N positive integers such that arr[i] ≠ arr[j] if j is divisible by i (1-based indexing is considered) such that the maximum value of the sequence is minimum among all possible sequences.
Examples:
Input: N = 3
Output: 1 2 2
Explanation: In this sequence 2 is divisible by 1. arr[2] = 2, arr[1] = 1 and arr[2] ≠ arr[1].
In this sequence 3 is divisible by 1. arr[3] = 2, arr[1] = 1 and arr[3] ≠ arr[1].
The maximum value is 2 which is the minimum possible among all sequences.Input: N = 1
Output: 1
Approach: This problem can be solved based on the following idea:
For each index i, the value of arr[i] must be at least same as the number of divisors it has (including the number itself).
Instead of directly finding divisors for each number, one can also find multiples (say j) of each index i. and increment count of divisors of j.
Follow the illustration given below for a better understanding.
Say N = 3.
Create arr[] = {0, 0, 0} to store number of divisors of each value.For i = 1:
=> Multiples of 1 are 1, 2 and 3.
=> Increment values of arr[1], arr[2] and arr[3].
=> So arr[] = {1, 1, 1}For i = 1:
=> Multiples of 2 is 2.
=> Increment value of arr[2].
=> So arr[] = {1, 2, 1}For i = 3:
=> Multiples of 3 is 3.
=> Increment value of arr[3].
=> So arr[] = {1, 2, 2}So the final array is arr = {1, 2, 2} where the maximum value (i.e. 2) is minimum among all possible sequences.
Follow the steps mentioned below to implement the above observation:
- Create an N sized array (say arr[]) with all elements initially filled with 0.
- Use Sieve of Eratosthenes to find all multiples of all numbers from i = 1 to N.
- For this traverse from i = 1 to N:
- Run a loop from j = i to N and increment j by i in each step:
- Increment the value of arr[j] by 1.
- Run a loop from j = i to N and increment j by i in each step:
- Return the final array.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to generate the arrayvector<int> goodSequence(int N){ vector<int> res(N); res[0] = 1; // Loop to implement // sieve of Eratosthenes for (int i = 1; i <= N; i++) { for (int j = 2 * i; j <= N; j += i) res[j - 1] = res[i - 1] + 1; } return res;}// Driver codeint main(){ int N = 3; // Function call vector<int> ans = goodSequence(N); for (int x : ans) cout << x << " "; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to generate the array static int[] goodSequence(int N) { int[] res = new int[N]; res[0] = 1; // Loop to implement // sieve of Eratosthenes for (int i = 1; i <= N; i++) { for (int j = 2 * i; j <= N; j += i) res[j - 1] = res[i - 1] + 1; } return res; } // Driver code public static void main (String[] args) { int N = 3; // Function call int ans[] = goodSequence(N); for (int x = 0; x < ans.length; x++) System.out.print(ans[x] + " "); }}// This code is contributed by hrithikgarg03188. |
Python3
# python3 code to implement the approachimport math# Function to generate the arraydef goodSequence(N): res = [0 for _ in range(N)] res[0] = 1 # Loop to implement # sieve of Eratosthenes for i in range(1, N + 1): for j in range(2*i, N+1, i): res[j - 1] = res[i - 1] + 1 return res# Driver codeif __name__ == "__main__": N = 3 # Function call ans = goodSequence(N) for x in ans: print(x, end=" ") # This code is contributed by rakeshsahni |
C#
// C# code to implement the approachusing System;class GFG { // Function to generate the array static int[] goodSequence(int N) { int[] res = new int[N]; res[0] = 1; // Loop to implement // sieve of Eratosthenes for (int i = 1; i <= N; i++) { for (int j = 2 * i; j <= N; j += i) res[j - 1] = res[i - 1] + 1; } return res; } // Driver code public static void Main() { int N = 3; // Function call int[] ans = goodSequence(N); for (int x = 0; x < ans.Length; x++) Console.Write(ans[x] + " "); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to generate the array function goodSequence(N) { let res = new Array(N); res[0] = 1; // Loop to implement // sieve of Eratosthenes for (let i = 1; i <= N; i++) { for (let j = 2 * i; j <= N; j += i) res[j - 1] = res[i - 1] + 1; } return res; } // Driver code let N = 3; // Function call let ans = goodSequence(N); for (let x of ans) document.write(x + " ") // This code is contributed by Potta Lokesh </script> |
1 2 2
Time Complexity: O(N*log(log(N)))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
