Flip Prefix
Source: codechef
Difficulty: 1148

Flip Prefix
You are given a
binary
string$S$of length$N$, i.e.$S_i = 0$or$1$.
You can do the following operation as many times as you want (possibly zero):
Choose a prefix$S[1, X]$($1 \le X \le N$) such that there are equal number of$0$s and$1$s in this prefix, and then flip$^{\dagger}$that prefix.
For example, in the string$001101$, we can choose the prefix of length$4$which has$2$$0$s and$2$$1$s, flipping it produces$110001$.
Count the number of possible strings you can obtain by doing these operations.$^{\dagger}$To flip a string means to change all$0$s to$1$s and all$1$s to$0$s.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains$N$- the size of the string
The second line contains$S$- a binary string.
Output Format
For each test case, output on a new line the count of strings obtainable.
Constraints$1 \le T \le 100$$1 \le N \le 60$$|S| = N$$S_i \in \{0, 1\}$Sample 1:
Explanation:
Test Case 1
: Flip the prefix of length$2$to obtain$100$. The original string,$010$should also be counted. Hence the answer is$2$.
Test Case 2
: No prefixes have equal$0$s and$1$s, so no operations are possible. The original string$0010$is the only possible string.

Sample Input:
3
3
010
4
0010
6
001101

Sample Output:
2
1
4

C++ solution:
//Flip Prefix(cc)
//dfs code // Kadane Algorithum
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
void solve()
{
   ll n; cin >> n;
   string s; cin >> s;
   ll count_1 = 0, count_0 = 0;
   ll count = 1;
   for(ll i=0;i<s.size();i++)
   {
        if(s[i] == '1') 
        {
            count_1++;
        }
        else if(s[i] == '0') 
        {
            count_0++;
        }
        if(count_1 == count_0)
        {
            count += count;
        }
   }
   cout << count << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanLines)

    // Read number of test cases
    scanner.Scan()
    T, _ := strconv.Atoi(scanner.Text())

    for t := 0; t < T; t++ {
        // Read N (length of string, not used here)
        scanner.Scan()
        // We read N but we actually don't need to use it
        // _ = scanner.Text()

        // Read binary string S
        scanner.Scan()
        S := scanner.Text()

        count0, count1 := 0, 0
        balancedPrefixes := 0

        for _, ch := range S {
            if ch == '0' {
                count0++
            } else {
                count1++
            }
            if count0 == count1 {
                balancedPrefixes++
            }
        }

        // Compute 2^balancedPrefixes
        result := 1
        for i := 0; i < balancedPrefixes; i++ {
            result *= 2
        }
        fmt.Println(result)
    }
}

Java solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class Codechef
{
    private static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws java.lang.Exception
    {
        FastScanner fs = new FastScanner();
        int t= fs.nextInt();
        for(int c=0; c<t; ++c)
        {
            int res = 1, n = fs.nextInt(), even = 0, odd = 0;
            String s = fs.next();
            for(char i : s.toCharArray())
            {
                if(i == '1')
                    ++odd;
                else
                    ++even;
                if(odd == even) res <<= 1;
            }
            out.println(res);
        }
        out.close();
    }
    
    static class FastScanner
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        
        String next()
        {
            while(!st.hasMoreTokens())
            {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {}
            }
            return st.nextToken();
        }
        
        int nextInt()
        {
            return Integer.parseInt(next());
        }
        
        long nextLong()
        {
            return Long.parseLong(next());
        }
    }
}

JavaScript solution:
// your code goes here
function analyzeSignalEquilibrium() {
  const signalReadings = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  let readingIndex = 0;
  const dataSets = parseInt(signalReadings[readingIndex++]);

  for (let setIteration = 0; setIteration < dataSets; setIteration++) {
    const signalLength = parseInt(signalReadings[readingIndex++]);
    const signalSequence = signalReadings[readingIndex++];

    let positiveSignals = 0;
    let negativeSignals = 0;
    let stablePoints = 0;

    for (let signalIndex = 0; signalIndex < signalLength; signalIndex++) {
      const currentSignal = signalSequence[signalIndex];
      if (currentSignal === '0') {
        positiveSignals++;
      } else {
        negativeSignals++;
      }

      if (positiveSignals === negativeSignals) {
        stablePoints++;
      }
    }

    const outcomePossibilities = Math.round(Math.pow(2, stablePoints));
    console.log(outcomePossibilities);
  }
}

analyzeSignalEquilibrium();

Python solution:
def solve_case(s):
    zeros = ones = 0
    balanced_prefixes = 0

    for ch in s:
        if ch == '0':
            zeros += 1
        else:
            ones += 1
        if zeros == ones:
            balanced_prefixes += 1

    return pow(2, balanced_prefixes)

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        S = input().strip()
        result = solve_case(S)
        print(result)

if __name__ == "__main__":
    main()

Ruby solution:
def count_possible_strings(s)
  zeros = 0
  ones = 0
  balanced_count = 0

  s.each_char do |c|
    if c == '0'
      zeros += 1
    else
      ones += 1
    end
    balanced_count += 1 if zeros == ones
  end

  balanced_count.zero? ? 1 : 2 ** balanced_count
end

def process_input
  input = $stdin.read.split("\n")
  idx = 0
  test_cases = input[idx].to_i
  idx += 1

  test_cases.times do
    n = input[idx].to_i
    idx += 1
    s = input[idx]
    idx += 1
    puts count_possible_strings(s)
  end
end

process_input