Given an array arr[] of either entirely positive integers or entirely negative integers except for one number. The task is to find that number.
Examples:
Input: arr[] = {3, 5, 2, 8, -7, 6, 9}
Output: -7
Explanation: Except -7 all the numbers in arr[] are positive integers.Input: arr[] = {-3, 5, -9}
Output: 5
Brute Force Approach:
A brute force approach to solve this problem would be to iterate over each element of the array and check whether it is positive or negative. We can keep track of the number of positive and negative elements in the array. Once we have this information, we can simply return the element that is different from the others.
Below is the implementation of the above approach:
C++
#include <iostream> using namespace std; int find( int * a, int N) { int i, pos_count = 0, neg_count = 0; for (i = 0; i < N; i++) { if (a[i] > 0) { pos_count++; } else { neg_count++; } } if (pos_count == 1) { for (i = 0; i < N; i++) { if (a[i] > 0) { return a[i]; } } } else if (neg_count == 1) { for (i = 0; i < N; i++) { if (a[i] < 0) { return a[i]; } } } return -1; } int main() { int arr[] = { 3, 5, 2, 8, -7, 6, 9 }; int N = sizeof (arr) / sizeof (arr[0]); cout << find(arr, N); return 0; } |
Java
import java.util.*; public class Main { public static int find( int [] a, int N) { int pos_count = 0 , neg_count = 0 ; for ( int i = 0 ; i < N; i++) { if (a[i] > 0 ) { pos_count++; } else { neg_count++; } } if (pos_count == 1 ) { for ( int i = 0 ; i < N; i++) { if (a[i] > 0 ) { return a[i]; } } } else if (neg_count == 1 ) { for ( int i = 0 ; i < N; i++) { if (a[i] < 0 ) { return a[i]; } } } return - 1 ; } public static void main(String[] args) { int [] arr = { 3 , 5 , 2 , 8 , - 7 , 6 , 9 }; int N = arr.length; System.out.println(find(arr, N)); } } |
Python3
def find(a, N): pos_count = 0 neg_count = 0 for i in range (N): if a[i] > 0 : pos_count + = 1 else : neg_count + = 1 if pos_count = = 1 : for i in range (N): if a[i] > 0 : return a[i] elif neg_count = = 1 : for i in range (N): if a[i] < 0 : return a[i] return - 1 arr = [ 3 , 5 , 2 , 8 , - 7 , 6 , 9 ] N = len (arr) print (find(arr, N)) |
C#
using System; public class Program { public static int Find( int [] a, int N) { // Count the number of positive and negative elements in the array. int posCount = 0; int negCount = 0; for ( int i = 0; i < N; i++) { if (a[i] > 0) { posCount++; } else { negCount++; } } // If there is exactly one positive element, return it. if (posCount == 1) { for ( int i = 0; i < N; i++) { if (a[i] > 0) { return a[i]; } } } // If there is exactly one negative element, return it. if (negCount == 1) { for ( int i = 0; i < N; i++) { if (a[i] < 0) { return a[i]; } } } // If there is no single element, return -1. return -1; } public static void Main() { int [] arr = { 3, 5, 2, 8, -7, 6, 9 }; int N = arr.Length; Console.WriteLine(Find(arr, N)); } } // This code is contributed by shivamgupta310570 |
Javascript
function find(a, N) { let pos_count = 0; let neg_count = 0; for (let i = 0; i < N; i++) { if (a[i] > 0) { pos_count++; } else { neg_count++; } } if (pos_count === 1) { for (let i = 0; i < N; i++) { if (a[i] > 0) { return a[i]; } } } else if (neg_count === 1) { for (let i = 0; i < N; i++) { if (a[i] < 0) { return a[i]; } } } return -1; } const arr = [3, 5, 2, 8, -7, 6, 9]; const N = arr.length; console.log(find(arr, N)); |
-7
Time Complexity: O(N^2)
Space Complexity: O(1)
Approach: The given problem can be solved by just comparing the first three numbers of arr[]. After that apply Linear Search and find the number. Follow the steps below to solve the problem.
- If the size of arr[] is smaller than 3, then return 0.
- Initialize the variables Cp and Cn.
- Where Cp = Count of positive integers and Cn = Count of negative integers.
- Iterate over the first 3 element
- If (arr[i]>0), Increment Cp by 1.
- Else Increment Cn by 1.
- Cp can be 2 or 3 and similarly, Cn can also either 2 or 3.
- If Cp<Cn, then the single element is positive, apply linear search and find it.
- If Cn<Cp, then the single element is negative, apply linear search and find it.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to return the single element int find( int * a, int N) { // Size can not be smaller than 3 if (N < 3) return 0; // Initialize the variable int i, Cp = 0, Cn = 0; // Check the single element is // positive or negative for (i = 0; i < 3; i++) { if (a[i] > 0) Cp++; else Cn++; } // Check for positive single element if (Cp < Cn) { for (i = 0; i < N; i++) if (a[i] > 0) return a[i]; } // Check for negative single element else { for (i = 0; i < N; i++) if (a[i] < 0) return a[i]; } } // Driver Code int main() { int arr[] = { 3, 5, 2, 8, -7, 6, 9 }; int N = sizeof (arr) / sizeof (arr[0]); cout << find(arr, N); } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to return the single element static int find( int []a, int N) { // Size can not be smaller than 3 if (N < 3 ) return 0 ; // Initialize the variable int i, Cp = 0 , Cn = 0 ; // Check the single element is // positive or negative for (i = 0 ; i < 3 ; i++) { if (a[i] > 0 ) Cp++; else Cn++; } // Check for positive single element if (Cp < Cn) { for (i = 0 ; i < N; i++) if (a[i] > 0 ) return a[i]; } // Check for negative single element else { for (i = 0 ; i < N; i++) if (a[i] < 0 ) break ; } return a[i]; } // Driver Code public static void main(String args[]) { int []arr = { 3 , 5 , 2 , 8 , - 7 , 6 , 9 }; int N = arr.length; System.out.println(find(arr, N)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# python program for the above approach # Function to return the single element def find(a, N): # Size can not be smaller than 3 if (N < 3 ): return 0 # Initialize the variable Cp = 0 Cn = 0 # Check the single element is # positive or negative for i in range ( 0 , 3 ): if (a[i] > 0 ): Cp + = 1 else : Cn + = 1 # Check for positive single element if (Cp < Cn): for i in range ( 0 , N): if (a[i] > 0 ): return a[i] # Check for negative single element else : for i in range ( 0 , N): if (a[i] < 0 ): return a[i] # Driver Code if __name__ = = "__main__" : arr = [ 3 , 5 , 2 , 8 , - 7 , 6 , 9 ] N = len (arr) print (find(arr, N)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; class GFG { // Function to return the single element static int find( int []a, int N) { // Size can not be smaller than 3 if (N < 3) return 0; // Initialize the variable int i, Cp = 0, Cn = 0; // Check the single element is // positive or negative for (i = 0; i < 3; i++) { if (a[i] > 0) Cp++; else Cn++; } // Check for positive single element if (Cp < Cn) { for (i = 0; i < N; i++) if (a[i] > 0) return a[i]; } // Check for negative single element else { for (i = 0; i < N; i++) if (a[i] < 0) break ; } return a[i]; } // Driver Code public static void Main() { int []arr = { 3, 5, 2, 8, -7, 6, 9 }; int N = arr.Length; Console.Write(find(arr, N)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for the above approach // Function to return the single element function find(a, N) { // Size can not be smaller than 3 if (N < 3) return 0; // Initialize the variable let i, Cp = 0, Cn = 0; // Check the single element is // positive or negative for (i = 0; i < 3; i++) { if (a[i] > 0) Cp++; else Cn++; } // Check for positive single element if (Cp < Cn) { for (i = 0; i < N; i++) if (a[i] > 0) return a[i]; } // Check for negative single element else { for (i = 0; i < N; i++) if (a[i] < 0) return a[i]; } } // Driver Code let arr = [ 3, 5, 2, 8, -7, 6, 9 ]; let N = arr.length; document.write(find(arr, N)); // This code is contributed Samim Hossain Mondal. </script> |
-7
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!