CODEWITHSUNDEEP
pythonalgorithmoptimizationdata-structuresbit-shift
Eric Hasegawa
Eric Hasegawa

Reputation: 659

Calculate circular shift pairs in a list

A circular shift moves some of the digits in a number to the beginning of the number, and shifts all other digits forward to the next position. For example, all of the circular shifts of 564 are 564, 645, 456.

Lets say two numbers of equal length a and b are circular pairs if a can become b via circular shifting. Using the example above, the circular pairs of 564 are 645 and 456.

Given an array of positive integers nums, count the number of circular pairs i and j where 0 <= i < j < len(nums)

For example, circular_shifts([13, 5604, 31, 2, 13, 4560, 546, 654, 456]) should return 5. With the pairs being (13, 31), (13, 13), (5604, 4560), (31, 13), (546, 654).

I wrote a brute force solution that saves all circular shifts of a number in a dictionary shifts and for every number num in nums, I check all the following numbers and if a number num2 the same digits as num, I see if num2 is in num's circular shifts. If it is then I added this to the total count.

Unfortunately this algorithm runs too slowly and times out, I'm looking for a faster way to solve this problem can anyone think of optimizations, clever tricks, or other strategies to speed this up?

Upvotes: 2

Views: 2762

Answers (4)

Anshuman Kirty
Anshuman Kirty

Reputation: 166

from collections import Counter

def big(num):
    max_num = num
    s = str(num)
    for _ in s:
        x = int(s[-1] + s[0:-1])
        if x > max_num:
            max_num = x
        s = s[-1] + s[0:-1]  # Update s for the next iteration
    return max_num
        
mylist = [1, 1, 1, 1]  # Example list
circs = [big(z) for z in mylist]

c = Counter(circs)

total = 0
for i in c:
    if c[i] > 1:
        total += c[i] * (c[i] - 1) // 2
print(total)

Upvotes: 1

Mahesh Jamdade
Mahesh Jamdade

Reputation: 20319

Here's my solution, where we

  1. iterate through the list
  2. rotate each number length-1 times
  3. and print only if the number is found in the remaining list
    numbers = [13, 5604, 31, 2, 13, 4560, 546, 654, 456]
    # shift_pairs = [(13,31),(13,13),(5604,4560),(31,13),(546,654)]
    pairsFound = 0
    for i in range(len(numbers)):
        number = numbers[i]
        length = len(str(number))
        numberToRotate = number
        shift_remaining = length - 1
        temp_list = numbers[i+1:]
        while(shift_remaining >= 0):
            t_remainder = numberToRotate % 10 # 4
            numberToRotate = numberToRotate // 10 # 560
            numberToRotate = numberToRotate + t_remainder * 10 **(length-1) # 4560
            # we should also check for length for cases like 4560, where on a shift we get 456
            if(numberToRotate in temp_list and len(str(numberToRotate)) == length):
                print("({},{})".format(number,numberToRotate))
                pairsFound += 1
            shift_remaining -= 1
    print("no of pairs:", pairsFound)

output

(13,31)
(13,13)
(5604,4560)
(31,13)
(546,654)
no of pairs: 5

Upvotes: 0

user19077881
user19077881

Reputation: 5450

Not very elegant as not much time but the following should be faster as does not repeatedly access the list. Shifting is done on string for simplicity.

from collections import Counter

def big(num):
    max = num
    s = str(num)
    for _ in s:
        x = int(s[-1] + s[0:-1])
        if x > max:
            max = x
    return max
        
circs = [big(z) for z in mylist]

c = Counter(circs)

total = 0
for i in c:
    if c[i] > 1:
        total += c[i]
print(total)

Upvotes: 3

Matt Timmermans
Matt Timmermans

Reputation: 59253

  1. Replace every number in the array with its greatest cyclic shift. 1234, for example, would become 4123
  2. Count the occurrences of each resulting number
  3. If a number occurs n times, that represents n(n-1)/2 cyclic shift pairs. Add them all up.

Upvotes: 3

Related Questions