Dada una array A[] que consta de N números que denotan los valores escritos en N pasos, la tarea es encontrar la puntuación alfa del viaje total de subir todas las escaleras. Dado que la respuesta puede ser muy grande, imprima la respuesta módulo 10 9 + 7 .
Puntuación alfa: la puntuación alfa en cada escalón es la suma de todos los números vistos anteriormente en los escalones subidos que son más pequeños que el número en el escalón actual.
La puntuación alfa del viaje total es la suma de las puntuaciones alfa de cada paso.
Ejemplos:
Entrada: A[] = {13, 14, 20}
Salida: 87
Explicación:
Puntuación alfa en el primer escalón = 13
Puntuación alfa en el segundo escalón = 13 + 14 = 27
Puntuación alfa en el tercer escalón = 13 + 14 + 20 = 47
Suma de todos los puntajes alfa = 13 + 27 + 47 = 87
Por lo tanto, el puntaje alfa del viaje total es 87.Entrada: A[] = {10, 11, 12}
Salida: 64
Explicación:
Puntuación alfa en el primer escalón = 10
Puntuación alfa en el segundo escalón = 10 + 11 = 21
Puntuación alfa en el tercer escalón = 10+11 + 12 = 33
Suma de todos los puntajes alfa = 10 + 21 + 33
Por lo tanto, el puntaje alfa del viaje total es 64.
Enfoque ingenuo:
el enfoque más simple para resolver el problema es recorrer cada elemento de la array y calcular la suma de todos los elementos más pequeños que el elemento actual presente en los índices anteriores para calcular la puntuación alfa de la escalera actual . Para cada suma calculada, actualice el total_sum ( puntuación alfa del viaje total ). Finalmente, imprima el total_sum como el Alpha Score del viaje completo.
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(1)
Enfoque eficiente:
el enfoque anterior se puede optimizar utilizando árboles de búsqueda binarios . Siga los pasos a continuación:
- Ordenar la array dada.
- Construya un BST a partir de la array ordenada .
- Atraviese recursivamente el BST y siga los pasos a continuación:
- Atraviesa el subárbol izquierdo.
- Agregue el valor del Node actual a la suma ( puntuación alfa para la escalera actual ) y actualice total_sum ( puntuación alfa del viaje hasta ahora ).
- Atraviesa el subárbol derecho.
- Después de completar el recorrido del BST, imprima total_sum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
static long sum = 0, total_sum = 0;
static long mod = 1000000007;
// Structure of a node
struct Node
{
Node *left, *right;
int data;
Node(int x)
{
data = x;
left = NULL;
right = NULL;
}
};
// Function to calculate and return
// the Alpha Score of the journey
long getAlphaScore(Node* node)
{
// Traverse left subtree
if (node->left != NULL)
getAlphaScore(node->left);
// Calculate the alpha score
// of the current step
sum = (sum + node->data) % mod;
// Update alpha score of
// the journey
total_sum = (total_sum + sum) % mod;
// Traverse right subtree
if (node->right != NULL)
getAlphaScore(node->right);
// Return
return total_sum;
}
// Function to construct a BST
// from the sorted array arr[]
Node* constructBST(int arr[], int start,
int end, Node* root)
{
if (start > end)
return NULL;
int mid = (start + end) / 2;
// Insert root
if (root == NULL)
root = new Node(arr[mid]);
// Construct left subtree
root->left = constructBST(arr, start,
mid - 1, root->left);
// Construct right subtree
root->right = constructBST(arr, mid + 1, end,
root->right);
// Return root
return root;
}
// Driver Code
int main()
{
int arr[] = { 10, 11, 12 };
int length = 3;
// Sort the array
sort(arr, arr + length);
Node *root = NULL;
// Construct BST from the sorted array
root = constructBST(arr, 0, length - 1, root);
cout << (getAlphaScore(root));
}
// This code is contributed by mohit kumar 29
Java
// Java Program to implement
// the above approach
import java.lang.*;
import java.util.*;
// Structure of a node
class Node {
Node left, right;
int data;
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}
class AlphaScore {
Node root;
AlphaScore() { root = null; }
static long sum = 0, total_sum = 0;
static long mod = 1000000007;
// Function to calculate and return
// the Alpha Score of the journey
public static long getAlphaScore(Node node)
{
// Traverse left subtree
if (node.left != null)
getAlphaScore(node.left);
// Calculate the alpha score
// of the current step
sum = (sum + node.data) % mod;
// Update alpha score of
// the journey
total_sum = (total_sum + sum) % mod;
// Traverse right subtree
if (node.right != null)
getAlphaScore(node.right);
// Return
return total_sum;
}
// Function to construct a BST
// from the sorted array arr[]
public static Node constructBST(int[] arr, int start,
int end, Node root)
{
if (start > end)
return null;
int mid = (start + end) / 2;
// Insert root
if (root == null)
root = new Node(arr[mid]);
// Construct left subtree
root.left
= constructBST(arr, start, mid - 1, root.left);
// Construct right subtree
root.right
= constructBST(arr, mid + 1, end, root.right);
// Return root
return root;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 10, 11, 12 };
int length = arr.length;
// Sort the array
Arrays.sort(arr);
Node root = null;
// Construct BST from the sorted array
root = constructBST(arr, 0, length - 1, root);
System.out.println(getAlphaScore(root));
}
}
Python3
# Python3 program to implement # the above approach # Structure of a node class Node: def __init__(self, data): self.data = data self.left = None self.right = None sum = 0 total_sum = 0 mod = 1000000007 # Function to calculate and return # the Alpha Score of the journey def getAlphaScore(node): global sum global total_sum # Traverse left subtree if node.left != None: getAlphaScore(node.left) # Calculate the alpha score # of the current step sum = (sum + node.data) % mod # Update alpha score of # the journey total_sum = (total_sum + sum) % mod # Traverse right subtree if node.right != None: getAlphaScore(node.right) # Return return total_sum # Function to construct a BST # from the sorted array arr[] def constructBST(arr, start, end, root): if start > end: return None mid = (start + end) // 2 # Insert root if root == None: root = Node(arr[mid]) # Construct left subtree root.left = constructBST(arr, start, mid - 1, root.left) # Construct right subtree root.right = constructBST(arr, mid + 1, end, root.right) # Return root return root # Driver code arr = [ 10, 11, 12 ] length = len(arr) # Sort the array arr.sort() root = None # Construct BST from the sorted array root = constructBST(arr, 0, length - 1, root) print(getAlphaScore(root)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
// Structure of a node
class Node
{
public Node left, right;
public int data;
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}
class AlphaScore{
Node root;
AlphaScore(){root = null;}
static long sum = 0, total_sum = 0;
static long mod = 1000000007;
// Function to calculate and return
// the Alpha Score of the journey
static long getAlphaScore(Node node)
{
// Traverse left subtree
if (node.left != null)
getAlphaScore(node.left);
// Calculate the alpha score
// of the current step
sum = (sum + node.data) % mod;
// Update alpha score of
// the journey
total_sum = (total_sum + sum) % mod;
// Traverse right subtree
if (node.right != null)
getAlphaScore(node.right);
// Return
return total_sum;
}
// Function to construct a BST
// from the sorted array []arr
static Node constructBST(int[] arr, int start,
int end, Node root)
{
if (start > end)
return null;
int mid = (start + end) / 2;
// Insert root
if (root == null)
root = new Node(arr[mid]);
// Construct left subtree
root.left = constructBST(arr, start,
mid - 1, root.left);
// Construct right subtree
root.right = constructBST(arr, mid + 1,
end, root.right);
// Return root
return root;
}
// Driver Code
public static void Main(String []args)
{
int []arr = { 10, 11, 12 };
int length = arr.Length;
// Sort the array
Array.Sort(arr);
Node root = null;
// Construct BST from the sorted array
root = constructBST(arr, 0, length - 1, root);
Console.WriteLine(getAlphaScore(root));
}
}
// This is code contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to implement
// the above approach
// Structure of a node
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
var root = null;
function AlphaScore(){root = null;}
var sum = 0, total_sum = 0;
var mod = 1000000007;
// Function to calculate and return
// the Alpha Score of the journey
function getAlphaScore(node)
{
// Traverse left subtree
if (node.left != null)
getAlphaScore(node.left);
// Calculate the alpha score
// of the current step
sum = (sum + node.data) % mod;
// Update alpha score of
// the journey
total_sum = (total_sum + sum) % mod;
// Traverse right subtree
if (node.right != null)
getAlphaScore(node.right);
// Return
return total_sum;
}
// Function to construct a BST
// from the sorted array []arr
function constructBST(arr, start, end, root)
{
if (start > end)
return null;
var mid = parseInt((start + end) / 2);
// Insert root
if (root == null)
root = new Node(arr[mid]);
// Construct left subtree
root.left = constructBST(arr, start,
mid - 1, root.left);
// Construct right subtree
root.right = constructBST(arr, mid + 1,
end, root.right);
// Return root
return root;
}
// Driver Code
var arr = [10, 11, 12];
var length = arr.length;
// Sort the array
arr.sort();
var root = null;
// Construct BST from the sorted array
root = constructBST(arr, 0, length - 1, root);
document.write(getAlphaScore(root));
// This code is contributed by rrrtnx.
</script>
64
Complejidad temporal: O(NlogN)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por MugdhaBehere y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA