Given a binary array a[] of size N of 1’s and 0’s. The task is to remove an element if a[i-1]+a[i]+a[i+1] is divisible by 3. Print 1 if more number of 1’s are removed than 0, otherwise print 0.
Examples:
Input: a[] = { 1, 1, 1, 0, 1, 0, 0}
Output: 1
Explanation: Remove the second 1 from the left since that is the only ‘1’ for which (a[i]+a[i-1]+a[i+1]) %3==0. So print 1.Input: a[] = { 1, 1}
Output: 0
Explanation: No removal possible, so print 0.
Approach: The idea is based on the observation that if both neighbours are equal to current element because if (a[i]=a[i-1]=a[i+1]) then there sum will always divisible by 3. Let’s say A stores the number of 1’s removed and B stores the number of 0’s removed. If ith element is equal to the neighbours, then if a[i] =1, increment A, otherwise B. If the count of A is greater than B, print 1, otherwise print 2=0. Follow the steps below to solve the problem:
- Initialize the variables A and B as 0 to store the number of 1 and 0 removed.
- Iterate over the range [0, N) using the variable i and perform the following steps:
- If a[i-1], a[i] and a[i+1] are equal, then if a[i] equals 1, then increase the value of A by 1 else B by 1.
- If A is greater than B, then print 1 else print 0.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>using namespace std;// Function to if more number of// 1's are removed or 0'svoid solution(vector<int> a){ // Stores count of 1's removes int A = 0; // Stores count of 0's removes int B = 0; // Traverse the array for (int i = 1; i < a.size() - 1; i++) { // Check the divisibility if (a[i] == a[i - 1] && a[i] == a[i + 1]) { // Check for 1 or 0 if (a[i] == 1) A++; else B++; } } // Print the result if (A > B) cout << ("1"); else cout << ("0");}// Driver Codeint main(){ vector<int> a = { 1, 1, 1, 0, 1, 0, 0 }; solution(a); return 0;}// This code is contributed by lokeshpotta20. |
Java
// Java program for above approachimport java.io.*;import java.util.*;class GFG { // Function to if more number of // 1's are removed or 0's public static void solution(int[] a) { // Stores count of 1's removes int A = 0; // Stores count of 0's removes int B = 0; // Traverse the array for (int i = 1; i < a.length - 1; i++) { // Check the divisibility if (a[i] == a[i - 1] && a[i] == a[i + 1]) { // Check for 1 or 0 if (a[i] == 1) A++; else B++; } } // Print the result if (A > B) System.out.println("1 "); else System.out.println("0 "); } // Driver Code public static void main(String[] args) { int a[] = { 1, 1, 1, 0, 1, 0, 0 }; solution(a); }} |
Python3
# Python3 program for above approach# Function to if more number of# 1's are removed or 0'sdef solution(a) : # Stores count of 1's removes A = 0; # Stores count of 0's removes B = 0; # Traverse the array for i in range(1 , len(a)- 1) : # Check the divisibility if (a[i] == a[i - 1] and a[i] == a[i + 1]) : # Check for 1 or 0 if (a[i] == 1) : A += 1; else : B += 1; # Print the result if (A > B) : print("1"); else : print("0");# Driver Codeif __name__ == "__main__" : a = [ 1, 1, 1, 0, 1, 0, 0 ]; solution(a); # This code is contributed by AnkThon |
C#
// C# program for above approachusing System;public class GFG { // Function to if more number of // 1's are removed or 0's public static void solution(int[] a) { // Stores count of 1's removes int A = 0; // Stores count of 0's removes int B = 0; // Traverse the array for (int i = 1; i < a.Length - 1; i++) { // Check the divisibility if (a[i] == a[i - 1] && a[i] == a[i + 1]) { // Check for 1 or 0 if (a[i] == 1) A++; else B++; } } // Print the result if (A > B) Console.WriteLine("1 "); else Console.WriteLine("0 "); } // Driver Code public static void Main(string[] args) { int []a = { 1, 1, 1, 0, 1, 0, 0 }; solution(a); }}// This code is contributed by AnkThon |
Javascript
<script>// Function to if more number of// 1's are removed or 0'sfunction solution(a) { // Stores count of 1's removes let A = 0; // Stores count of 0's removes let B = 0; // Traverse the array for (let i = 1; i < a.length - 1; i++) { // Check the divisibility if (a[i] == a[i - 1] && a[i] == a[i + 1]) { // Check for 1 or 0 if (a[i] == 1) A++; else B++; } } // Print the result if (A > B) document.write(("1")); else document.write(("0"));}// Driver Codelet a = [1, 1, 1, 0, 1, 0, 0];solution(a);// This code is contributed by Saurabh Jaiswal.</script> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
