0

I was practising Cracking the Coding Interview Questions and stumbled upon this question called isUnique, where the constraint is to check if a given string has duplicates without using any extra data structures. So, after trying out the brute-force method o(n^2), I learnt about the usage of a bit manipulation method wherein we can set a particular bit according to the ASCCI value of the particular character.

My doubt here is that, I know that a python integer takes up 32 bits of space which translates to a maximum value of 4294967296 or 2^32 but according to my implementation and the test case I used -> "Jake"

def isUniqueCheck(s):
  checker = 0 #Our counter variable
  flag = 0
  for i in range(len(s)):
    ascii_index = ord(s[i])
    if ascii_index >=97 and ascii_index <= 122:
      ascii_index -= 32
    value = checker & (1<<ascii_index)
    if(value>0):
      flag=1
      break
    checker = checker | (1<<ascii_index)
    # print(checker) -> To see set bit Values
  print('Unique') if (flag==0) else print('Duplicates Found')

The Checker variable gets set as follows:

  • For "j" checker = 1 << 74
  • For "a" checker = 1 << 65
  • For "k" checker = 1 << 75
  • For "e" checker = 1 << 69

All the above set bits exceeded the maximum integer value yet the code still works. I'd like to know the maximum left shift that can be done with an integer variable. Thanks in Advance.

Wadu Hek
  • 33
  • 6
  • 2
    Python uses multi-precision integers, so there's no practical limit to the size. – Barmar Jun 24 '21 at 15:44
  • 1
    integers in python has infinite precision so there's no upper limit. You can shift as long as want up to the memory limit of your PC. Try `123*45734` or `1 << 32768` – phuclv Jun 24 '21 at 15:45

0 Answers0