Dada una array de longitud N que contiene solo números enteros, la tarea es imprimir los números especiales de la array. Un número en esta array se llama Número especial si es divisible por al menos otro número en la array.
Ejemplos:
Entrada: 1 2 3
Salida: 2 3
Explicación: tanto 2 como 3 son divisibles por 1.
Entrada: 2 3 4 6 8 9
Salida: 4 6 8 9
Explicación: 2 y 3 no son divisibles por ningún otro elemento. El resto del elemento es divisible por al menos 1 elemento. 6 es divisible por 2 y 3, 4 divisible por 2, 8 divisible por 2 y 4 ambos, 9 divisible por 3.
Entrada: 3 5 7 11
Salida:
Explicación: todos los elementos son primos relativos, por lo que no hay un número especial.
Una solución simple es atravesar todos los elementos, luego verificar cada elemento si es divisible por cualquier otro. La complejidad temporal de esta solución es O(n 2 )
Otra solución que funciona mejor cuando hay muchos elementos con valores no muy grandes. Almacene todos los elementos de la array en hash y descubra el elemento máximo en la array, luego, hasta el elemento máximo, descubra los múltiplos de un número dado, luego, si el múltiplo del elemento de la array está en hash, ese número es divisible por al menos un elemento de la array . Para eliminar valores duplicados, almacenamos el valor en el conjunto porque si la array tiene 2, 3 y 6, solo 6 es divisible por al menos un elemento de la array, tanto 2 como 3 dividen 6, por lo que 6 se almacenará solo una vez.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find special numbers
void divisibilityCheck(int arr[], int n)
{
// Storing all array elements in a hash
// and finding maximum element in the array
unordered_set<int> s;
int max_ele = INT_MIN;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
// Update the maximum element of the array
max_ele = max(max_ele, arr[i]);
}
// Traversing the array elements and storing the array
// multiples that are present in s in res
unordered_set<int> res;
for (int i = 0; i < n; i++) {
// Check for non-zero values only
if (arr[i] != 0) {
// Checking the factors of current element
for (int j = arr[i] * 2; j <= max_ele; j += arr[i]) {
// If current factor is already part
// of the array then store it
if (s.find(j) != s.end())
res.insert(j);
}
}
}
// For non-distinct elmments
// To store the frequency of elements
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
mp[arr[i]]++;
unordered_map<int, int>::iterator it;
vector<int> ans;
for (it = mp.begin(); it != mp.end(); it++) {
// If frequency is at least 2
if (it->second >= 2) {
if (res.find(it->first) == res.end()) {
// If frequency is greater than 1 and
// the number is not divisible by
// any other number
int val = it->second;
// Then we push the element number of
// times it is present in the vector
while (val--)
ans.push_back(it->first);
}
}
// If frequency is greater than 1 and the number
// is divisible by any other number
if (res.find(it->first) != res.end()) {
int val = it->second;
// Then we push the element number of
// times it is present in the vector
while (val--)
ans.push_back(it->first);
}
}
// Print the elements that are divisible by
// at least one other element from the array
for (auto x : ans)
cout << x << " ";
}
// Driver code
int main()
{
int arr[] = { 2, 3, 8, 6, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
divisibilityCheck(arr, n);
return 0;
}
Java
// Java program to find special
// numbers in an array
import java.io.*;
import java.util.*;
class GFG {
// Function to find
// special numbers
static void divisibilityCheck(List<Integer> arr,
int n)
{
// Storing all array elements
// in a hash and finding maximum
// element in array
List<Integer> s = new ArrayList<Integer>();
int max_ele = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
s.add(arr.get(i));
// finding maximum
// element of array
max_ele = Math.max(max_ele,
arr.get(i));
}
// traversing array element and
// storing the array multiples
// that are present in s in res.
LinkedHashSet<Integer> res = new LinkedHashSet<Integer>();
for (int i = 0; i < n; i++) {
// Check for non-zero values only
if (arr.get(i) != 0)
// checking the factor
// of current element
for (int j = arr.get(i) * 2;
j <= max_ele;
j += arr.get(i)) {
// if factor is already
// part of array element
// then store it
if (s.contains(j))
res.add(j);
}
}
// displaying elements that
// are divisible by at least
// one other in array
List<Integer> list = new ArrayList<Integer>(res);
Collections.reverse(list);
for (Integer temp : list)
System.out.print(temp + " ");
}
// Driver Code
public static void main(String args[])
{
List<Integer> arr = Arrays.asList(2, 3, 8, 6, 9, 10);
int n = arr.size();
divisibilityCheck(arr, n);
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python3 program to find special numbers # in an array import math as mt # Function to find special numbers def divisibilityCheck(arr, n): # Storing all array elements in a hash # and finding maximum element in array s = dict() max_ele = -10**9 for i in range(n): s[arr[i]] = 1 # finding maximum element of array max_ele = max(max_ele, arr[i]) # traversing array element and storing # the array multiples that are present # in s in res. res = dict() for i in range(n): # Check for non-zero values only if (arr[i] != 0): # checking the factor of current element for j in range(arr[i] * 2, max_ele + 1, arr[i]): # if factor is already part of # array element then store it if (j in s.keys()): res[j] = 1 # displaying elements that are divisible # by at least one other in array for x in res: print(x, end = " ") # Driver code arr = [ 2, 3, 8, 6, 9, 10] n = len(arr) divisibilityCheck(arr, n) # This code is contributed by # Mohit Kumar 29
C#
// C# program to find special
// numbers in an array
using System;
using System.Linq;
using System.Collections.Generic;
class GFG {
// Function to find
// special numbers
static void divisibilityCheck(List<int> arr,
int n)
{
// Storing all array elements
// in a hash and finding maximum
// element in array
List<int> s = new List<int>();
int max_ele = Int32.MinValue;
for (int i = 0; i < n; i++) {
s.Add(arr[i]);
// finding maximum element of array
max_ele = Math.Max(max_ele,
arr[i]);
}
// traversing array element and
// storing the array multiples
// that are present in s in res.
HashSet<int> res = new HashSet<int>();
for (int i = 0; i < n; i++) {
// Check for non-zero values only
if (arr[i] != 0)
// checking the factor
// of current element
for (int j = arr[i] * 2; j <= max_ele;
j += arr[i]) {
// if factor is already part
// of array element then store it
if (s.Contains(j))
res.Add(j);
}
}
// displaying elements that
// are divisible by at least
// one other in array
foreach(int i in res.Reverse())
Console.Write(i + " ");
}
// Driver Code
static void Main()
{
List<int> arr = new List<int>() { 2, 3, 8,
6, 9, 10 };
int n = arr.Count;
divisibilityCheck(arr, n);
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Javascript
<script>
// JavaScript implementation of the approach
// Function to find special numbers
function divisibilityCheck(arr, n) {
// Storing all array elements in a hash
// and finding maximum element in the array
let s = new Set();
let max_ele = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < n; i++) {
s.add(arr[i]);
// Update the maximum element of the array
max_ele = Math.max(max_ele, arr[i]);
}
// Traversing the array elements and storing the array
// multiples that are present in s in res
let res = new Set();
for (let i = 0; i < n; i++) {
// Check for non-zero values only
if (arr[i] != 0) {
// Checking the factors of current element
for (let j = arr[i] * 2; j <= max_ele; j += arr[i]) {
// If current factor is already part
// of the array then store it
if (s.has(j))
res.add(j);
}
}
}
// For non-distinct elmments
// To store the frequency of elements
let mp = new Map();
for (let i = 0; i < n; i++) {
if (mp.has(arr[i])) {
mp.set(arr[i], mp.get(arr[i]) + 1)
} else {
mp.set(arr[i], 1)
}
}
let ans = [];
for (let it of mp) {
// If frequency is at least 2
if (it[1] >= 2) {
if (res.has(it[0])) {
// If frequency is greater than 1 and
// the number is not divisible by
// any other number
let val = it[1];
// Then we push the element number of
// times it is present in the vector
while (val--)
ans.push(it[0]);
}
}
// If frequency is greater than 1 and the number
// is divisible by any other number
if (res.has(it[0])) {
let val = it[1];
// Then we push the element number of
// times it is present in the vector
while (val--)
ans.push(it[0]);
}
}
// Print the elements that are divisible by
// at least one other element from the array
for (let x of ans.sort((a, b) => a - b))
document.write(x + " ");
}
// Driver code
let arr = [2, 3, 8, 6, 9, 10];
let n = arr.length
divisibilityCheck(arr, n);
</script>
6 8 9 10
Complejidad de tiempo: O(nxm), donde n es el tamaño de la array y m es el elemento máximo en la array
Espacio auxiliar: O(n)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Nota: si necesitamos que los resultados se impriman en orden, podemos usar set en lugar de unordered_set .
Publicación traducida automáticamente
Artículo escrito por Asif_jafri y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA