S to T
Source: codechef
Difficulty: 1640

S to T
You are given$2$binary strings$S$and$T$, of length$N$. Here, binary strings means both$S$and$T$contain only$0$s and$1$s.
Is it possible to make$S$equal to$T$using at most$3 \cdot N$such operations:
Choose$1 \le i < N$such that$S_i = 1$and then flip$S_{i + 1}$, i.e. change it from$0$to$1$or$1$to$0$.
If it is possible, please print an operation sequence. If it is impossible, print$-1$. You do not need to minimize the length of the sequence. If multiple sequences are possible, all will be accepted.
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 contains$N$- the length of the string.
The second line contains$S$- the initial string.
The third line contains$T$- the target string.
Output Format
For each test case, print the following:
if it is possible, print:
on the first line, print$K (0 \le K \le 3 \cdot N)$the number of operations performed.
on the second line, print$K$integers$X_1, X_2, ..., X_K (1 \le X_i < N)$the indices chosen for each of the$K$operations in that order.
if it is not possible, print$-1$.
Constraints$1 \le T \le 10^4$$2 \le N \le 2 \cdot 10^5$$|S| = |T| = N$$S_i \in \{0, 1\}$$T_i \in \{0, 1\}$The sum of$N$over all test cases does not exceed$2 \cdot 10^5$.
Sample 1:
Explanation:
Test Case 1
: In the first test case, we first choose$i = 3$(note$S_3 = 1$) and flip$S_4$to get$0111$. Then, we choose$i = 2$(note$S_2 = 1$) and flip$S_3$to get$0101$, which equals$T$.
Test Case 2
: It can be proven to be impossible.

Sample Input:
4
4
0110
0101
2
01
10
2
10
11
2
00
00

Sample Output:
2
3 2
-1
1
1
0

C++ solution:
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f(i, n) for (ll i = 0; i < n; i++)
#define ia(a, n) \
    ll a[n];     \
    f(i, n) cin >> a[i]
#define iv(v, n)     \
    vector<ll> v(n); \
    f(i, n) cin >> v[i]
#define MOD (1000000007)
#define INF 1000000000000000000LL
#define nl '\n'
#define yes cout << "YES\n"
#define no cout << "NO\n"

void solve(){
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    int first = -1;
    vector<int> v;
    for(int i=0; i<n; i++){
        if(s[i] != t[i]){
            cout << -1 << nl;
            return;
        }
        if(s[i] == '1'){
            first = i;
            break;
        }
    }
    if(first == -1){
        cout << 0 << nl;
        return;
    }
    for(int i=first+1; i<n; i++){
        if(s[i] != '1'){
            v.emplace_back(i);
            s[i] = '1';
        }
    }
    for(int i=n-1; i>=first+1; i--){
        if(s[i] != t[i]){
            v.emplace_back(i);
        }
    }
    cout << v.size() << nl;
    for(int x : v){
        cout << x << ' ';
    }
    cout << nl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    int t;
    cin >> t;
    while(t--){
        solve();
    }
return 0;   
}

Go solution:
package main

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

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var testCases int
    fmt.Fscan(in, &testCases)
    for tc := 0; tc < testCases; tc++ {
        var length int
        fmt.Fscan(in, &length)

        var source, dest string
        fmt.Fscan(in, &source, &dest)

        ops, ok := computeSwaps(length, source, dest)
        if !ok {
            fmt.Fprintln(out, -1)
            continue
        }

        fmt.Fprintln(out, len(ops))
        if len(ops) > 0 {
            for i, pos := range ops {
                out.WriteString(strconv.Itoa(pos))
                if i+1 < len(ops) {
                    out.WriteByte(' ')
                }
            }
            out.WriteByte('\n')
        }
    }
}

func computeSwaps(n int, source, dest string) ([]int, bool) {
    if source[0] != dest[0] {
        return nil, false
    }

    valid := true
    seenOne := source[0] == '1'
    for i := 1; i < n && valid; i++ {
        if !seenOne && source[i] != dest[i] {
            valid = false
        }
        if source[i] == '1' {
            seenOne = true
        }
    }
    if !valid {
        return nil, false
    }

    arr := []byte(source)
    var ops []int

    for i := n - 1; i >= 1; i-- {
        if arr[i] == dest[i] {
            continue
        }
        if arr[i-1] == '0' {
            j := i - 2
            for j >= 0 && arr[j] == '0' {
                j--
            }
            if j < 0 {
                valid = false
                break
            }
            for k := j; k <= i-2; k++ {
                ops = append(ops, k+1)
                arr[k+1] ^= 1
            }
        }
        ops = append(ops, i)
        arr[i] ^= 1
    }

    if !valid || string(arr) != dest {
        return nil, false
    }
    return ops, true
}

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

public class Main {

  public static boolean isprime(long x) {
    if (x == 2 || x == 3 || x == 5) {
      return true;
    }
    for (long i = 2; i <= Math.sqrt(x); i++) {
      if (x % i == 0) {
        return false;
      }
    }
    return true;
  }

  public static long gcd(long a, long b) {
    if (a == 0) {
      return b;
    }
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }

  static void sort(long[] a) {
    ArrayList<Long> l = new ArrayList<>();
    for (long i : a) {
      l.add(i);
    }
    Collections.sort(l);
    for (int i = 0; i < a.length; i++) {
      a[i] = l.get(i);
    }
  }

  static void sortInt(int[] a) {
    ArrayList<Integer> l = new ArrayList<>();
    for (int i : a) {
      l.add(i);
    }
    Collections.sort(l);
    for (int i = 0; i < a.length; i++) {
      a[i] = l.get(i);
    }
  }

  static long mod = 1_000_000_000 + 7;

  static long lm(long i, long lcm) {
    return (i * (lcm)) / (gcd(i, lcm));
  }

  static long fact[] = new long[200001];

  static long bipow(long x, long y) {
    long z = 1;
    while (y != 0) {
      if ((y & 1) != 0) {
        z = mul(z, x);
      }
      x = mul(x, x);
      y >>= 1;
    }
    return z;
  }

  static long mul(long n, long m) {
    return (n * m) % mod;
  }

  public static long inver(long x) {
    return bipow(x, mod - 2);
  }

  public static long find_combin(long m, long n) {
    long y = mul(fact[(int) (m - n)], fact[(int) n]);
    return mul(fact[(int) m], inver(y));
  }

  // public static class pair implements Comparable<pair> {
  //     long x;
  //     int y;
  //     public pair(long x, int y) {
  //         this.x = x;
  //         this.y = y;
  //     }
  //     @Override
  //     public int compareTo(pair a) {
  //         return (int) (a.x - this.x);
  //     }
  // }
  static Comparator<int[]> customComparator = new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b) {
      // First compare based on the values at index 0
      if (a[0] != b[0]) {
        return a[0] - b[0];
      } else {
        // If values at index 0 are equal, compare based on a[i][1] - a[i][0]
        return a[1] - a[0] - (b[1] - b[0]);
      }
    }
  };

  public static class pair implements Comparable<pair> {

    int x;
    int y;

    public pair(int x, int y) {
      this.x = x;
      this.y = y;
    }

    @Override
    public int compareTo(pair a) {
      if (this.x != a.x) {
        return Integer.compare(this.x, a.x);
      }
      return Integer.compare(this.y, a.y);
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner();

    int test_case = sc.nextInt();

    for (int ttt = 0; ttt < test_case; ttt++) {
      int n = sc.nextInt();

    
      // 10101
      // 11101
      // 10111
      // 10100

      String s = sc.next();
      String t=  sc.next();

      boolean tt = true;
      int ct = 0 ;

      int index = -1;

      for(int i = 0 ; i < n;i++){
        if(s.charAt(i)!=t.charAt(i)){
           if(ct==0){
             tt = false;
             break;
           }
           
           break;
        }
        if((s.charAt(i))=='1'){
          index  = i ;
          ct++;
        }
      }
        

      if(!tt){
        System.out.println("-1");continue;
      }

      if(index==-1){
        System.out.println(0);continue;
      }

      int res = 0 ;
      StringBuilder sb = new StringBuilder("");

      
      for(int i = index+1 ; i < n;i++){
           if(s.charAt(i)=='0'){
            sb.append((i)+" ");
            res++;
           }
      }

      for(int i = n-1 ; i > index ;i--){
        if(t.charAt(i)=='0'){
          sb.append((i)+" ");
          res++;
        }
      }

      // sb.append("\n");
      if(res==0){
      System.out.println(res);
      // System.out.print(sb);
      }
      else{
        System.out.println(res);
        System.out.println(sb);
      }
      
    }
  }


  public static class Scanner {

    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) {
        e.printStackTrace();
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    int[] readArray(int n) {
      int[] arr = new int[n];
      for (int i = 0; i < n; i++) {
        arr[i] = nextInt();
      }
      return arr;
    }

    long[] readLong(int n) {
      long[] arr = new long[n];
      for (int i = 0; i < n; i++) {
        arr[i] = nextLong();
      }
      return arr;
    }
  }
}

JavaScript solution:
'use strict';
const fs = require('fs');

function main() {
    const data = fs.readFileSync(0, 'utf-8').trim().split(/\s+/);
    let idx = 0;
    const TC = parseInt(data[idx++], 10);
    const result = [];

    for (let tc = 0; tc < TC; tc++) {
        const N = parseInt(data[idx++], 10);
        const S = data[idx++].split('');
        const Tgt = data[idx++].split('');

        if (S.join('') === Tgt.join('')) {
            result.push('0');
            continue;
        }

        const p0 = S.indexOf('1');
        if (p0 === -1) {
            result.push('-1');
            continue;
        }

        let ok = true;
        for (let i = 0; i <= p0; i++) {
            if (S[i] !== Tgt[i]) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            result.push('-1');
            continue;
        }

        const ops = [];
        for (let j = p0; j < N - 1; j++) {
            if (S[j + 1] === '0') {
                ops.push(j + 1);
                S[j + 1] = '1';
            }
        }

        for (let j = N - 1; j > p0; j--) {
            if (S[j] !== Tgt[j]) {
                ops.push(j);
                S[j] = S[j] === '0' ? '1' : '0';
            }
        }

        if (S.join('') !== Tgt.join('')) {
            result.push('-1');
        } else {
            result.push(String(ops.length));
            if (ops.length > 0) {
                result.push(ops.join(' '));
            }
        }
    }

    console.log(result.join('\n'));
}

main();

Python solution:
# Code by Sahil
# Problem: Bit-flip sequence to transform S into T
# Author: Sahil Arun Bhoite

import sys

def solve_Sahil():
    data = sys.stdin.read().split()
    sahil_T = int(data[0])
    sahil_idx = 1
    out_lines = []
    for _ in range(sahil_T):
        sahil_N = int(data[sahil_idx]); sahil_idx += 1
        sahil_S = list(data[sahil_idx]); sahil_idx += 1
        sahil_T_str = list(data[sahil_idx]); sahil_idx += 1

        sahil_ops = []
        # Step 1: make all bits in sahil_S into '1'
        for i in range(sahil_N - 1):
            if sahil_S[i] == '1' and sahil_S[i+1] == '0':
                sahil_ops.append(i+1)  # 1-based index
                sahil_S[i+1] = '1'

        # Step 2: work backwards to match sahil_T_str
        for i in range(sahil_N-1, 0, -1):
            if sahil_S[i] != sahil_T_str[i]:
                if sahil_S[i-1] == '1':
                    # direct flip at position i
                    sahil_ops.append(i)  # 1-based
                    sahil_S[i] = '1' if sahil_S[i] == '0' else '0'
                else:
                    # need to propagate a '1' from earlier
                    sahil_found = False
                    for j in range(i-2, -1, -1):
                        if sahil_S[j] == '1':
                            for k in range(j, i-1):
                                sahil_ops.append(k+1)
                                sahil_S[k+1] = '1' if sahil_S[k+1] == '0' else '0'
                            sahil_found = True
                            break
                    if not sahil_found:
                        out_lines.append("-1")
                        break
                    sahil_ops.append(i)
                    sahil_S[i] = '1' if sahil_S[i] == '0' else '0'
        else:
            # check first position
            if sahil_S[0] != sahil_T_str[0]:
                out_lines.append("-1")
            else:
                out_lines.append(str(len(sahil_ops)))
                out_lines.append(" ".join(map(str, sahil_ops)))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve_Sahil()

Ruby solution:
t = gets.to_i
t.times do
  n = gets.to_i
  s = gets.chomp.chars
  t = gets.chomp.chars
  ans = []
  
  if s[0] != t[0]
    puts -1
    next
  end

  # Forward pass: handle 0s in S that need to be 1s in T
  (1...n).each do |i|
    if s[i] == '0' && s[i-1] == '1'
      ans << i
      s[i] = '1'
    end
  end

  possible = true
  # Backward pass: adjust remaining differences
  (n-1).downto(1) do |i|
    if s[i] != t[i]
      if s[i-1] == '1'
        ans << i
        s[i] = t[i]
      else
        possible = false
        break
      end
    end
  end

  unless possible
    puts -1
    next
  end

  puts ans.size
  puts ans.join(' ') unless ans.empty?
end