Problem Statement

Input Format

Constraints

\1ドル≤N<100\$

\$N % 2 = 1\$ (N is an odd number)

\0ドル≤A_{i}≤100,∀i∈[1,N]\$

Output Format

Solution

• I don't think that the information like N is odd or maximum limit of 100 is related to my solution. Is there some optimizations I am missing?
• What about the space complexity? I think it's \$O(N)\$ + size of the histogram.
• Runtime seems linear i.e \$O(N)\$.

Solution 2

Problem Statement

Input Format

Constraints

1 ≤ N < 100

N % 2 = 1 (i.e. N is an odd number)

0 ≤ Ai ≤ 100, ∀ i ∈ [1,N]

Output Format

Solution

• I don't think that the information like N is odd or maximum limit of 100 is related to my solution. Is there some optimization I am missing?
• What about the space complexity? I think it's O(N) + size of the histogram.
• Runtime seems linear i.e O(N).

Solution 2

Problem Statement

There are N integers in an array A. All but one integer occur in pairs. Your task is to find the number that occurs only once.

Input Format

The first line of the input contains an integer N, indicating the number of integers. The next line contains N space-separated integers that form the array A.

Constraints

\1ドル≤N<100\$

\$N % 2 = 1\$ (N is an odd number)

\0ドル≤A_{i}≤100,∀i∈[1,N]\$

Output Format

Output S, the number that occurs only once.

Solution

#!/usr/bin/py
from collections import Counter
def histogram(ary):
 """ Creates a histogram of the given array.
 Args:
 ary: The array.
 Returns:
 The dictionary with key as number and value as count.
 """
 return Counter(ary)
def lonelyinteger(ary):
 """ Finds the unique element in the array.
 Args:
 ary: The input array.
 Returns:
 Number or None
 """
 for frequency in histogram(ary).items():
 if frequency[1] == 1:
 return frequency[0]
 return None
if __name__ == '__main__':
 a = int(raw_input())
 b = map(int, raw_input().strip().split(" "))
 print lonelyinteger(b)

The solution works perfectly fine. But in the process of learning problem-solving, I am interested in a few things:

• I don't think that the information like N is odd or maximum limit of 100 is related to my solution. Is there some optimizations I am missing?
• What about the space complexity? I think it's \$O(N)\$ + size of the histogram.
• Runtime seems linear i.e \$O(N)\$.

Problem Statement

There are N integers in an array A. All but one integer occur in pairs. Your task is to find the number that occurs only once.

Input Format

The first line of the input contains an integer N, indicating the number of integers. The next line contains N space-separated integers that form the array A.

Constraints

\1ドル≤N<100\$

\$N % 2 = 1\$ (N is an odd number)

\0ドル≤A_{i}≤100,∀i∈[1,N]\$

Output Format

Output S, the number that occurs only once.

Solution

#!/usr/bin/py
from collections import Counter
def histogram(ary):
 """ Creates a histogram of the given array.
 Args:
 ary: The array.
 Returns:
 The dictionary with key as number and value as count.
 """
 return Counter(ary)
def lonelyinteger(ary):
 """ Finds the unique element in the array.
 Args:
 ary: The input array.
 Returns:
 Number or None
 """
 for frequency in histogram(ary).items():
 if frequency[1] == 1:
 return frequency[0]
 return None
if __name__ == '__main__':
 a = int(raw_input())
 b = map(int, raw_input().strip().split(" "))
 print lonelyinteger(b)

The solution works perfectly fine. But in the process of learning problem-solving, I am interested in a few things:

• I don't think that the information like N is odd or maximum limit of 100 is related to my solution. Is there some optimizations I am missing?
• What about the space complexity? I think it's \$O(N)\$ + size of the histogram.
• Runtime seems linear i.e \$O(N)\$.

Solution 2

It includes the factors like why N should be odd.

Example: 1 ^ 1 ^ 2 ^ 2 ^ 3

#!/usr/bin/py
def lonelyinteger(a):
 res = 0
 for each in a:
 res ^= each
 return res
 
if __name__ == '__main__':
 a = input()
 b = map(int, raw_input().strip().split(" "))
 print lonelyinteger(b)

Problem Statement

There are N integers in an array A. All but one integer occur in pairs. Your task is to find the number that occurs only once.

Input Format

The first line of the input contains an integer N, indicating the number of integers. The next line contains N space-separated integers that form the array A.

Constraints

\1ドル≤N<100\$

\$N % 2 = 1\$ (N is an odd number)

\0ドル≤A_{i}≤100,∀i∈[1,N]\$

Output Format

Output S, the number that occurs only once.

Solution

#!/usr/bin/py
from collections import Counter
def histogram(ary):
 """ Creates a histogram of the given array.
 Args:
 ary: The array.
 Returns:
 The dictionary with key as number and value as count.
 """
 return Counter(ary)
def lonelyinteger(ary):
 """ Finds the unique element in the array.
 Args:
 ary: The input array.
 Returns:
 Number or None
 """
 for frequency in histogram(ary).items():
 if frequency[1] == 1:
 return frequency[0]
 return None
if __name__ == '__main__':
 a = int(raw_input())
 b = map(int, raw_input().strip().split(" "))
 print lonelyinteger(b)

The solution works perfectly fine. But in the process of learning problem solving I am interested in few things.

• I don't think that the information like N is odd or maximum limit of 100 is related to my soltuion, is there some optimizations I am missing?
• What about the space complexity? I think its \$O(N)\$ + size of the histogram.
• Run time seems linear i.e \$O(N)\$.

Problem Statement

There are N integers in an array A. All but one integer occur in pairs. Your task is to find the number that occurs only once.

Input Format

The first line of the input contains an integer N, indicating the number of integers. The next line contains N space-separated integers that form the array A.

Constraints

\1ドル≤N<100\$

\$N % 2 = 1\$ (N is an odd number)

\0ドル≤A_{i}≤100,∀i∈[1,N]\$

Output Format

Output S, the number that occurs only once.

Solution

#!/usr/bin/py
from collections import Counter
def histogram(ary):
 """ Creates a histogram of the given array.
 Args:
 ary: The array.
 Returns:
 The dictionary with key as number and value as count.
 """
 return Counter(ary)
def lonelyinteger(ary):
 """ Finds the unique element in the array.
 Args:
 ary: The input array.
 Returns:
 Number or None
 """
 for frequency in histogram(ary).items():
 if frequency[1] == 1:
 return frequency[0]
 return None
if __name__ == '__main__':
 a = int(raw_input())
 b = map(int, raw_input().strip().split(" "))
 print lonelyinteger(b)

The solution works perfectly fine. But in the process of learning problem-solving, I am interested in a few things:

• I don't think that the information like N is odd or maximum limit of 100 is related to my solution. Is there some optimizations I am missing?
• What about the space complexity? I think it's \$O(N)\$ + size of the histogram.
• Runtime seems linear i.e \$O(N)\$.