GeeksforGeeks questions

.geeks_for_geeks

minimum-count-of-0s-to-be-removed-from-given-binary-string-to-make-all-1s-occurs-consecutively.py

# https://www.geeksforgeeks.org/minimum-count-of-0s-to-be-removed-from-given-binary-string-to-make-all-1s-occurs-consecutively/

# s = "010001011"
s = "011110000"
first_one = 0
last_one = len(s) - 1
zero_count = 0

while s[first_one] == "0":
    first_one += 1

while s[last_one] == "0":
    last_one -= 1

for i in range(first_one + 1, last_one):
    if s[i] == "0":
        zero_count += 1

print(zero_count)

rearrange-array-to-find-k-using-binary-search-algorithm-without-sorting.py

# https://www.geeksforgeeks.org/rearrange-array-to-find-k-using-binary-search-algorithm-without-sorting/


def binary_search(arr, n):
    l = 0
    r = len(arr) - 1
    mid = (r + l) // 2

    while r >= l:
        if arr[mid] > n:
            r = mid - 1
        elif arr[mid] < n:
            l = mid + 1

        mid = (r + l) // 2

        if arr[mid] == n:
            print("Found!")
            return

    print("Not found!")


def binary_search_arrange(arr, n):
    n_pos = 0
    for i in range(len(arr)):
        if arr[i] == n:
            n_pos = i
            break
    print(f"n_pos        {n_pos}\n")

    l = 0
    print(f"l            {l}")
    r = len(arr) - 1
    print(f"r            {r}")
    mid = (r + l) // 2
    print(f"mid          {mid}")
    new_arr = list(arr)
    print(f"new_arr      {new_arr}")
    print(f"new_arr[mid] {new_arr[mid]}\n")

    while r >= l:
        if (mid > n_pos) and (new_arr[mid] < n):
            for i in range(len(new_arr)):
                if new_arr[i] > n:
                    print(f"switch: {new_arr[i]} ⇆ {new_arr[mid]}")
                    new_arr[i], new_arr[mid] = new_arr[mid], new_arr[i]
                    print(f"new_arr      {new_arr}\n")
                    break
        elif (mid < n_pos) and (new_arr[mid] > n):
            for i in range(len(new_arr)):
                if new_arr[i] < n:
                    print(f"switch: {new_arr[i]} ⇆ {new_arr[mid]}")
                    new_arr[i], new_arr[mid] = new_arr[mid], new_arr[i]
                    print(f"new_arr      {new_arr}\n")
                    break

        if new_arr[mid] > n:
            print("new_arr[mid] > k")
            r = mid - 1
        elif new_arr[mid] < n:
            print("new_arr[mid] < k")
            l = mid + 1
        else:
            print("new_arr[mid] == k")
            return new_arr

        mid = (r + l) // 2

        print(f"l            {l}")
        print(f"r            {r}")
        print(f"mid          {mid}")
        print(f"new_arr      {new_arr}")
        print(f"new_arr[mid] {new_arr[mid]}\n")


# fmt: off
# arr = [10, 7, 2, 5, 3, 8]
arr = [36, 40,  5, 21, 19, 33,  2, 45, 23,  4,
        7, 25, 11, 24, 29, 32, 46, 15, 22,  6,
       44, 14, 13, 28, 26, 47, 34, 38,  1, 49]
# fmt: on
print(f"arr          {arr}")
# k = 7
k = 22
print(f"k            {k}")

new_arr = binary_search_arrange(arr, k)
print(f"new_arr {new_arr}")

print("binary_search")
binary_search(new_arr, k)

sort-the-given-array-in-spiral-manner-starting-from-the-center.py

# https://www.geeksforgeeks.org/sort-the-given-array-in-spiral-manner-starting-from-the-center/


def bubble_sort_left_right(arr, ord, start, stop):
    arr_cp = list(arr)
    step = 1

    for i in range(start, stop, step):
        for j in range(start, stop - i, step):
            if ord:  # True - asc
                if arr_cp[j] > arr_cp[j + step]:
                    arr_cp[j], arr_cp[j + step] = (
                        arr_cp[j + step],
                        arr_cp[j],
                    )
            else:  # False - desc
                if arr_cp[j] < arr_cp[j + step]:
                    arr_cp[j], arr_cp[j + step] = (
                        arr_cp[j + step],
                        arr_cp[j],
                    )
    return arr_cp


def bubble_sort_right_left(arr, ord, start, stop):
    arr_cp = list(arr)
    step = -1

    for i in range(start, stop, step):
        for j in range(start, stop - i + start, step):
            if ord:  # True - asc
                if arr_cp[j + step] > arr_cp[j]:
                    arr_cp[j], arr_cp[j + step] = (
                        arr_cp[j + step],
                        arr_cp[j],
                    )
            else:  # False - desc
                if arr_cp[j + step] < arr_cp[j]:
                    arr_cp[j], arr_cp[j + step] = (
                        arr_cp[j + step],
                        arr_cp[j],
                    )
    return arr_cp


def bubble_sort_left_right_first_pass(arr, ord, start, stop):
    arr_cp = list(arr)
    step = 1

    for j in range(start, stop, step):
        if ord:  # True - asc
            if arr_cp[j] > arr_cp[j + step]:
                arr_cp[j], arr_cp[j + step] = (
                    arr_cp[j + step],
                    arr_cp[j],
                )
        else:  # False - desc
            if arr_cp[j] < arr_cp[j + step]:
                arr_cp[j], arr_cp[j + step] = (
                    arr_cp[j + step],
                    arr_cp[j],
                )
    return arr_cp


def bubble_sort_right_left_first_pass(arr, ord, start, stop):
    arr_cp = list(arr)
    step = -1

    for j in range(start, stop, step):
        if not ord:  # True - asc
            if arr_cp[j] > arr_cp[j + step]:
                arr_cp[j], arr_cp[j + step] = (
                    arr_cp[j + step],
                    arr_cp[j],
                )
        else:  # False - desc
            if arr_cp[j] < arr_cp[j + step]:
                arr_cp[j], arr_cp[j + step] = (
                    arr_cp[j + step],
                    arr_cp[j],
                )
    return arr_cp


def bubble_sort_pass(arr, start, stop):
    arr_cp = list(arr)
    step = -1 if start > stop else 1

    for j in range(start, stop, step):
        if arr_cp[j] < arr_cp[j + step]:
            arr_cp[j], arr_cp[j + step] = (
                arr_cp[j + step],
                arr_cp[j],
            )

    return arr_cp


def spiral_sort(arr):
    arr_cp = list(arr)
    start = len(arr_cp) - 1
    stop = 0

    if len(arr) % 2 == 0:
        start, stop = stop, start

    while start != stop:
        arr_cp = bubble_sort_pass(arr_cp, start, stop)
        delta = start - stop
        stop += delta // abs(delta)
        start, stop = stop, start

    return arr_cp


arr = [4, 5, 3, 7, 6, 9, 7, 1]

print(spiral_sort(arr))