Dada una array de enteros positivos. Ordene la array dada en orden decreciente del número de factores de cada elemento, es decir, el elemento que tiene el mayor número de factores debe ser el primero en mostrarse y el número que tiene el menor número de factores debe ser el último. Dos elementos con el mismo número de factores deben estar en el mismo orden que en la array original.
Ejemplos:
Input : {5, 11, 10, 20, 9, 16, 23}
Output : 20 16 10 9 5 11 23
Number of distinct factors:
For 20 = 6, 16 = 5, 10 = 4, 9 = 3
and for 5, 11, 23 = 2 (same number of factors
therefore sorted in increasing order of index)
Input : {104, 210, 315, 166, 441, 180}
Output : 180 210 315 441 104 166
Los siguientes pasos ordenan los números en orden decreciente de conteo de factores.
- Cuente un número distinto de factores de cada elemento. Consulte esto .
- Puede usar una estructura para cada elemento para almacenar su índice original y el recuento de factores. Cree una array de tales estructuras para almacenar dicha información para todos los elementos.
- Ordene esta array de estructuras sobre la base de la declaración del problema utilizando cualquier algoritmo de clasificación.
- Recorra esta array de estructuras desde el principio y obtenga el número de la array original con la ayuda del índice almacenado en la estructura de cada elemento de la array ordenada de estructuras.
C++
// C++ implementation to sort numbers on
// the basis of factors
#include <bits/stdc++.h>
using namespace std;
// structure of each element having its index
// in the input array and number of factors
struct element
{
int index, no_of_fact;
};
// function to count factors for
// a given number n
int countFactors(int n)
{
int count = 0;
int sq = sqrt(n);
// if the number is a perfect square
if (sq * sq == n)
count++;
// count all other factors
for (int i=1; i<sqrt(n); i++)
{
// if i is a factor then n/i will be
// another factor. So increment by 2
if (n % i == 0)
count += 2;
}
return count;
}
// comparison function for the elements
// of the structure
bool compare(struct element e1, struct element e2)
{
// if two elements have the same number
// of factors then sort them in increasing
// order of their index in the input array
if (e1.no_of_fact == e2.no_of_fact)
return e1.index < e2.index;
// sort in decreasing order of number of factors
return e1.no_of_fact > e2.no_of_fact;
}
// function to print numbers after sorting them in
// decreasing order of number of factors
void printOnBasisOfFactors(int arr[], int n)
{
struct element num[n];
// for each element of input array create a
// structure element to store its index and
// factors count
for (int i=0; i<n; i++)
{
num[i].index = i;
num[i].no_of_fact = countFactors(arr[i]);
}
// sort the array of structures as defined
sort(num, num+n, compare);
// access index from the structure element and corresponding
// to that index access the element from arr
for (int i=0; i<n; i++)
cout << arr[num[i].index] << " ";
}
// Driver program to test above
int main()
{
int arr[] = {5, 11, 10, 20, 9, 16, 23};
int n = sizeof(arr) / sizeof(arr[0]);
printOnBasisOfFactors(arr, n);
return 0;
}
Java
// Java implementation to sort numbers on
// the basis of factors
import java.util.Arrays;
import java.util.Comparator;
class Element
{
//each element having its index
// in the input array and number of factors
int index, no_of_fact;
public Element(int i, int countFactors)
{
index = i;
no_of_fact = countFactors;
}
// method to count factors for
// a given number n
static int countFactors(int n)
{
int count = 0;
int sq = (int)Math.sqrt(n);
// if the number is a perfect square
if (sq * sq == n)
count++;
// count all other factors
for (int i=1; i<Math.sqrt(n); i++)
{
// if i is a factor then n/i will be
// another factor. So increment by 2
if (n % i == 0)
count += 2;
}
return count;
}
// function to print numbers after sorting them in
// decreasing order of number of factors
static void printOnBasisOfFactors(int arr[], int n)
{
Element num[] = new Element[n];
// for each element of input array create a
// structure element to store its index and
// factors count
for (int i=0; i<n; i++)
{
num[i] = new Element(i,countFactors(arr[i]));
}
// sort the array of structures as defined
Arrays.sort(num,new Comparator<Element>() {
@Override
// compare method for the elements
// of the structure
public int compare(Element e1, Element e2) {
// if two elements have the same number
// of factors then sort them in increasing
// order of their index in the input array
if (e1.no_of_fact == e2.no_of_fact)
return e1.index < e2.index ? -1 : 1;
// sort in decreasing order of number of factors
return e1.no_of_fact > e2.no_of_fact ? -1 : 1;
}
});
// access index from the structure element and corresponding
// to that index access the element from arr
for (int i=0; i<n; i++)
System.out.print(arr[num[i].index]+" ");
}
// Driver program to test above
public static void main(String[] args)
{
int arr[] = {5, 11, 10, 20, 9, 16, 23};
printOnBasisOfFactors(arr, arr.length);
}
}
// This code is contributed by Gaurav Miglani
Javascript
<script>
// Javascript implementation to sort numbers on
// the basis of factors
// each element having its index
// in the input array and number of factors
class Element {
constructor(i, countFactors) {
this.index = i;
this.no_of_fact = countFactors;
}
}
// method to count factors for
// a given number n
function countFactors(n) {
let count = 0;
let sq = Math.floor(Math.sqrt(n));
// if the number is a perfect square
if (sq * sq == n)
count++;
// count all other factors
for (let i = 1; i < Math.sqrt(n); i++) {
// if i is a factor then n/i will be
// another factor. So increment by 2
if (n % i == 0)
count += 2;
}
return count;
}
// function to print numbers after sorting them in
// decreasing order of number of factors
function printOnBasisOfFactors(arr, n) {
let num = new Array(n);
// for each element of input array create a
// structure element to store its index and
// factors count
for (let i = 0; i < n; i++) {
num[i] = new Element(i, countFactors(arr[i]));
}
// sort the array of structures as defined
num.sort((e1, e2) => {
// if two elements have the same number
// of factors then sort them in increasing
// order of their index in the input array
if (e1.no_of_fact == e2.no_of_fact)
return e1.index < e2.index ? -1 : 1;
// sort in decreasing order of number of factors
return e1.no_of_fact > e2.no_of_fact ? -1 : 1;
})
// access index from the structure element and corresponding
// to that index access the element from arr
for (let i = 0; i < n; i++)
document.write(arr[num[i].index] + " ");
}
// Driver program to test above
let arr = [5, 11, 10, 20, 9, 16, 23];
printOnBasisOfFactors(arr, arr.length);
// This code is contributed by gfgking
</script>
Producción:
20 16 10 9 5 11 23
Complejidad de tiempo: O(n √n)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA