Dada una array arr[] que consta de N enteros positivos distintos, la tarea es imprimir los primeros K Números de Moran distintos de la array dada.
Un número N es un número de Moran si N dividido por la suma de sus dígitos da un número primo .
Ejemplos: 18, 21, 27, 42, 45
Ejemplos:
Entrada: arr[] = {192, 21, 18, 138, 27, 42, 45}, K = 4
Salida: 21, 27, 42, 45
Explicación:
- La suma de dígitos del entero 21 es 2 + 1 = 3. Por lo tanto, dividir 21 por su suma de dígitos = 21 / 3 = 7, que es un número primo.
- La suma de dígitos del entero 27 es 2 + 7 = 9. Por lo tanto, dividir 27 por su suma de dígitos da como resultado 27 / 9 = 3, que es un número primo.
- La suma de dígitos del entero 42 es 4 + 2 = 6. Por lo tanto, dividir 42 por su suma de dígitos da como resultado 42 / 6 = 7, que es un número primo.
- La suma de dígitos del entero 45 es 4 + 5 = 9. Por lo tanto, dividir 45 por su suma de dígitos da como resultado 45 / 9 = 5, que es un número primo.
Entrada: arr[]={127, 186, 198, 63, 27, 91}, K = 3
Salida: 27, 63, 198
Enfoque: siga los pasos que se indican a continuación para resolver el problema:
- Ordenar la array
- Recorra la array ordenada y para cada elemento, verifique si es un número de Moran o no
- Si se encuentra que es cierto, inserte el elemento en un Conjunto e incremente el contador hasta que llegue a K .
- Imprime los elementos del Conjunto cuando el tamaño del conjunto es igual a K .
A continuación se muestra la implementación del enfoque anterior:
C++
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
// Function to calculate the
// sum of digits of a number
int digiSum(int a)
{
// Stores the sum of digits
int sum = 0;
while (a) {
// Add the digit to sum
sum += a % 10;
// Remove digit
a = a / 10;
}
// Returns the sum
// of digits
return sum;
}
// Function to check if a number
// is prime or not
bool isPrime(int r)
{
bool s = true;
for (int i = 2; i * i <= r; i++) {
// If r has any divisor
if (r % i == 0) {
// Set r as non-prime
s = false;
break;
}
}
return s;
}
// Function to check if a
// number is moran number
bool isMorannumber(int n)
{
int dup = n;
// Calculate sum of digits
int sum = digiSum(dup);
// Check if n is divisible
// by the sum of digits
if (n % sum == 0) {
// Calculate the quotient
int c = n / sum;
// If the quotient is prime
if (isPrime(c)) {
return true;
}
}
return false;
}
// Function to print the first K
// Moran numbers from the array
void FirstKMorannumber(int a[],
int n, int k)
{
int X = k;
// Sort the given array
sort(a, a + n);
// Initialise a set
set<int> s;
// Traverse the array from the end
for (int i = n - 1; i >= 0
&& k > 0;
i--) {
// If the current array element
// is a Moran number
if (isMorannumber(a[i])) {
// Insert into the set
s.insert(a[i]);
k--;
}
}
if (k > 0) {
cout << X << " Moran numbers are"
<< " not present in the array" << endl;
return;
}
set<int>::iterator it;
for (it = s.begin(); it != s.end(); ++it) {
cout << *it << ", ";
}
cout << endl;
}
// Driver Code
int main()
{
int A[] = { 34, 198, 21, 42,
63, 45, 22, 44, 43 };
int K = 4;
int N = sizeof(A) / sizeof(A[0]);
FirstKMorannumber(A, N, K);
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG{
// Function to calculate the
// sum of digits of a number
static int digiSum(int a)
{
// Stores the sum of digits
int sum = 0;
while (a != 0)
{
// Add the digit to sum
sum += a % 10;
// Remove digit
a = a / 10;
}
// Returns the sum
// of digits
return sum;
}
// Function to check if a number
// is prime or not
static boolean isPrime(int r)
{
boolean s = true;
for(int i = 2; i * i <= r; i++)
{
// If r has any divisor
if (r % i == 0)
{
// Set r as non-prime
s = false;
break;
}
}
return s;
}
// Function to check if a
// number is moran number
static boolean isMorannumber(int n)
{
int dup = n;
// Calculate sum of digits
int sum = digiSum(dup);
// Check if n is divisible
// by the sum of digits
if (n % sum == 0)
{
// Calculate the quotient
int c = n / sum;
// If the quotient is prime
if (isPrime(c))
{
return true;
}
}
return false;
}
// Function to print the first K
// Moran numbers from the array
static void FirstKMorannumber(int[] a,
int n, int k)
{
int X = k;
// Sort the given array
Arrays.sort(a);
// Initialise a set
TreeSet<Integer> s = new TreeSet<Integer>();
// Traverse the array from the end
for(int i = n - 1; i >= 0 && k > 0; i--)
{
// If the current array element
// is a Moran number
if (isMorannumber(a[i]))
{
// Insert into the set
s.add(a[i]);
k--;
}
}
if (k > 0)
{
System.out.println(X + " Moran numbers are" +
" not present in the array");
return;
}
for(int value : s)
System.out.print(value + ", ");
System.out.print("\n");
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 34, 198, 21, 42,
63, 45, 22, 44, 43 };
int K = 4;
int N = A.length;
FirstKMorannumber(A, N, K);
}
}
// This code is contributed by akhilsaini
Python3
import math # Function to calculate the # sum of digits of a number def digiSum(a): # Stores the sum of digits sums = 0 while (a != 0): # Add the digit to sum sums += a % 10 # Remove digit a = a // 10 # Returns the sum # of digits return sums # Function to check if a number # is prime or not def isPrime(r): s = True for i in range(2, int(math.sqrt(r)) + 1): # If r has any divisor if (r % i == 0): # Set r as non-prime s = False break return s # Function to check if a # number is moran number def isMorannumber(n): dup = n # Calculate sum of digits sums = digiSum(dup) # Check if n is divisible # by the sum of digits if (n % sums == 0): # Calculate the quotient c = n // sums # If the quotient is prime if isPrime(c): return True return False # Function to print the first K # Moran numbers from the array def FirstKMorannumber(a, n, k): X = k # Sort the given array a.sort() # Initialise a set s = set() # Traverse the array from the end for i in range(n - 1, -1, -1): if (k <= 0): break # If the current array element # is a Moran number if (isMorannumber(a[i])): # Insert into the set s.add(a[i]) k -= 1 if (k > 0): print(X, end =' Moran numbers are not ' 'present in the array') return lists = sorted(s) for i in lists: print(i, end = ', ') # Driver Code if __name__ == '__main__': A = [ 34, 198, 21, 42, 63, 45, 22, 44, 43 ] K = 4 N = len(A) FirstKMorannumber(A, N, K) # This code is contributed by akhilsaini
C#
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to calculate the
// sum of digits of a number
static int digiSum(int a)
{
// Stores the sum of digits
int sum = 0;
while (a != 0)
{
// Add the digit to sum
sum += a % 10;
// Remove digit
a = a / 10;
}
// Returns the sum
// of digits
return sum;
}
// Function to check if a number
// is prime or not
static bool isPrime(int r)
{
bool s = true;
for(int i = 2; i * i <= r; i++)
{
// If r has any divisor
if (r % i == 0)
{
// Set r as non-prime
s = false;
break;
}
}
return s;
}
// Function to check if a
// number is moran number
static bool isMorannumber(int n)
{
int dup = n;
// Calculate sum of digits
int sum = digiSum(dup);
// Check if n is divisible
// by the sum of digits
if (n % sum == 0)
{
// Calculate the quotient
int c = n / sum;
// If the quotient is prime
if (isPrime(c))
{
return true;
}
}
return false;
}
// Function to print the first K
// Moran numbers from the array
static void FirstKMorannumber(int[] a,
int n, int k)
{
int X = k;
// Sort the given array
Array.Sort(a);
// Initialise a set
SortedSet<int> s = new SortedSet<int>();
// Traverse the array from the end
for(int i = n - 1; i >= 0 && k > 0; i--)
{
// If the current array element
// is a Moran number
if (isMorannumber(a[i]))
{
// Insert into the set
s.Add(a[i]);
k--;
}
}
if (k > 0)
{
Console.WriteLine(X + " Moran numbers are" +
" not present in the array");
return;
}
foreach(var val in s)
{
Console.Write(val + ", ");
}
Console.Write("\n");
}
// Driver Code
public static void Main()
{
int[] A = { 34, 198, 21, 42,
63, 45, 22, 44, 43 };
int K = 4;
int N = A.Length;
FirstKMorannumber(A, N, K);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Function to calculate the
// sum of digits of a number
function digiSum(a)
{
// Stores the sum of digits
let sum = 0;
while (a) {
// Add the digit to sum
sum += a % 10;
// Remove digit
a = Math.floor(a / 10);
}
// Returns the sum
// of digits
return sum;
}
// Function to check if a number
// is prime or not
function isPrime(r)
{
let s = true;
for (let i = 2; i * i <= r; i++) {
// If r has any divisor
if (r % i == 0) {
// Set r as non-prime
s = false;
break;
}
}
return s;
}
// Function to check if a
// number is moran number
function isMorannumber(n)
{
let dup = n;
// Calculate sum of digits
let sum = digiSum(dup);
// Check if n is divisible
// by the sum of digits
if (n % sum == 0) {
// Calculate the quotient
let c = n / sum;
// If the quotient is prime
if (isPrime(c)) {
return true;
}
}
return false;
}
// Function to print the first K
// Moran numbers from the array
function FirstKMorannumber(a, n, k)
{
let X = k;
// Sort the given array
a = a.sort((x, y) => x - y)
// Initialise a set
let s = new Set();
// Traverse the array from the end
for (let i = n - 1; i >= 0
&& k > 0;
i--) {
// If the current array element
// is a Moran number
if (isMorannumber(a[i])) {
// Insert into the set
s.add(a[i]);
k--;
}
}
if (k > 0) {
document.write(X + " Moran numbers are"
+ " not present in the array" + "<br>");
return;
}
// Convert the set into array and then sort the array
s = [...s].sort((a, b) => a - b)
for (let it of s) {
document.write(it + ", ");
}
document.write("<br>");
}
// Driver Code
let A = [ 34, 198, 21, 42,
63, 45, 22, 44, 43 ];
let K = 4;
let N = A.length;
FirstKMorannumber(A, N, K);
// This code is contributed by gfgking
</script>
Producción:
42, 45, 63, 198,
Complejidad temporal: O(N 3/2 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por crisscross y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA