Find the size of the final imaginary Array after removing the balls
Given 2 arrays color[]and radius[] of length N each representing N balls, where color[i] represents the color of the ith ball while radius[i] represents the radius of the ith ball. If two consecutive balls have the same color and size, both are removed from the array, the task is to find the length of the final imaginary array.
Examples:
Input: N = 3, color[] = {2, 2, 5}, radius[] = {3, 3, 4}
Output: 1
Explanation: First ball and second ball have the same color 2 and the same radius 3. So, after removing only one ball is left. It could not be removed from the array. Hence, the final array has length 1.Input: N = 4, color[] = {1, 3, 3, 1}, radius[] = {2, 5, 5, 2}
Output: 0
Explanation: Ball 2 and ball 3 have the same color 3 and the same radius 5. So, they are removed. Now, we have got our color[]={1, 1} and radius[]={2, 2}.Both the left balls are consecutive now and they are having same color and radius. So, these two balls are removed as well. Now, we are left with the empty final array. Hence, the length of the final array is 0.
Approach: This can be solved with the following idea:
Use a vector to store the indices of the remaining elements in the final sequence and remove adjacent pairs that have the same color and radius.
Below are the steps mentioned to implement the code:
- Create an empty vector to store the indices of the remaining elements in the final sequence.
- Loop through the elements of the given sequence.
- For each element, check if the last element in the ‘ans’ vector has the same color and radius as the current element.
- If they are the same, remove the last element from the ‘ans‘ vector. If they are not the same, add the current index to the ‘ans’ vector.
- Finally, return the size of the ‘ans‘ vector, which represents the length of the final sequence after removing all adjacent pairs that have the same color and radius.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find the length // of imaginary int find_Length( int n, vector< int > color, vector< int > radius) { // Create an empty vector to result vector< int > ans; // Loop through the elements of // the sequence for ( int i = 0; i < n; i++) { // Check if the last element in // the 'ans' vector has the same // color and radius as the // current element if (ans.size() != 0 && color[i] == color[ans.back()] && radius[ans.back()] == radius[i]) { // If they are the same, // remove the last element // from the 'ans' vector ans.pop_back(); } else { // If they are not the same, // add the current index to // the 'ans' vector ans.push_back(i); } } // Return the size of the // 'ans' vector return ans.size(); } // Driver Code int main() { int n = 3; vector< int > color(n), radius(n); color = { 2, 2, 5 }; radius = { 3, 3, 4 }; // Function call int ans = find_Length(n, color, radius); cout << ans << "\n" ; return 0; } |
Java
import java.util.*; class Main { // Function to find the length of imaginary static int findLength( int n, List<Integer> color, List<Integer> radius) { // Create an empty list to store the result List<Integer> ans = new ArrayList<>(); // Loop through the elements of the sequence for ( int i = 0 ; i < n; i++) { // Check if the last element in the 'ans' list has the same color and // radius as the current element if (!ans.isEmpty() && color.get(i).equals(color.get(ans.get(ans.size() - 1 ))) && radius.get(ans.get(ans.size() - 1 )).equals(radius.get(i))) { // If they are the same, remove the last element from the 'ans' list ans.remove(ans.size() - 1 ); } else { // If they are not the same, add the current index to the 'ans' list ans.add(i); } } // Return the size of the 'ans' list return ans.size(); } // Driver code public static void main(String[] args) { int n = 3 ; List<Integer> color = new ArrayList<>(Arrays.asList( 2 , 2 , 5 )); List<Integer> radius = new ArrayList<>(Arrays.asList( 3 , 3 , 4 )); // Function call int ans = findLength(n, color, radius); System.out.println(ans); } } // This code is contributed by Codearcade |
Python3
# Python code for the above approach: def find_length(n, color, radius): # Create an empty list to store the result ans = [] # Loop through the elements of the sequence for i in range (n): # Check if the last element in the 'ans' list has the same color and radius as the current element if ans and color[i] = = color[ans[ - 1 ]] and radius[ans[ - 1 ]] = = radius[i]: # If they are the same, remove the last element from the 'ans' list ans.pop() else : # If they are not the same, add the current index to the 'ans' list ans.append(i) # Return the size of the 'ans' list, which represents the length of the longest subsequence return len (ans) # Driver code if __name__ = = "__main__" : n = 3 color = [ 2 , 2 , 5 ] radius = [ 3 , 3 , 4 ] # Function call ans = find_length(n, color, radius) print (ans) |
C#
// C# code for the above approach: using System; using System.Collections.Generic; class GFG { // Function to find the length of imaginary static int FindLength( int n, List< int > color, List< int > radius) { // Create an empty list to store the result List< int > ans = new List< int >(); // Loop through the elements of the sequence for ( int i = 0; i < n; i++) { // Check if the last element in the 'ans' list has the same color and // radius as the current element if (ans.Count > 0 && color[i] == color[ans[ans.Count - 1]] && radius[ans[ans.Count - 1]] == radius[i]) { // If they are the same, remove the last element from the 'ans' list ans.RemoveAt(ans.Count - 1); } else { // If they are not the same, add the current index to the 'ans' list ans.Add(i); } } // Return the size of the 'ans' list return ans.Count; } // Driver code public static void Main( string [] args) { int n = 3; List< int > color = new List< int > { 2, 2, 5 }; List< int > radius = new List< int > { 3, 3, 4 }; // Function call int ans = FindLength(n, color, radius); Console.WriteLine(ans); } } |
Javascript
// Function to find the length of imaginary function FindLength(n, color, radius) { // Create an empty list to store the result let ans = []; // Loop through the elements of the sequence for (let i = 0; i < n; i++) { // Check if the last element in the 'ans' list has the same color and // radius as the current element if (ans.length > 0 && color[i] === color[ans[ans.length - 1]] && radius[ans[ans.length - 1]] === radius[i]) { // If they are the same, remove the last element from the 'ans' list ans.pop(); } else { // If they are not the same, add the current index to the 'ans' list ans.push(i); } } // Return the size of the 'ans' list return ans.length; } // Driver code let n = 3; let color = [2, 2, 5]; let radius = [3, 3, 4]; let ans = FindLength(n, color, radius); console.log(ans); |
1
Time Complexity: O(n), since we traverse once through the array.
Auxiliary Space: O(n), since we are using a vector to store the elements.
Approach – 2: Using Stack
1. Initializing an empty stack to store the colors and radii of the imaginary circles as pairs.
2. For each circle, we check if it has the same color and radius as the top element in the stack. If so, we pop the top element.
3. If the circle’s color and radius are different from the top element, we push it onto the stack.
4. At the end, the size of the stack will be the length of the longest imaginary.
5. Finally, return the size of the stack as the result.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find the length // of imaginary int find_Length( int N, vector< int > color, vector< int > radius) { // Create a stack to store unique color-radius pairs stack<pair< int , int >> st; // Loop through each color-radius pair for ( int i = 0; i < N; i++) { bool flag = true ; int col = color[i], rad = radius[i]; // Check if there is a pair in the stack with the same color and radius while (!st.empty() && (st.top().first == col && st.top().second == rad)) { st.pop(); flag = false ; } // If there is no such pair, push the current pair onto the stack if (flag) st.push({col,rad}); } // Return the number of unique color-radius pairs in the stack return st.size(); } // Driver Code int main() { int n = 3; vector< int > color(n), radius(n); color = { 2, 2, 5 }; radius = { 3, 3, 4 }; // Function call int ans = find_Length(n, color, radius); cout << ans << "\n" ; return 0; } |
Java
// Java code implementation // of above approach import java.util.Stack; public class Main { public static void main(String[] args) { int n = 3 ; int [] color = { 2 , 2 , 5 }; int [] radius = { 3 , 3 , 4 }; int ans = findLength(n, color, radius); System.out.println(ans); } static int findLength( int N, int [] color, int [] radius) { // Create a stack to store unique color-radius pairs Stack<Pair> st = new Stack<>(); // Loop through each color-radius pair for ( int i = 0 ; i < N; i++) { boolean flag = true ; int col = color[i]; int rad = radius[i]; // Check if there is a pair in the stack with the same color and radius while (!st.isEmpty() && st.peek().color == col && st.peek().radius == rad) { st.pop(); flag = false ; } // If there is no such pair, push the current pair onto the stack if (flag) { st.push( new Pair(col, rad)); } } // Return the number of unique color-radius pairs in the stack return st.size(); } } // Driver Code class Pair { int color; int radius; public Pair( int color, int radius) { this .color = color; this .radius = radius; } } // This code is contributed by Dwaipayan Bandyopadhyay |
Python3
# Function to find the length # of imaginary def find_Length(N, color, radius): # Create a stack to store unique color-radius pairs st = [] # Loop through each color-radius pair for i in range (N): flag = True col = color[i] rad = radius[i] # Check if there is a pair in the stack with the same color and radius while st and (st[ - 1 ][ 0 ] = = col and st[ - 1 ][ 1 ] = = rad): st.pop() flag = False # If there is no such pair, push the current pair onto the stack if flag: st.append((col, rad)) # Return the number of unique color-radius pairs in the stack return len (st) # Driver n = 3 color = [ 2 , 2 , 5 ] radius = [ 3 , 3 , 4 ] ans = find_Length(n, color, radius) print (ans) |
C#
using System; using System.Collections.Generic; class Program { // Function to find the length of imaginary static int FindLength( int N, List< int > color, List< int > radius) { // Create a stack to store unique color-radius pairs Stack<Tuple< int , int >> stack = new Stack<Tuple< int , int >>(); // Loop through each color-radius pair for ( int i = 0; i < N; i++) { bool flag = true ; int col = color[i]; int rad = radius[i]; // Check if there is a pair in the stack with the same color and radius while (stack.Count > 0 && (stack.Peek().Item1 == col && stack.Peek().Item2 == rad)) { stack.Pop(); flag = false ; } // If there is no such pair, push the current pair onto the stack if (flag) { stack.Push(Tuple.Create(col, rad)); } } // Return the number of unique color-radius pairs in the stack return stack.Count; } static void Main() { int n = 3; List< int > color = new List< int > { 2, 2, 5 }; List< int > radius = new List< int > { 3, 3, 4 }; // Function call int ans = FindLength(n, color, radius); Console.WriteLine(ans); } } |
Javascript
class Pair { constructor(color, radius) { this .color = color; this .radius = radius; } } function findLength(N, color, radius) { // Create an empty stack to store unique color-radius pairs const stack = []; // Loop through each color-radius pair for (let i = 0; i < N; i++) { let flag = true ; const col = color[i]; const rad = radius[i]; // Check if there is a pair in the stack with the same color and radius while (stack.length > 0 && stack[stack.length - 1].color === col && stack[stack.length - 1].radius === rad) { stack.pop(); flag = false ; } // If there is no such pair, push the current pair onto the stack if (flag) { stack.push( new Pair(col, rad)); } } // Return the number of unique color-radius pairs in the stack return stack.length; } // Driver code const n = 3; const color = [2, 2, 5]; const radius = [3, 3, 4]; // Function call const ans = findLength(n, color, radius); console.log(ans); |
1
Time Complexity: O(n), as traversing over the array so time complexity is O(n).
Auxiliary Space: O(n), as taken a stack so space complexity is O(n).
Contact Us