# Unique Characters

Problem: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

```def isUniqueChars(str):
#first sort the string O(nlgn)
sortedStr = "".join(sorted(str))

isUnique = True

#compare the consecutive characters O(n)
for i in range(len(sortedStr)-1):
if sortedStr[i] == sortedStr[i+1]:
isUnique = False

return isUnique

print isUniqueChars("Amber".lower())

def isUniqueChars2(str):
#considering the characters are ascii characters building an array for 256 characters acting as a hash table
arr = [0]*256
for c in str:
asciiValue = ord(c)
arr[asciiValue] += 1

isUnique = True

#checking for repeated characters O(1)
for entries in str:
if arr[ord(entries)] > 1:
isUnique = False
return isUnique

print isUniqueChars2("Amber".lower())

```

# Find two repeating elements in a given array

The problem is as follows:
Given an array with n+2 elements, all elements of the array are in range 1 to n and also all
elements occur only once except two numbers which occur twice. Find those two repeating numbers.

Sample Input: [4,2,4,5,2,3,1]
Sample Output: 2,4

```
arr = [4,2,4,5,2,3,1]

'''Using hash table concept
Complexity Time: O(n), Space: O(n)'''

def twiceOccurringElement(arr):
countarr = [0]* len(arr)

for entry in arr:
countarr[entry] += 1

elements = []
for i in range(len(countarr)):
if countarr[i] > 1:
elements.append(i)

return elements

print twiceOccurringElement(arr)

```

# Maximum repeated element

The problem is as follows:
Given an array of n numbers. Give an algorithm for finding the element which
appears maximum number of times in the array.

Sample Input: [3,2,1,2,2,2,3]
Sample Output: 2

```'''Using hashing
Complexity Space: O(n), Time: O(n)'''

arr = [3,2,1,2,2,2,3]

def maximumRepetition(arr):
numDict = {}
for entry in arr:
if entry in numDict:
numDict[entry] += 1
else:
numDict[entry] = 1

maxElement = 0
maxCount = 0
for entries in numDict:
if numDict[entries] > maxCount:
maxCount = numDict[entries]
maxElement = entries

return maxElement

print maximumRepetition(arr)

'''Improved method
Complexity Time O(n) Space: O(1)'''

n = len(arr) #This is supposed to be given

def maximumRepitionImproved(arr):
for i in range(len(arr)):
arr[arr[i]] += n

maxi = -1
maxValue = 0
for i in range(len(arr)):
if arr[i]/n > maxValue:
maxValue = arr[i]/n
maxi = i
return arr[maxi]

print maximumRepetition(arr)
```

# First element which is repeated

The problem is:
Given an array of n numbers give an algorithm for finding the first elementÂ in the array which is repeated.

Sample Input : [3,2,1,2,2,3]
Sample Output : 3

```
'''Using hashing technique
Complexity Time: O(n) Space: O(n)'''

def detectRepetition(arr):
numDict = {}

for i in range(len(arr)):
if arr[i] in numDict:
if numDict[arr[i]] < 0:
pass
else:
numDict[arr[i]] = -(numDict[arr[i]])
else:
numDict[arr[i]] = i+1

max = -100000000000000
repeatedentry = 0
for entry, pos in numDict.iteritems():
if pos < 0:
if pos > max:
max = pos
repeatedentry = entry

return repeatedentry

print detectRepetition(arr)

```

# Find The Missing Number

The problem is as follows:
We are given a list of n-1 integers and these integers are in the range of 1 to n.
There are no duplicates in the list. One of the integers is missing in the list.
Give an algorithm to find the missing integer.

Sample Input: [1,2,4,6,3,7,8]
Sample Output: 5

```arr = [1,2,4,6,3,7,8]

'''solution using brute force
Complexity Time: O(n^2) Space = O(1)'''

def findMissing(arr):
missingNumber = -1
for i in range(1,len(arr)):
if i in arr:
pass
else:
missingNumber = i
return missingNumber

print findMissing(arr)

'''solution using sorting
Complexity Time: O(nlogn) Space:O(1)'''

def findMissingUsingSorting(arr):
missingNumber = -1
arr.sort()
for i in range(len(arr)):

if arr[i] == i+1:
pass
else:
missingNumber = i+1
break
return missingNumber

print findMissing(arr)

'''solution using hashing technique
Complexity Time: O(n) Space O(n)'''

def findMissingUsingHashing(arr):
numberDict = {}
missingNumber = -1
for i in range(len(arr)+1):
numberDict[i+1] = 0

for i in arr:
numberDict[i] = 1

for i in numberDict:
if numberDict[i] == 0:
missingNumber = i

return missingNumber

print findMissing(arr)

```