Test if Binary Array will be made Palindrome by flipping two bits at a time

[ad_1]

View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Given a binary array A[] of measurement N, the duty is to verify whether or not the array will be transformed right into a palindrome by flipping two bits in every operation.

Be aware: The operation will be carried out any variety of instances.

Examples:

Enter: A[] = {1, 0, 1, 0, 1, 1}
Output: Sure

Clarification: We will carry out the next operation:
Choose i = 2 and j = 4. Then {1, 0, 1, 0, 1, 1}→{1, 0, 0, 0, 0, 1} which is a palindrome.

Enter: A[] = {0, 1}
Output: No

Method: The issue will be solved primarily based on the next statement: 

Rely variety of 0s and 1s. 

  • If the worth of depend of 0s and 1s are odd then no palindrome will be made by performing operation on A[].
  • In any other case, array A[] can transformed right into a palindrome after performing operation on array.

Observe the beneath steps to resolve the issue:

  • Set zeros = 0 and ones = 0 to retailer the depend of variety of 0s and 1s within the array.
  • After that iterate a loop from 0 to N-1 reminiscent of:
    • If A[i] = 0 increment the worth of zeros in any other case increment the worth of ones.
  • If the worth of zeros and ones is odd then print “No” i.e. it’s not doable to transform A to a palindrome by making use of the above operation any variety of instances.
  • In any other case, print “Sure”.

Beneath is the implementation of the above method.

Java

  

import java.io.*;

import java.util.*;

  

public class GFG {

  

    

    

    public static String verify(int arr[], int n)

    {

        int one = 0, zero = 0;

        for (int i = 0; i < n; i++) {

            if (arr[i] == '0') {

                zero++;

            }

            else {

                one++;

            }

        }

        if (one % 2 != 0 && zero % 2 != 0)

            return "No";

        return "Sure";

    }

  

    

    public static void foremost(String[] args)

    {

        int[] A = { 1, 0, 1, 0, 1, 1 };

        int N = A.size;

  

        

        System.out.println(verify(A, N));

    }

}

Time Complexity: O(N)
Auxiliary House: O(1)

[ad_2]

Leave a Reply