basic_algorithms/rearrange_array_digits.py at master · jagruti8/basic_algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
# -*- coding: utf-8 -*-
"""
Created on Fri Jul 31 07:45:36 2020

@author: JAGRUTI
"""

import random

def rearrange_digits(input_list):
    """
    Rearrange Array Elements so as to form two number such that their sum is maximum.
    Assumption: All array elements are in the range [0, 9]
    Args:
       input_list(list): Input List
    Returns:
       (int),(int): Two maximum sums
    """
    # sum is 0 if there are no elements
    if len(input_list) == 0:
        print("Numbers are:", 0, 0)
        return [0, 0]

    # sum is the only element present in the list
    if len(input_list) == 1:
        print("Numbers are:", input_list[0], 0)
        return [input_list[0], 0]

    # sort the list using randomized quick sort - O(nlog(n)) - Best and average case time complexity
    sorted_list = quick_sort(input_list, 0, len(input_list)-1)

    index = 0
    num_1 = ''
    num_2 = ''

    # join numbers alternately from odd and even positions for first and second number respectively
    while(index<len(sorted_list)):
        num_1 = str(sorted_list[index]) + str(num_1)

        # check if digit at even position exists
        if (index + 1)<len(sorted_list):
            num_2 = str(sorted_list[index+1]) + str(num_2)

        index += 2

    print("Numbers are:" ,int(num_1), int(num_2))
    return [int(num_1), int(num_2)]

# quick sort for sorting the array - tail recursive approach to have worst case time complexity of O(log(n)) - Idea from
# "https://www.geeksforgeeks.org/"

def quick_sort(array, low, high):

    while(low<high):

        pivot_index = sort_again(array, low, high)

        quick_sort(array, low, pivot_index-1)

        low = pivot_index + 1

    return array

def sort_again(array, low, high):

    # pick random element as pivot - randomized quick sort to have less chances of worst-case scenario - time complexity - O(n^2)
    randpivot = random.randrange(low, high)

    # swap pivot value with the highest index value
    swap(array, randpivot, high)

    left_index = low
    pivot_index = high

    # until pivot element reaches its correct position in the array - left-side elements smaller than equal to pivot and
    # right-side elements larger than pivot
    while(left_index!=pivot_index):

        if array[left_index]<=array[pivot_index]:
            left_index += 1
            continue
        # fill left_index position with the element to the left of pivot, shift pivot element to left and
        # get the left_index element to pivot position. Decrement the pivot index
        swap(array, left_index, pivot_index-1)
        swap(array, pivot_index, pivot_index-1)
        pivot_index -= 1

    return pivot_index

# function for swapping two elements
def swap(array, index1, index2):
    temp = array[index1]
    array[index1] = array[index2]
    array[index2] = temp

def test_function(test_case):
    output = rearrange_digits(test_case[0])
    solution = test_case[1]
    output_sum = sum(output)
    solution_sum = sum(solution)
    print("My solution: {}, Target: {}".format(output_sum, solution_sum))
    if output_sum == solution_sum:
        print("Pass")
    else:
        print("Fail")

# Edge cases
test_function([[], [0, 0]]) # Numbers are: 0 0 | My solution: 0, Target: 0 | Pass
test_function([[0], [0, 0]]) # Numbers are: 0 0 | My solution: 0, Target: 0 | Pass
test_function([[1], [1, 0]]) # Numbers are: 1 0 | My solution: 1, Target: 1 | Pass

# Normal cases
test_function([[1, 2, 3, 4, 5], [542, 31]]) # Numbers are: 531 42 | My solution: 573, Target: 573 | Pass
test_function([[4, 6, 2, 5, 9, 8], [964, 852]]) # Numbers are: 852 964 | My solution: 1816, Target: 1816 | Pass

# Large Lists
final_list = []
for i in range(10):
    final_list += [i for j in range(i+1)]
#print(final_list)
random.shuffle(final_list)
#print(final_list)
num1 = 9999988888777766655544433210
num2 = 999998888777766665554433221
test_function([final_list, [num1, num2]])
# Numbers are: 9999988888777766655544433210 999998888777766665554433221
# My solution: 10999987777555533321098866431, Target: 10999987777555533321098866431
# Pass