Recuento de elementos a la izquierda que son divisibles por el elemento actual – Part 1

Dado un arreglo A[] de N enteros, la tarea es generar un arreglo B[] tal que B[i] contenga el conteo de índices j en A[] tal que j < i y A[j] % A[i ] = 0
Ejemplos: 
 

Entrada: arr[] = {3, 5, 1} 
Salida: 0 0 2 
3 y 5 no dividen ningún elemento a 
su izquierda pero 1 divide 3 y 5.
Entrada: arr[] = {8, 1, 28, 4 , 2, 6, 7} 
Salida: 0 1 0 2 3 0 1 
 

Enfoque: ejecute un ciclo desde el primer elemento hasta el último elemento de la array y, para el elemento actual, ejecute otro ciclo para los elementos a su izquierda y verifique cuántos elementos a su izquierda son divisibles por él.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to print the
// elements of the array
void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// Function to generate and print
// the required array
void generateArr(int A[], int n)
{
    int B[n];
 
    // For every element of the array
    for (int i = 0; i < n; i++) {
 
        // To store the count of elements
        // on the left that the current
        // element divides
        int cnt = 0;
        for (int j = 0; j < i; j++) {
            if (A[j] % A[i] == 0)
                cnt++;
        }
        B[i] = cnt;
    }
 
    // Print the generated array
    printArr(B, n);
}
 
// Driver code
int main()
{
    int A[] = { 3, 5, 1 };
    int n = sizeof(A) / sizeof(A[0]);
 
    generateArr(A, n);
 
    return 0;
}

// Java implementation of above approach
class GFG
{
 
// Utility function to print the
// elements of the array
static void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        System.out.print(arr[i] + " ");
}
 
// Function to generate and print
// the required array
static void generateArr(int A[], int n)
{
    int []B = new int[n];
 
    // For every element of the array
    for (int i = 0; i < n; i++)
    {
 
        // To store the count of elements
        // on the left that the current
        // element divides
        int cnt = 0;
        for (int j = 0; j < i; j++)
        {
            if (A[j] % A[i] == 0)
                cnt++;
        }
        B[i] = cnt;
    }
 
    // Print the generated array
    printArr(B, n);
}
 
// Driver code
public static void main(String args[])
{
    int A[] = { 3, 5, 1 };
    int n = A.length;
 
    generateArr(A, n);
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
 
# Utility function to print the
# elements of the array
def printArr(arr, n):
 
    for i in arr:
        print(i, end = " ")
 
# Function to generate and print
# the required array
def generateArr(A, n):
    B = [0 for i in range(n)]
 
    # For every element of the array
    for i in range(n):
 
        # To store the count of elements
        # on the left that the current
        # element divides
        cnt = 0
        for j in range(i):
            if (A[j] % A[i] == 0):
                cnt += 1
 
        B[i] = cnt
 
    # Print the generated array
    printArr(B, n)
 
# Driver code
A = [3, 5, 1]
n = len(A)
 
generateArr(A, n)
 
# This code is contributed by Mohit Kumar

// C# implementation of above approach
using System;
     
class GFG
{
 
// Utility function to print the
// elements of the array
static void printArr(int []arr, int n)
{
    for (int i = 0; i < n; i++)
        Console.Write(arr[i] + " ");
}
 
// Function to generate and print
// the required array
static void generateArr(int []A, int n)
{
    int []B = new int[n];
 
    // For every element of the array
    for (int i = 0; i < n; i++)
    {
 
        // To store the count of elements
        // on the left that the current
        // element divides
        int cnt = 0;
        for (int j = 0; j < i; j++)
        {
            if (A[j] % A[i] == 0)
                cnt++;
        }
        B[i] = cnt;
    }
 
    // Print the generated array
    printArr(B, n);
}
 
// Driver code
public static void Main(String []args)
{
    int []A = { 3, 5, 1 };
    int n = A.Length;
 
    generateArr(A, n);
}
}
 
// This code is contributed by Rajput-Ji

<script>
// Javascript implementation of the approach
 
// Utility function to print the
// elements of the array
function printArr(arr, n)
{
    for (let i = 0; i < n; i++)
        document.write(arr[i] + " ");
}
 
// Function to generate and print
// the required array
function generateArr(A, n)
{
    let B = new Array(n);
 
    // For every element of the array
    for (let i = 0; i < n; i++) {
 
        // To store the count of elements
        // on the left that the current
        // element divides
        let cnt = 0;
        for (let j = 0; j < i; j++) {
            if (A[j] % A[i] == 0)
                cnt++;
        }
        B[i] = cnt;
    }
 
    // Print the generated array
    printArr(B, n);
}
 
// Driver code
    let A = [ 3, 5, 1 ];
    let n = A.length;
 
    generateArr(A, n);
 
</script>

0 0 2

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(n)