There are N stations in a straight line, each of them has some non-negative radiation power. Every station can increase the radiation power of its neighbouring stations in the following way,
Station i with radiation power R will increase (i – 1)th station’s radiation by R – 1, (i – 2)th station’s radiation by R – 2, so on… and (i + 1)th station’s radiation by R – 1, (i + 2)th station’s radiation by R – 2, so on… upto when the effective radiation power is positive.
The task is to find the final radiations for each of the stations.
Examples:
Input: arr[] = {1, 2, 3}
Output: 3 4 4
The new radiation will be {1 + (2 – 1) + (3 – 2), 2 + (1 – 1) + (3 – 1), 3 + (2 – 1)}
i.e. {3, 4, 4}
Input: arr[] = {9, 87, 55, 2, 1}
Output: 148 149 149 147 144
Input: arr[] = {7, 9, 12, 2, 5}
Output: 26 28 29 28 25
Naive Approach: For each station, i increase the radiation of the neighbour stations as mentioned above upto when the effective radiation becomes negative.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to print the final radiationsvoid print(int rStation[], int n){ for (int i = 1; i <= n; i++) cout << rStation[i] << " "; cout << endl;}// Function to create the array of the// resultant radiationsvoid radiated_Station(int station[], int n){ // Resultant radiations int rStation[n + 1]; // Initialize resultant array with 0 memset(rStation, 0, sizeof(rStation)); for (int i = 1; i <= n; i++) { // Declaring index counter for left // and right radiation int li = i - 1, ri = i + 1; // Effective radiation for left // and right case int lRad = station[i] - 1, rRad = station[i] - 1; // Radiation for i-th station rStation[i] += station[i]; // Radiation increment for left stations while (li >= 1 && lRad >= 1) { rStation[li--] += lRad--; } // Radiation increment for right stations while (ri <= n && rRad >= 1) { rStation[ri++] += rRad--; } } // Print the resultant radiation // for each of the stations print(rStation, n);}// Driver codeint main(){ // 1-based indexing int station[] = { 0, 7, 9, 12, 2, 5 }; int n = (sizeof(station) / sizeof(station[0])) - 1; radiated_Station(station, n); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function to print the final radiations static void print(int rStation[], int n) { for (int i = 1; i <= n; i++) System.out.print(rStation[i] + " "); System.out.println(""); } // Function to create the array of the // resultant radiations static void radiated_Station(int station[], int n) { // Resultant radiations int rStation[] = new int[n + 1]; for (int i = 1; i <= n; i++) { // Declaring index counter for left // and right radiation int li = i - 1, ri = i + 1; // Effective radiation for left // and right case int lRad = station[i] - 1, rRad = station[i] - 1; // Radiation for i-th station rStation[i] += station[i]; // Radiation increment for left stations while (li >= 1 && lRad >= 1) { rStation[li--] += lRad--; } // Radiation increment for right stations while (ri <= n && rRad >= 1) { rStation[ri++] += rRad--; } } // Print the resultant radiation // for each of the stations print(rStation, n); } // Driver code public static void main(String[] args) { // 1-based indexing int station[] = { 0, 7, 9, 12, 2, 5 }; int n = station.length - 1; radiated_Station(station, n); }}// This code has been contributed by 29AjayKumar |
Python3
# Python 3 implementation of the approach# Function to print the final radiationsdef printf(rStation, n): for i in range(1, n + 1, 1): print(rStation[i], end = " ") print("\n", end = " ")# Function to create the array of the# resultant radiationsdef radiated_Station(station, n): # Resultant radiations rStation = [0 for i in range(n + 1)] for i in range(1, n + 1): # Declaring index counter for left # and right radiation li = i - 1 ri = i + 1 # Effective radiation for left # and right case lRad = station[i] - 1 rRad = station[i] - 1 # Radiation for i-th station rStation[i] += station[i] # Radiation increment for left stations while (li >= 1 and lRad >= 1): rStation[li] += lRad lRad -= 1 li -= 1 # Radiation increment for right stations while (ri <= n and rRad >= 1): rStation[ri] += rRad rRad -= 1 ri += 1 # Print the resultant radiation # for each of the stations printf(rStation, n)# Driver codeif __name__ == '__main__': # 1-based indexing station = [0, 7, 9, 12, 2, 5] n = len(station) - 1 radiated_Station(station, n) # This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG { // Function to print the final radiations static void print(int[] rStation, int n) { for (int i = 1; i <= n; i++) Console.Write(rStation[i] + " "); Console.WriteLine(""); } // Function to create the array of the // resultant radiations static void radiated_Station(int[] station, int n) { // Resultant radiations int[] rStation = new int[n + 1]; for (int i = 1; i <= n; i++) { // Declaring index counter for left // and right radiation int li = i - 1, ri = i + 1; // Effective radiation for left // and right case int lRad = station[i] - 1, rRad = station[i] - 1; // Radiation for i-th station rStation[i] += station[i]; // Radiation increment for left stations while (li >= 1 && lRad >= 1) { rStation[li--] += lRad--; } // Radiation increment for right stations while (ri <= n && rRad >= 1) { rStation[ri++] += rRad--; } } // Print the resultant radiation // for each of the stations print(rStation, n); } // Driver code public static void Main(String[] args) { // 1-based indexing int[] station = { 0, 7, 9, 12, 2, 5 }; int n = station.Length - 1; radiated_Station(station, n); }}/* This code contributed by PrinciRaj1992 */ |
PHP
<?php// PHP implementation of the approach // Function to print the final radiationsfunction print_radiation($rStation, $n){ for ($i = 1; $i <= $n; $i++) { echo $rStation[$i]." "; } echo "\n";}// Function to create the array of the// resultant radiationsfunction radiated_Station($station, $n){ // Resultant radiations $rStation = array(); // Initialize resultant array with 0 $rStation = array_fill(0, $n+1, 0); for ($i = 1; $i <= $n; $i++) { // Declaring index counter for left // and right radiation $li = $i - 1; $ri = $i + 1; // Effective radiation for left // and right case $lRad = $station[$i] - 1; $rRad = $station[$i] - 1; // Radiation for i-th station $rStation[$i] += $station[$i]; // Radiation increment for left stations while ($li >= 1 && $lRad >= 1) { $rStation[$li--] += $lRad--; } // Radiation increment for right stations while ($ri <= $n && $rRad >= 1) { $rStation[$ri++] += $rRad--; } } // Print the resultant radiation // for each of the stations print_radiation($rStation, $n);} // Driver code// 1-based indexing$station = array( 0, 7, 9, 12, 2, 5 );$n = (sizeof($station) / sizeof($station[0])) - 1;radiated_Station($station, $n);//code contributed by Shashank_Sharma?> |
Javascript
<script>// javascript implementation of the approach // Function to print the final radiations function print( rStation, n) { for (var i = 1; i <= n; i++) document.write(rStation[i] + " "); document.write("<br>"); } // Function to create the array of the // resultant radiations function radiated_Station(station, n) { // Resultant radiations var rStation = [] ; rStation.length = 6 ; rStation.fill(0) for (var i = 1; i <= n; i++) { // Declaring index counter for left // and right radiation var li = i - 1, ri = i + 1; // Effective radiation for left // and right case var lRad = station[i] - 1, rRad = station[i] - 1; // Radiation for i-th station rStation[i] += station[i]; // Radiation increment for left stations while (li >= 1 && lRad >= 1) { rStation[li--] += lRad--; } // Radiation increment for right stations while (ri <= n && rRad >= 1) { rStation[ri++] += rRad--; } } // Print the resultant radiation // for each of the stations print(rStation, n); } // Driver code // 1-based indexing var station = [ 0, 7, 9, 12, 2, 5 ] var n = station.length - 1; radiated_Station(station, n); // This code is contributed by bunnyram19. </script> |
Output:
26 28 29 28 25
Time Complexity: O(n*n)
Auxiliary Space: O(n)
Efficient Approach:
- For each station, we’ll calculate its extreme left and right radiation effects separately.
- Then two iterations one from left another from right will construct two arrays.
- Left iteration will construct array left_Rad[] that is made of each station’s left effective radiation and right_Rad[] will be constructed by the Right iteration.
- For station i let us assume it will be effected by m number of stations’ left radiation and n number of stations’ right radiation. we need another arrays lCount[] for the m values and rcount[] for n values.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to print the final radiationsvoid print(int rStation[], int n){ for (int i = 1; i <= n; i++) cout << rStation[i] << " "; cout << endl;}// Function to create the array of the// resultant radiationsvoid radiated_Station(int station[], int n){ // Resultant radiations int rStation[n + 1]; int left_Rad[n + 2], right_Rad[n + 2]; // Frequency of stations that affect each station int lCount[n + 2], rCount[n + 2]; // Initialization of the arrays with 0 memset(left_Rad, 0, sizeof(left_Rad)); memset(right_Rad, 0, sizeof(right_Rad)); memset(lCount, 0, sizeof(lCount)); memset(rCount, 0, sizeof(rCount)); for (int i = 1; i < n + 1; i++) { // Radiation of station i int Rad = station[i]; // Left and right most position of radiation // for station i, index should be // in between the station range int li = max(1, i - Rad + 1), ri = min(n, Rad - 1 + i); // At station 1 radiation effect // for station i int at1 = max(0, Rad - i + 1); left_Rad[1] += at1; // While iterating from left avoid // effective radiation at right left_Rad[i + 1] -= Rad; // At station n radiation effect // for station i int atn = max(0, Rad - n + i); right_Rad[n] += atn; // While iterating from right avoid // effective radiation at left right_Rad[i - 1] -= Rad; // Left and right most position // where station i effects lCount[li]++; rCount[ri]++; // Avoiding right radiation for // left iteration and vice-versa lCount[i + 1]--; rCount[i - 1]--; } // Left iteration for (int i = 1; i <= n; i++) { lCount[i] += lCount[i - 1]; // Total radiations at index 1 already counted if (i > 1) left_Rad[i] += left_Rad[i - 1] + lCount[i]; } // Right iteration for (int i = n; i >= 1; i--) { rCount[i] += rCount[i + 1]; // Total radiations at index n already counted if (i < n) right_Rad[i] += right_Rad[i + 1] + rCount[i]; } // Final iteration that creates // the resultant radiation for (int i = 1; i <= n; i++) { // Added extra value in each index rStation[i] = left_Rad[i] + right_Rad[i] - station[i]; } // Print the resultant radiation // for each of the stations print(rStation, n);}// Driver codeint main(){ // 1-based indexing int station[] = { 0, 7, 9, 12, 2, 5 }; int n = (sizeof(station) / sizeof(station[0])) - 1; radiated_Station(station, n); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function to print the final radiations static void print(int rStation[], int n) { for (int i = 1; i <= n; i++) System.out.print(rStation[i] + " "); System.out.println(""); } // Function to create the array of the // resultant radiations static void radiated_Station(int station[], int n) { // Resultant radiations int[] rStation = new int[n + 1]; int[] left_Rad = new int[n + 2]; int[] right_Rad = new int[n + 2]; // Frequency of stations that affect each station int[] lCount = new int[n + 2]; int[] rCount = new int[n + 2]; for (int i = 1; i < n + 1; i++) { // Radiation of station i int Rad = station[i]; // Left and right most position of radiation // for station i, index should be // in between the station range int li = Math.max(1, i - Rad + 1), ri = Math.min(n, Rad - 1 + i); // At station 1 radiation effect // for station i int at1 = Math.max(0, Rad - i + 1); left_Rad[1] += at1; // While iterating from left avoid // effective radiation at right left_Rad[i + 1] -= Rad; // At station n radiation effect // for station i int atn = Math.max(0, Rad - n + i); right_Rad[n] += atn; // While iterating from right avoid // effective radiation at left right_Rad[i - 1] -= Rad; // Left and right most position // where station i effects lCount[li]++; rCount[ri]++; // Avoiding right radiation for // left iteration and vice-versa lCount[i + 1]--; rCount[i - 1]--; } // Left iteration for (int i = 1; i <= n; i++) { lCount[i] += lCount[i - 1]; // Total radiations at index 1 already counted if (i > 1) left_Rad[i] += left_Rad[i - 1] + lCount[i]; } // Right iteration for (int i = n; i >= 1; i--) { rCount[i] += rCount[i + 1]; // Total radiations at index n already counted if (i < n) right_Rad[i] += right_Rad[i + 1] + rCount[i]; } // Final iteration that creates // the resultant radiation for (int i = 1; i <= n; i++) { // Added extra value in each index rStation[i] = left_Rad[i] + right_Rad[i] - station[i]; } // Print the resultant radiation // for each of the stations print(rStation, n); } // Driver code public static void main(String[] args) { // 1-based indexing int station[] = { 0, 7, 9, 12, 2, 5 }; int n = station.length - 1; radiated_Station(station, n); }}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach# Function to print the final radiationsdef print_array(rStation, n): for i in range(1, n + 1): print(rStation[i], end = " ")# Function to create the array of the# resultant radiationsdef radiated_Station(station, n): # Resultant radiations rStation = [0] * (n + 1) left_Rad = [0] * (n + 2) right_Rad = [0] * (n + 2) # Frequency of stations that # affect each station lCount = [0] * (n + 2) rCount = [0] * (n + 2) for i in range(1, n + 1): # Radiation of station i Rad = station[i] # Left and right most position of # radiation for station i, index # should be in between the station range li = max(1, i - Rad + 1) ri = min(n, Rad - 1 + i); # At station 1 radiation effect # for station i at1 = max(0, Rad - i + 1) left_Rad[1] += at1; # While iterating from left avoid # effective radiation at right left_Rad[i + 1] -= Rad; # At station n radiation effect # for station i atn = max(0, Rad - n + i); right_Rad[n] += atn # While iterating from right avoid # effective radiation at left right_Rad[i - 1] -= Rad # Left and right most position # where station i effects lCount[li] += 1 rCount[ri] += 1 # Avoiding right radiation for # left iteration and vice-versa lCount[i + 1] -= 1 rCount[i - 1] -= 1 # Left iteration for i in range(1, n + 1): lCount[i] += lCount[i - 1] # Total radiations at index 1 # already counted if (i > 1): left_Rad[i] += (left_Rad[i - 1] + lCount[i]) # Right iteration for i in range(n, 0, -1): rCount[i] += rCount[i + 1] # Total radiations at index n already counted if (i < n): right_Rad[i] += (right_Rad[i + 1] + rCount[i]) # Final iteration that creates # the resultant radiation for i in range(1, n + 1): # Added extra value in each index rStation[i] = (left_Rad[i] + right_Rad[i] - station[i]) # Print the resultant radiation # for each of the stations print_array(rStation, n)# Driver codeif __name__ == "__main__": # 1-based indexing station = [ 0, 7, 9, 12, 2, 5 ] n = len(station) - 1 radiated_Station(station, n)# This code is contributed by chitranayal |
C#
// C# implementation of the approachusing System;class GFG { // Function to print the final radiations static void print(int[] rStation, int n) { for (int i = 1; i <= n; i++) Console.Write(rStation[i] + " "); Console.WriteLine(""); } // Function to create the array of the // resultant radiations static void radiated_Station(int[] station, int n) { // Resultant radiations int[] rStation = new int[n + 1]; int[] left_Rad = new int[n + 2]; int[] right_Rad = new int[n + 2]; // Frequency of stations that affect each station int[] lCount = new int[n + 2]; int[] rCount = new int[n + 2]; for (int i = 1; i < n + 1; i++) { // Radiation of station i int Rad = station[i]; // Left and right most position of radiation // for station i, index should be // in between the station range int li = Math.Max(1, i - Rad + 1), ri = Math.Min(n, Rad - 1 + i); // At station 1 radiation effect // for station i int at1 = Math.Max(0, Rad - i + 1); left_Rad[1] += at1; // While iterating from left avoid // effective radiation at right left_Rad[i + 1] -= Rad; // At station n radiation effect // for station i int atn = Math.Max(0, Rad - n + i); right_Rad[n] += atn; // While iterating from right avoid // effective radiation at left right_Rad[i - 1] -= Rad; // Left and right most position // where station i effects lCount[li]++; rCount[ri]++; // Avoiding right radiation for // left iteration and vice-versa lCount[i + 1]--; rCount[i - 1]--; } // Left iteration for (int i = 1; i <= n; i++) { lCount[i] += lCount[i - 1]; // Total radiations at index 1 already counted if (i > 1) left_Rad[i] += left_Rad[i - 1] + lCount[i]; } // Right iteration for (int i = n; i >= 1; i--) { rCount[i] += rCount[i + 1]; // Total radiations at index n already counted if (i < n) right_Rad[i] += right_Rad[i + 1] + rCount[i]; } // Final iteration that creates // the resultant radiation for (int i = 1; i <= n; i++) { // Added extra value in each index rStation[i] = left_Rad[i] + right_Rad[i] - station[i]; } // Print the resultant radiation // for each of the stations print(rStation, n); } // Driver code public static void Main(String[] args) { // 1-based indexing int[] station = { 0, 7, 9, 12, 2, 5 }; int n = station.Length - 1; radiated_Station(station, n); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// JavaScript implementation of the approach// Function to print the final radiationsfunction print(rStation, n){ for (let i = 1; i <= n; i++) document.write(rStation[i] + " "); document.write("<br>");}// Function to create the array of the// resultant radiationsfunction radiated_Station(station, n){ // Resultant radiations let rStation = new Array(n + 1); let left_Rad = new Array(n + 2).fill(0); let right_Rad = new Array(n + 2).fill(0); // Frequency of stations that affect each station let lCount = new Array(n + 2).fill(0); let rCount = new Array(n + 2).fill(0); for (let i = 1; i < n + 1; i++) { // Radiation of station i let Rad = station[i]; // Left and right most position of radiation // for station i, index should be // in between the station range let li = Math.max(1, i - Rad + 1); let ri = Math.min(n, Rad - 1 + i); // At station 1 radiation effect // for station i let at1 = Math.max(0, Rad - i + 1); left_Rad[1] += at1; // While iterating from left avoid // effective radiation at right left_Rad[i + 1] -= Rad; // At station n radiation effect // for station i let atn = Math.max(0, Rad - n + i); right_Rad[n] += atn; // While iterating from right avoid // effective radiation at left right_Rad[i - 1] -= Rad; // Left and right most position // where station i effects lCount[li]++; rCount[ri]++; // Avoiding right radiation for // left iteration and vice-versa lCount[i + 1]--; rCount[i - 1]--; } // Left iteration for (let i = 1; i <= n; i++) { lCount[i] += lCount[i - 1]; // Total radiations at index 1 already counted if (i > 1) left_Rad[i] += left_Rad[i - 1] + lCount[i]; } // Right iteration for (let i = n; i >= 1; i--) { rCount[i] += rCount[i + 1]; // Total radiations at index n already counted if (i < n) right_Rad[i] += right_Rad[i + 1] + rCount[i]; } // Final iteration that creates // the resultant radiation for (let i = 1; i <= n; i++) { // Added extra value in each index rStation[i] = left_Rad[i] + right_Rad[i] - station[i]; } // Print the resultant radiation // for each of the stations print(rStation, n);}// Driver code // 1-based indexing let station = [ 0, 7, 9, 12, 2, 5 ]; let n = station.length - 1; radiated_Station(station, n);</script> |
Output:
26 28 29 28 25
Time Complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
