Mnewsfr.com

DSA Flip Bits Problem with Solution in Numerous Language

Given an array A[] consisting of 0’s and 1’s. A flip operation is one in which you turn 1 into 0 and a 0 into 1. You have to do at most one “Flip” operation of any subarray. Formally, select a range (l, r) in the array A[], such that (0 ≤ l ≤ r < n) holds and flip the elements in this range to get the maximum ones in the final array. You can possibly make zero operations to get the answer.

Example -1

Input: N = 5 A[] = {1, 0, 0, 1, 0}

Output: 4 Explanation: We can perform a flip operation in the range [1,2] After flip operation array is : [ 1 1 1 1 0 ] Count of one after fliping is : 4 [Note: the subarray marked in bold is the flipped subarray]

Example -2

Input: N = 7 A[] = {1, 0, 0, 1, 0, 0, 1}

Output: 6 Explanation: We can perform a flip operation in the range [1,5] After flip operation array is : [ 1 1 1 0 1 1 1] Count of one after fliping is : 6 [Note: the subarray marked in bold is the flipped subarray]

Your Task :

You don't need to read input or print anything. Your task is to complete the function maxOnes() which takes the array A[] and its size N as inputs and returns the maximum number of 1's you can have in the array after atmost one flip operation.

Flip Bits Using Python

def maxOnes(A, N):
    max_ones = 0
    max_ones_with_flip = 0
    current_ones = 0

    for num in A:
        if num == 1:
            current_ones += 1
            max_ones_with_flip += 1
        else:
            current_ones = max(current_ones - 1, 0)
            max_ones_with_flip += 1

        max_ones = max(max_ones, current_ones)

    return max(max_ones, max_ones_with_flip)

# Example usage
A = [1, 0, 1, 1, 0, 1, 0, 1]
N = len(A)
result = maxOnes(A, N)
print(result)  # This will output the maximum number of 1's possible after the operation.

Flip Bits Using C#

using System;

class Program
{
    static int MaxOnes(int[] A, int N)
    {
        int maxOnes = 0;
        int maxOnesWithFlip = 0;
        int currentOnes = 0;

        for (int i = 0; i < N; i++)
        {
            if (A[i] == 1)
            {
                currentOnes++;
                maxOnesWithFlip++;
            }
            else
            {
                currentOnes = Math.Max(currentOnes - 1, 0);
                maxOnesWithFlip++;
            }

            maxOnes = Math.Max(maxOnes, currentOnes);
        }

        return Math.Max(maxOnes, maxOnesWithFlip);
    }

    static void Main(string[] args)
    {
        int[] A = { 1, 0, 1, 1, 0, 1, 0, 1 };
        int N = A.Length;
        int result = MaxOnes(A, N);
        Console.WriteLine(result); // This will output the maximum number of 1's possible after the operation.
    }
}

Flip Bits Using Java

public class Main {
    public static int maxOnes(int[] A, int N) {
        int maxOnes = 0;
        int maxOnesWithFlip = 0;
        int currentOnes = 0;

        for (int i = 0; i < N; i++) {
            if (A[i] == 1) {
                currentOnes++;
                maxOnesWithFlip++;
            } else {
                currentOnes = Math.max(currentOnes - 1, 0);
                maxOnesWithFlip++;
            }

            maxOnes = Math.max(maxOnes, currentOnes);
        }

        return Math.max(maxOnes, maxOnesWithFlip);
    }

    public static void main(String[] args) {
        int[] A = {1, 0, 1, 1, 0, 1, 0, 1};
        int N = A.length;
        int result = maxOnes(A, N);
        System.out.println(result); // This will output the maximum number of 1's possible after the operation.
    }
}

Flip Bits Using JavaScript

function maxOnes(A) {
    let maxOnes = 0;
    let maxOnesWithFlip = 0;
    let currentOnes = 0;

    for (let i = 0; i < A.length; i++) {
        if (A[i] === 1) {
            currentOnes++;
            maxOnesWithFlip++;
        } else {
            currentOnes = Math.max(currentOnes - 1, 0);
            maxOnesWithFlip++;
        }

        maxOnes = Math.max(maxOnes, currentOnes);
    }

    return Math.max(maxOnes, maxOnesWithFlip);
}

// Example usage
const A = [1, 0, 1, 1, 0, 1, 0, 1];
const result = maxOnes(A);
console.log(result); // This will output the maximum number of 1's possible after the operation.

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(1)

Constraints

1 ≤ N ≤ 106 0 ≤ A[i] ≤ 1