Given a positive integer n, check if it is an Ore number or not. Print ‘YES’ if n is an ore number otherwise print ‘NO’.
Ore Number: In mathematics, Ore numbers are positive integers whose divisors have an integer harmonic value. Ore numbers are often called harmonic divisor numbers. Ore numbers are named after Øystein Ore.
For example, 6 has four divisors namely 1, 2, 3, and 6.
The harmonic mean of the divisors is-
The harmonic mean of divisors of 6 is 2, an integer. So, 6 is an Ore number or harmonic divisor number.
First, a few Ore numbers or harmonic divisor numbers are:
1, 6, 28, 140, 270, 496, 672, 1638, 2970, 6200, 8128, 8190
Examples:
Input : N = 6
Output : Yes
Input : N = 4
Output: No
Explanation : Harmonic mean of divisors of 4
is not an Integer.
Prerequisite:
The idea is to generate all divisors of the given number and then check if the harmonic mean of the divisor is an Integer or not.
- Generate All Divisors of the given number – ‘n’
- Calculate the Harmonic mean of the divisors of n
- Check if the Harmonic mean is an Integer or not
- If Yes, Then the number is an Ore Number otherwise Not
Below is the implementation of the above approach:
C++
// CPP program to check if the given number is// Ore number#include <bits/stdc++.h>using namespace std;vector<int> arr;// Function that returns harmonic meanvoid generateDivisors(int n){ // Note that this loop runs till square root for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, store 'i' if (n / i == i) arr.push_back(i); else // Otherwise store 'i' and 'n/i' both { arr.push_back(i); arr.push_back(n / i); } } }}// Utility function to calculate harmonic// mean of the divisorsdouble harmonicMean(int n){ generateDivisors(n); // Declare sum variables and initialize // with zero. double sum = 0.0; int len = arr.size(); // calculate denominator for (int i = 0; i < len; i++) sum = sum + double(n / arr[i]); sum = double(sum / n); // Calculate harmonic mean and return return double(arr.size() / sum);}// Function to check if a number is ore numberbool isOreNumber(int n){ // Calculate Harmonic mean of divisors of n double mean = harmonicMean(n); // Check if harmonic mean is an integer or not if (mean - int(mean) == 0) return true; else return false;}// Driver Codeint main(){ int n = 28; if (isOreNumber(n)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// Java program to check if the given// number is Ore numberimport java.util.*;class GFG { static Vector<Integer> arr = new Vector<Integer>(); // Function that returns harmonic mean. static void generateDivisors(int n) { // Note that this loop runs till square root for (int i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, store 'i' if (n / i == i) arr.add(i); else // Otherwise store 'i' and 'n/i' both { arr.add(i); arr.add(n / i); } } } } // Utility function to calculate harmonic mean // of the divisors static double harmonicMean(int n) { generateDivisors(n); // Declare sum variables and initialize // with zero. double sum = 0.0; int len = arr.size(); // calculate denominator for (int i = 0; i < len; i++) sum = sum + n / arr.get(i); sum = sum / n; // Calculate harmonic mean and return return arr.size() / sum; } // Function to check if a number // is Ore number static boolean isOreNumber(int n) { // Calculate Harmonic mean of divisors of n double mean = harmonicMean(n); // Check if Harmonic mean is an Integer or not if (mean - Math.floor(mean) == 0) return true; else return false; } // Driver Code public static void main(String[] args) { int n = 28; if (isOreNumber(n)) System.out.println("YES"); else System.out.println("NO"); }} |
Python3
# Python3 program to check if the # given number is Ore number arr = [] # Function that returns harmonic mean def generateDivisors(n): # Note that this loop runs till square root for i in range(1, int(n**(0.5)) + 1): if n % i == 0: # If divisors are equal, store 'i' if n // i == i: arr.append(i) # Otherwise store 'i' and 'n/i' both else: arr.append(i) arr.append(n // i) # Utility function to calculate harmonic # mean of the divisors def harmonicMean(n): generateDivisors(n) # Declare sum variables and initialize # with zero. Sum = 0 length = len(arr) # calculate denominator for i in range(0, length): Sum = Sum + (n / arr[i]) Sum = Sum / n # Calculate harmonic mean and return return length / Sum# Function to check if a number# is ore number def isOreNumber(n): # Calculate Harmonic mean of # divisors of n mean = harmonicMean(n) # Check if harmonic mean is an # integer or not if mean - int(mean) == 0: return True else: return False# Driver Code if __name__ == "__main__": n = 28 if isOreNumber(n) == True: print("YES") else: print("NO") # This code is contributed# by Rituraj Jain |
C#
// C# program to check if the given// number is Ore numberusing System;using System.Collections;class GFG {static ArrayList arr = new ArrayList();// Function that returns harmonic mean.static void generateDivisors(int n){ // Note that this loop runs // till square root for (int i = 1; i <= Math.Sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // store 'i' if (n / i == i) arr.Add(i); else // Otherwise store 'i' // and 'n/i' both { arr.Add(i); arr.Add(n / i); } } }}// Utility function to calculate // harmonic mean of the divisorsstatic double harmonicMean(int n){ generateDivisors(n); // Declare sum variables and // initialize with zero. double sum = 0.0; int len = arr.Count; // calculate denominator for (int i = 0; i < len; i++) sum = sum + n / (int)arr[i]; sum = sum / n; // Calculate harmonic mean // and return return arr.Count / sum;}// Function to check if a number// is Ore numberstatic bool isOreNumber(int n){ // Calculate Harmonic mean of // divisors of n double mean = harmonicMean(n); // Check if Harmonic mean is // an Integer or not if (mean - Math.Floor(mean) == 0) return true; else return false;}// Driver Codepublic static void Main(){ int n = 28; if (isOreNumber(n)) Console.WriteLine("YES"); else Console.WriteLine("NO");}}// This code is contributed by mits |
Javascript
<script>// Javascript program to check// if the given number is// Ore numbervar arr = [];// Function that returns harmonic meanfunction generateDivisors(n){ // Note that this loop runs till square root for (var i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, store 'i' if (n / i == i) arr.push(i); else // Otherwise store 'i' and 'n/i' both { arr.push(i); arr.push(n / i); } } }}// Utility function to calculate harmonic// mean of the divisorsfunction harmonicMean(n){ generateDivisors(n); // Declare sum variables and initialize // with zero. var sum = 0.0; var len = arr.length; // calculate denominator for (var i = 0; i < len; i++) sum = sum + (n / arr[i]); sum = (sum / n); // Calculate harmonic mean and return return (arr.length / sum);}// Function to check if a number is ore numberfunction isOreNumber(n){ // Calculate Harmonic mean of divisors of n var mean = harmonicMean(n); // Check if harmonic mean is an integer or not if (mean - parseInt(mean) == 0) return true; else return false;}// Driver Codevar n = 28;if (isOreNumber(n)) document.write( "YES");else document.write( "NO");</script> |
Output
YES
Time Complexity: O(sqrt(n)), Where n is the given number.
Auxiliary Space: O(sqrt(n)), for storing the divisor of n in the array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
