# Finding stray number in Dart(2.14) with O(n) Complexity

## Problem statement

You are given an *odd-length* array of integers, in which all of them are the same, except for one single number.

Complete the method which accepts such an array, and returns that single different number.

The input array will always be valid! (odd-length >= 3)

**Example**:

```
[1, 1, 2] ==> 2
[17, 17, 3, 17, 17, 17, 17] ==> 3
```

**Test**

```
import "package:test/test.dart";
import "package:solution/solution.dart";
void main() {
group("Fixed tests", () {
test('Testing for [1, 1, 2]', () {
expect(stray([1, 1, 2]), equals(2));
});
test('Testing for [17, 17, 3, 17, 17, 17, 17]', () {
expect(stray([17, 17, 3, 17, 17, 17, 17]), equals(3));
});
test('Testing for [8, 1, 1, 1, 1, 1, 1]', () {
expect(stray([8, 1, 1, 1, 1, 1, 1]), equals(8));
});
test('Testing for [1, 1, 1, 1, 1, 1, 0]', () {
expect(stray([1, 1, 1, 1, 1, 1, 0]), equals(0));
});
test('Testing for [0, 0, 0, 7, 0, 0, 0]', () {
expect(stray([0, 0, 0, 7, 0, 0, 0]), equals(7));
});
test('Testing for [-21, -21, -21, -21, -6, -21, -21]', () {
expect(stray([-21, -21, -21, -21, -6, -21, -21]), equals(-6));
});
});
}
```

## My Approach

```
int stray(List<int> numbers) {
if(numbers[0] != numbers[1]){
return numbers[0] == numbers[2] ? numbers[1] : numbers[0];
}
else {
int result = numbers.firstWhere((number) => number != numbers[0]);
return result;
}
}
```

**Reasoning:**

*Handling Different First Two Numbers:*

- If the first 2 numbers in the array are different, we compare the first number with the third number to identify the stray number and this step has a O(1) complexity.

`numbers[0] == numbers[2] ? numbers[1] : numbers[0];`

*2. Finding the Stray Number If First Two Numbers Are The Same*

- if the first 2 numbers are the same, the .firstWhere() method is used to find the first number in the list that is different. This method iterates through the elements and returns the first to satisfy the given condition, ensuring a O(n) complexity.
- Where n represents the length of numbers in the list, as for the worst case scenario, it would need to iterate through the whole list.

**Conclusion**

The overall time complexity is O(n) for finding the stray number.

## Wrapping Up

There you go! Let me know what better approach you have to solving the above problems. ;)

Problem statement source: Codewars

references to achieve solution: https://api.flutter.dev/flutter/dart-core/Iterable/firstWhere.html

# About Me

I am Zaahra, a Google Women Techmakers Ambassador who enjoy mentoring people and writing about technical contents that might help people in their developer journey. I also enjoy building stuffs to solve real life problems.

*To reach me:*

LinkedIn: https://www.linkedin.com/in/faatimah-iz-zaahra-m-0670881a1/

X (previously Twitter): _fz3hra

GitHub: https://github.com/fz3hra

Cheers,

Umme Faatimah-Iz-Zaahra Mujore | Google Women TechMakers Ambassador | Software Engineer