Find a sequence of distinct integers whose Harmonic Mean is N
Given an integer N, the task is to find a sequence of distinct integers whose Harmonic Mean is N itself. In case such a sequence doesn’t exist, print -1.
Examples:
Input: N = 5
Output: {3, 4, 5, 6, 20}
Explanation: Given sequence is the correct answer because 5/(1/3+1/4+1/5+1/6+1/20)=5. Note that there are other possible sequences as well. For example – {2, 6, 12, 20, 5}.Input: N=3
Output: {2, 3, 6}
Approach: To solve the problem follow the below observations:
Observations:
- For N = 1, the sequence {1} satisfies the conditions.
- For N = 2, there is no possible sequence satisfying the given conditions. So, we’ll consider the case for N > 2.
- We know that 1/X(X+1) = 1/X – 1/(X+1). Using this fact, we can see that the sequence {1*2, 2*3, …, (N-1)*N, N} would satisfy the required conditions. (Reason: {1*2, 2*3, …, (N-1)*N, N} = {2, 6, 12, 20…..(N-1)*N, N}.
- The harmonic mean of this sequence:
- N/(1/(1*2) + 1/(2*3) + 1/(3*4) +…+ 1/(N-1)*N) + 1/N)
- N/(1-1/2 + 1/2-1/3 + 1/3-1/4) +…+ 1/(N-1)-1/N + 1/N)
- N/1 = N
- However, for the cases when N can be represented as N=X*(X-1), for some integer X, it can be seen that the above observation fails as the sequence would contain a duplicate.
For example, for N=6 (6=2*3), the sequence would be {2, 6, 12, 20, 30, 6}. Here 6 is repeated, but we want all distinct integers in the sequence.
- Suppose the sequence from observation 1 is {A1, A2, A3….AN}. To avoid repeating numbers when N is even (as N = X*(X-1) will be possible only when N is even), we’ll print the sequence {2, 2*A1, 2*A2,….,2*A(N-2), 2*(N-1)}.
The following steps can be used to solve the problem :
- For N = 1, print 1.
- For N = 2, print -1.
- For odd N, print the sequence {1*2, 2*3, …, (N-1)*N, N}.
- For even N, print the sequence {2, 2*(1*2, 2*3, …, (N-2)(N-1), N-1}.
Following is the code based on the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to find a sequence of // distinct integers whose // Harmonic Mean is N void printSequence( int N) { // Sequence is not possible for N=2 if (N == 2) { cout << -1; return ; } // For N=1, the sequence is {1} itself if (N == 1) { cout << 1; return ; } // If N is odd if (N % 2) { // Sequence would be // 1*2, 2*3,...,(N-1)*N, N for ( int i = 1; i <= N - 1; i++) { cout << i * (i + 1) << " "; } cout << N << "\n"; } // If N is even else { // Sequence would be // 2, 2*(1*2, 2*3,...,(N-2)(N-1), N-1) cout << 2 << " "; for ( int i = 1; i <= N - 2; i++) { cout << 2 * i * (i + 1) << " "; } cout << 2 * (N - 1) << "\n"; } } // Driver Code int main() { int N = 5; // Function Call printSequence(N); } |
Java
// Java Implementation import java.util.*; public class GFG { // Function to find a sequence of // distinct integers whose // Harmonic Mean is N static void printSequence( int N) { // Sequence is not possible for N=2 if (N == 2 ) { System.out.println(- 1 ); return ; } // For N=1, the sequence is {1} itself if (N == 1 ) { System.out.println( 1 ); return ; } // If N is odd if (N % 2 != 0 ) { // Sequence would be // 1*2, 2*3,...,(N-1)*N, N for ( int i = 1 ; i <= N - 1 ; i++) { System.out.print(i * (i + 1 ) + " " ); } System.out.println(N); } // If N is even else { // Sequence would be // 2, 2*(1*2, 2*3,...,(N-2)(N-1), N-1) System.out.print( 2 + " " ); for ( int i = 1 ; i <= N - 2 ; i++) { System.out.print( 2 * i * (i + 1 ) + " " ); } System.out.println( 2 * (N - 1 )); } } // Driver Code public static void main(String[] args) { int N = 5 ; // Function Call printSequence(N); } } //this code is contributed by uttamdp_10 |
Python3
#Python Implementation # Function to find a sequence of # distinct integers whose # Harmonic Mean is N def print_sequence(N): # Sequence is not possible for N=2 if N = = 2 : print ( - 1 ) return # For N=1, the sequence is {1} itself if N = = 1 : print ( 1 ) return # If N is odd if N % 2 ! = 0 : # Sequence would be # 1*2, 2*3,...,(N-1)*N, N for i in range ( 1 , N): print (i * (i + 1 ), end = " " ) print (N) # If N is even else : # Sequence would be # 2, 2*(1*2, 2*3,...,(N-2)(N-1), N-1) print ( 2 , end = " " ) for i in range ( 1 , N - 1 ): print ( 2 * i * (i + 1 ), end = " " ) print ( 2 * (N - 1 )) # Driver Code if __name__ = = "__main__" : N = 5 # Function Call print_sequence(N) # this code is contributed by uttamdp_10 |
C#
// C# code for the above approach using System; public class GFG { // Function to find a sequence of // distinct integers whose // Harmonic Mean is N static void PrintSequence( int N) { // Sequence is not possible for N=2 if (N == 2) { Console.WriteLine(-1); return ; } // For N=1, the sequence is {1} itself if (N == 1) { Console.WriteLine(1); return ; } // If N is odd if (N % 2 != 0) { // Sequence would be // 1*2, 2*3,...,(N-1)*N, N for ( int i = 1; i <= N - 1; i++) { Console.Write(i * (i + 1) + " " ); } Console.WriteLine(N); } // If N is even else { // Sequence would be // 2, 2*(1*2, 2*3,...,(N-2)(N-1), N-1) Console.Write(2 + " " ); for ( int i = 1; i <= N - 2; i++) { Console.Write(2 * i * (i + 1) + " " ); } Console.WriteLine(2 * (N - 1)); } } // Driver Code static public void Main() { int N = 5; // Function Call PrintSequence(N); } } |
Javascript
// JavaScript code for the above approach // Function to find a sequence of // distinct integers whose // Harmonic Mean is N function printSequence(N) { // Sequence is not possible for N=2 if (N === 2) { console.log(-1); return ; } // For N=1, the sequence is [1] itself if (N === 1) { console.log(1); return ; } // If N is odd if (N % 2) { // Sequence would be // 1*2, 2*3,...,(N-1)*N, N for (let i = 1; i <= N - 1; i++) { process.stdout.write(i * (i + 1) + " " ); } console.log(N); } // If N is even else { // Sequence would be // 2, 2*(1*2, 2*3,...,(N-2)(N-1), N-1) process.stdout.write(2 + " " ); for (let i = 1; i <= N - 2; i++) { process.stdout.write(2 * i * (i + 1) + " " ); } console.log(2 * (N - 1)); } } // Driver Code const N = 5; // Function Call printSequence(N); // This code is contributed by prasad264 |
2 6 12 20 5
Time Complexity: O(N)
Auxiliary Space: O(1)