Dado un arreglo circular arr[] de N enteros y dos enteros M y K , la tarea es encontrar la suma de los elementos del arreglo arr[] después de realizar M operaciones tales que en cada operación, incremente los elementos del arreglo adyacentes de todos los elementos positivos del arreglo. por K , es decir, si arr[i] > 0 , entonces incremente el valor de arr[i – 1] y arr[i + 1] por K .
Ejemplos:
Entrada: arr[] = {0, 1, 0, 1, 0, 0}, M = 2, K = 1
Salida: 16
Explicación:
En la primera operación después de incrementar los elementos de array adyacentes de arr[] > 0, el la array dada se modifica a arr[] = {1, 1, 2, 1, 1, 0}.
En la segunda operación después de incrementar los elementos de array adyacentes de arr[] > 0, la array dada se modifica a arr[] = {2, 3, 4, 3, 2, 2}. Entonces la suma de todos los elementos de arr[] es 16.Entrada: arr[] = {1, 2, 3}, M = 10, K = 2
Salida: 126
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Cualquier elemento distinto de cero siempre aumentará la suma de la array en 2 * K en un solo movimiento.
- El número de movimientos necesarios para incrementar un número entero de 0 a un valor distinto de cero siempre es igual a la distancia del elemento distinto de cero más cercano.
Siga los pasos a continuación para resolver el problema:
- Cree una array steps[] , que almacene la distancia del elemento actual desde el elemento distinto de cero más cercano.
- Cree una función más cercana a la izquierda() para encontrar el índice del elemento distinto de cero más cercano mientras recorre la array en la dirección izquierda utilizando el enfoque que se describe en este artículo .
- De manera similar, cree una función más cercana a la derecha() para encontrar el índice del elemento distinto de cero más cercano mientras recorre la array en la dirección correcta.
- El número de operaciones requeridas para incrementar el valor del i -ésimo elemento desde 0 viene dado por pasos[i] y después de eso, contribuirá 2 * K a la suma final después de cada operación. Por lo tanto, la contribución total del i -ésimo entero en la suma final después de M operaciones es 2 * K * (M – pasos[i]) .
- Recorra la array arr[] en el rango [1, N] y realice un seguimiento de la suma aportada por cada índice en una variable, digamos sum .
- Después de completar los pasos anteriores, imprima el valor de sum como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the nearest non-zero
// element in the left direction
void nearestLeft(int arr[], int N,
vector<int>& steps)
{
// Stores the index of the first element
// greater than 0 from the right side
int L = -N;
// Traverse the array in the range [1, N]
for (int i = N - 1; i >= 0; i--) {
// Check arr[i] is greater than 0
if (arr[i] > 0) {
// Update the value of L
L = -(N - i);
break;
}
}
// Traverse the array from the left side
for (int i = 0; i < N; i++) {
// Check arr[i] is greater than 0
if (arr[i] > 0) {
// Update the value of L
L = i;
}
// Update the value of steps[i]
steps[i] = i - L;
}
}
// Function to find the nearest non-zero
// element in the right direction
void nearestRight(int arr[], int N,
vector<int>& steps)
{
// Stores the index of the first element
// greater than 0 from the left side
int R = 2 * N;
// Traverse the array from the left side
for (int i = 0; i < N; i++) {
// Check arr[i] is greater than 0
if (arr[i] > 0) {
// Update the value of R
R = N + i;
break;
}
}
// Traverse the array from the right side
for (int i = N - 1; i >= 0; i--) {
// Check arr[i] is greater than 0
if (arr[i] > 0) {
// Update the value of R
R = i;
}
// Update the value of steps[i]
steps[i] = min(steps[i], R - i);
}
}
// Function to find the sum of the array
// after the given operation M times
int findSum(int arr[], int N, int M, int K)
{
// Stores the distance of the nearest
// non zero element.
vector<int> steps(N);
// Stores sum of the initial array arr[]
int sum = accumulate(arr, arr + N, 0);
if (sum == 0) {
return 0;
}
nearestLeft(arr, N, steps);
nearestRight(arr, N, steps);
// Traverse the array from the left side
for (int i = 0; i < N; i++)
// Update the value of sum
sum += 2 * K * max(0, M - steps[i]);
// Print the total sum of the array
return sum;
}
// Driver Code
int main()
{
int arr[] = { 0, 1, 0, 1, 0, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
int M = 2;
int K = 1;
cout << findSum(arr, N, M, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the nearest non-zero
// element in the left direction
static void nearestLeft(int arr[], int N,
int[] steps)
{
// Stores the index of the first element
// greater than 0 from the right side
int L = -N;
// Traverse the array in the range [1, N]
for (int i = N - 1; i >= 0; i--)
{
// Check arr[i] is greater than 0
if (arr[i] > 0)
{
// Update the value of L
L = -(N - i);
break;
}
}
// Traverse the array from the left side
for (int i = 0; i < N; i++)
{
// Check arr[i] is greater than 0
if (arr[i] > 0)
{
// Update the value of L
L = i;
}
// Update the value of steps[i]
steps[i] = i - L;
}
}
// Function to find the nearest non-zero
// element in the right direction
static void nearestRight(int arr[], int N,
int[] steps)
{
// Stores the index of the first element
// greater than 0 from the left side
int R = 2 * N;
// Traverse the array from the left side
for (int i = 0; i < N; i++) {
// Check arr[i] is greater than 0
if (arr[i] > 0) {
// Update the value of R
R = N + i;
break;
}
}
// Traverse the array from the right side
for (int i = N - 1; i >= 0; i--)
{
// Check arr[i] is greater than 0
if (arr[i] > 0)
{
// Update the value of R
R = i;
}
// Update the value of steps[i]
steps[i] = Math.min(steps[i], R - i);
}
}
static int accumulate(int[] arr, int start, int end){
int sum = 0;
for(int i= 0; i < arr.length; i++)
sum += arr[i];
return sum;
}
// Function to find the sum of the array
// after the given operation M times
static int findSum(int arr[], int N, int M, int K)
{
// Stores the distance of the nearest
// non zero element.
int []steps = new int[N];
// Stores sum of the initial array arr[]
int sum = accumulate(arr, 0, N);
if (sum == 0) {
return 0;
}
nearestLeft(arr, N, steps);
nearestRight(arr, N, steps);
// Traverse the array from the left side
for (int i = 0; i < N; i++)
// Update the value of sum
sum += 2 * K * Math.max(0, M - steps[i]);
// Print the total sum of the array
return sum;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 0, 1, 0, 1, 0, 0 };
int N = arr.length;
int M = 2;
int K = 1;
System.out.print(findSum(arr, N, M, K));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to find the nearest non-zero # element in the left direction def nearestLeft(arr, N, steps): # Stores the index of the first element # greater than 0 from the right side L = -N # Traverse the array in the range [1, N] for i in range(N - 1, -1, -1): # Check arr[i] is greater than 0 if (arr[i] > 0): # Update the value of L L = -(N - i) break # Traverse the array from the left side for i in range(N): # Check arr[i] is greater than 0 if (arr[i] > 0): # Update the value of L L = i # Update the value of steps[i] steps[i] = i - L # Function to find the nearest non-zero # element in the right direction def nearestRight(arr, N, steps): # Stores the index of the first element # greater than 0 from the left side R = 2 * N # Traverse the array from the left side for i in range(N): # Check arr[i] is greater than 0 if (arr[i] > 0): # Update the value of R R = N + i break # Traverse the array from the right side for i in range(N - 1, -1, -1): # Check arr[i] is greater than 0 if (arr[i] > 0): # Update the value of R R = i # Update the value of steps[i] steps[i] = min(steps[i], R - i) # Function to find the sum of the array # after the given operation M times def findSum(arr, N, M, K): # Stores the distance of the nearest # non zero element. steps = [0] * N # Stores sum of the initial array arr[] s = sum(arr) if (s == 0): return 0 nearestLeft(arr, N, steps) nearestRight(arr, N, steps) # Traverse the array from the left side for i in range(N): # Update the value of sum s += 2 * K * max(0, M - steps[i]) # Print the total sum of the array return s # Driver Code if __name__ == "__main__": arr = [ 0, 1, 0, 1, 0, 0 ] N = len(arr) M = 2 K = 1 print(findSum(arr, N, M, K)) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
public class GFG{
// Function to find the nearest non-zero
// element in the left direction
static void nearestLeft(int []arr, int N,
int[] steps)
{
// Stores the index of the first element
// greater than 0 from the right side
int L = -N;
// Traverse the array in the range [1, N]
for (int i = N - 1; i >= 0; i--)
{
// Check arr[i] is greater than 0
if (arr[i] > 0)
{
// Update the value of L
L = -(N - i);
break;
}
}
// Traverse the array from the left side
for (int i = 0; i < N; i++)
{
// Check arr[i] is greater than 0
if (arr[i] > 0)
{
// Update the value of L
L = i;
}
// Update the value of steps[i]
steps[i] = i - L;
}
}
// Function to find the nearest non-zero
// element in the right direction
static void nearestRight(int []arr, int N,
int[] steps)
{
// Stores the index of the first element
// greater than 0 from the left side
int R = 2 * N;
// Traverse the array from the left side
for (int i = 0; i < N; i++) {
// Check arr[i] is greater than 0
if (arr[i] > 0) {
// Update the value of R
R = N + i;
break;
}
}
// Traverse the array from the right side
for (int i = N - 1; i >= 0; i--)
{
// Check arr[i] is greater than 0
if (arr[i] > 0)
{
// Update the value of R
R = i;
}
// Update the value of steps[i]
steps[i] = Math.Min(steps[i], R - i);
}
}
static int accumulate(int[] arr, int start, int end){
int sum = 0;
for(int i= 0; i < arr.Length; i++)
sum += arr[i];
return sum;
}
// Function to find the sum of the array
// after the given operation M times
static int findSum(int []arr, int N, int M, int K)
{
// Stores the distance of the nearest
// non zero element.
int []steps = new int[N];
// Stores sum of the initial array []arr
int sum = accumulate(arr, 0, N);
if (sum == 0) {
return 0;
}
nearestLeft(arr, N, steps);
nearestRight(arr, N, steps);
// Traverse the array from the left side
for (int i = 0; i < N; i++)
// Update the value of sum
sum += 2 * K * Math.Max(0, M - steps[i]);
// Print the total sum of the array
return sum;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 0, 1, 0, 1, 0, 0 };
int N = arr.Length;
int M = 2;
int K = 1;
Console.Write(findSum(arr, N, M, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the nearest non-zero
// element in the left direction
function nearestLeft(arr, N,
steps)
{
// Stores the index of the first element
// greater than 0 from the right side
let L = -N;
// Traverse the array in the range [1, N]
for (let i = N - 1; i >= 0; i--)
{
// Check arr[i] is greater than 0
if (arr[i] > 0)
{
// Update the value of L
L = -(N - i);
break;
}
}
// Traverse the array from the left side
for (let i = 0; i < N; i++)
{
// Check arr[i] is greater than 0
if (arr[i] > 0)
{
// Update the value of L
L = i;
}
// Update the value of steps[i]
steps[i] = i - L;
}
}
// Function to find the nearest non-zero
// element in the right direction
function nearestRight(arr, N,
steps)
{
// Stores the index of the first element
// greater than 0 from the left side
let R = 2 * N;
// Traverse the array from the left side
for (let i = 0; i < N; i++) {
// Check arr[i] is greater than 0
if (arr[i] > 0) {
// Update the value of R
R = N + i;
break;
}
}
// Traverse the array from the right side
for (let i = N - 1; i >= 0; i--)
{
// Check arr[i] is greater than 0
if (arr[i] > 0)
{
// Update the value of R
R = i;
}
// Update the value of steps[i]
steps[i] = Math.min(steps[i], R - i);
}
}
// Function to find the sum of the array
// after the given operation M times
function findSum(arr, N, M, K)
{
// Stores the distance of the nearest
// non zero element.
let steps = new Array(N);
// Stores sum of the initial array arr[]
let sum = 0;
for (let i = 0; i < N; i++) {
sum = sum + arr[i];
}
if (sum == 0) {
return 0;
}
nearestLeft(arr, N, steps);
nearestRight(arr, N, steps);
// Traverse the array from the left side
for (let i = 0; i < N; i++)
// Update the value of sum
sum += 2 * K * Math.max(0, M - steps[i]);
// Print the total sum of the array
return sum;
}
// Driver Code
let arr = [0, 1, 0, 1, 0, 0];
let N = arr.length;
let M = 2;
let K = 1;
document.write(findSum(arr, N, M, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
16
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA