CONSEONE - EDITORIAL

editorial
, , , ,
1

PROBLEM LINK:

Contest

Setter: debrc

Tester: dustu_947 , mishra_roshan

Editorialist: debrc

DIFFICULTY:

Simple

PREREQUISITES:

Basic observations

PROBLEM:

Given a number N of D digits formed using at most 2 distinct decimal digits, convert it into a number of same digits by choosing a segment of same digits and change them to a segment of another digit any number of times. Find the minimum number of operation you need to perform to make the number with all digits same.

EXPLANATION

To convert the number to a number of same digits in minimum number of steps, its always better to change a segment to a segment of digits which is already present in that number, i.e. replace one of the digit’s all segments to segments of the other digit.
As the number is formed of 2 distinct digits, count the number of segments present for each digit.
Then return the minimum of the two.

TIME COMPLEXITY

Time complexity is O(D) for traversing the digits of the number.

SOLUTIONS:

Setter's Solution
C++ 
#include<bits/stdc++.h>
using namespace std;

int t, n, i, j, cnt1, cnt2;
char x, y;
char arr[1000100];

int main() {
    scanf("%d", &t);

    while(t--) {
        cnt1 = 0;
        cnt2 = 0;
        scanf("%s", &arr);
        n = strlen(arr);

        x = arr[0];
        cnt1++;

        for(i = 1; i < n; i++) {
            if(arr[i] != arr[i-1]) {
                if(arr[i]==x)
                    cnt1++;
                else
                    cnt2++;
            }
        }
        printf("%d\n", min(cnt1, cnt2));
    }
    return 0;
}
Python 
for _ in range(int(input())):
    n=input()
    digits=set()
    for i in n:
        digits.add(i)
    digits=list(digits)
    if len(digits)==1:
        print(0)
        continue
    one=digits[0]
    two=digits[1]
    flagOne=0
    countOne=0
    flagTwo=0
    countTwo=0
    for i in n:
        if i==two:
            flagTwo=1
        if i==one and flagTwo:
            flagTwo=0
            countTwo+=1
        if i==one:
            flagOne=1
        if i==two and flagOne:
            flagOne=0
            countOne+=1
    if flagOne:
        countOne+=1
    if flagTwo:
        countTwo+=1
    print(min(countOne,countTwo))
Tester's Solution
Java 
import java.util.*;
import java.io.*;

// public
class A {
    
    public static void main(String[] args) throws IOException {
        
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        l:
        while(t-- > 0) {
            char[] c = sc.next().toCharArray();
            int n = c.length;
            char u = c[n-1];
            int i = 0;
            int ans = 0;
            while(i < n) {
                boolean flag = false;
                while(i < n && c[i] != u) {
                    i++;
                    flag = true;
                }
                
                if (flag) ans++;
                
                if (c[i] == u) i++;
            }
            System.out.println(ans);
        }
        
        
    }
}

Feel free to Share your approach.
Suggestions are welcomed as always had been.