Kth odd number in an array
Given an array arr[] and an integer K, the task is to find the Kth odd element from the given array.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}, K = 2
Output: 3
3 is the 2nd odd element from the given arrayInput: arr[] = {2, 4, 6, 18}, K = 5
Output: -1
There are no odd elements in the given array.
Approach: Traverse the array element by element and for every odd element encountered, decrement the value k by 1. If the value of k becomes equal to 0 then print the current element. Else after the traversal of the complete array, if the value of k is > 0 then print -1 as the total number of odd elements in the array is < k.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function to return the kth odd element // from the array int kthOdd( int arr[], int n, int k) { // Traverse the array for ( int i = 0; i <= n; i++) { // If current element is odd if ((arr[i] % 2) == 1) k--; // If kth odd element is found if (k == 0) return arr[i]; } // Total odd elements in the array are < k return -1; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 2; cout << (kthOdd(arr, n, k)); return 0; } // This code is contributed by jit_t |
Java
// Java implementation of the approach public class GFG { // Function to return the kth odd element // from the array static int kthOdd( int arr[], int n, int k) { // Traverse the array for ( int i = 0 ; i < n; i++) { // If current element is odd if (arr[i] % 2 == 1 ) k--; // If kth odd element is found if (k == 0 ) return arr[i]; } // Total odd elements in the array are < k return - 1 ; } // Driver code public static void main(String args[]) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int n = arr.length; int k = 2 ; System.out.print(kthOdd(arr, n, k)); } } |
Python3
# Python3 implementation of the approach # Function to return the kth odd # element from the array def kthOdd (arr, n, k): # Traverse the array for i in range (n): # If current element is odd if (arr[i] % 2 = = 1 ): k - = 1 ; # If kth odd element is found if (k = = 0 ): return arr[i]; # Total odd elements in the # array are < k return - 1 ; # Driver code arr = [ 1 , 2 , 3 , 4 , 5 ]; n = len (arr); k = 2 ; print (kthOdd(arr, n, k)); # This code is contributed by mits |
C#
// C# implementation of the approach using System; class GFG { // Function to return the kth odd element // from the array static int kthOdd( int []arr, int n, int k) { // Traverse the array for ( int i = 0; i < n; i++) { // If current element is odd if (arr[i] % 2 == 1) k--; // If kth odd element is found if (k == 0) return arr[i]; } // Total odd elements in the array are < k return -1; } // Driver code public static void Main() { int []arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; int k = 2; Console.WriteLine(kthOdd(arr, n, k)); } } // This code is contributed by SoM15242 |
Javascript
<script> // JavaScript implementation of the approach // Function to return the kth odd element // from the array function kthOdd(arr , n , k) { // Traverse the array for (i = 0; i < n; i++) { // If current element is odd if (arr[i] % 2 == 1) k--; // If kth odd element is found if (k == 0) return arr[i]; } // Total odd elements in the array are < k return -1; } // Driver code var arr = [ 1, 2, 3, 4, 5 ]; var n = arr.length; var k = 2; document.write(kthOdd(arr, n, k)); // This code contributed by Rajput-Ji </script> |
PHP
<?php // PHP implementation of the approach // Function to return the kth odd // element from the array function kthOdd ( $arr , $n , $k ) { // Traverse the array for ( $i = 0; $i < $n ; $i ++) { // If current element is odd if ( $arr [ $i ] % 2 == 1) $k --; // If kth odd element is found if ( $k == 0) return $arr [ $i ]; } // Total odd elements in the // array are < k return -1; } // Driver code $arr = array ( 1, 2, 3, 4, 5 ); $n = sizeof( $arr ); $k = 2; echo (kthOdd( $arr , $n , $k )); // This code is contributed by ajit.. ?> |
3
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach: Iterating the array and counting odd elements
Below is the implementation of the above approach:
C++
#include <iostream> #include <vector> int findKthOddElement(std::vector< int >& array, int K) { int count = 0; for ( int element : array) { // Checking if the element is odd if (element % 2 != 0) { //increment the count count++; if (count == K) { return element; } } } return -1; } int main() { std::vector< int > array = {1, 2, 3, 4, 5}; int K = 2; int result = findKthOddElement(array, K); std::cout << result << std::endl; return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class Main { public static int findKthOddElement(List<Integer> list, int K) { int count = 0 ; for ( int element : list) { // Checking if the element is odd if (element % 2 != 0 ) { // Increment the count count++; //checking if count is equal to k or not if (count == K) { return element; } } } return - 1 ; } public static void main(String[] args) { List<Integer> list = new ArrayList<>(); list.add( 1 ); list.add( 2 ); list.add( 3 ); list.add( 4 ); list.add( 5 ); //input int K = 2 ; int result = findKthOddElement(list, K); System.out.println(result); } } |
Python3
# Python3 implementation of the above approach def find_kth_odd_element(array, K): count = 0 for element in array: # Checking if the element is odd if element % 2 ! = 0 : count + = 1 if count = = K: return element return - 1 # Driver Code array = [ 1 , 2 , 3 , 4 , 5 ] K = 2 result = find_kth_odd_element(array, K) print (result) |
C#
using System; using System.Collections.Generic; class Program { // Function to find the Kth odd element in a list static int FindKthOddElement(List< int > list, int K) { int count = 0; foreach ( int element in list) { // Checking if the element is odd if (element % 2 != 0) { count++; // If we've found the Kth odd element, return it if (count == K) { return element; } } } // If there are fewer than K odd elements, return -1 return -1; } static void Main() { List< int > list = new List< int > { 1, 2, 3, 4, 5 }; int K = 2; int result = FindKthOddElement(list, K); if (result != -1) { Console.WriteLine( "The " + K + "th odd element is: " + result); } else { Console.WriteLine( "There are fewer than " + K + " odd elements in the list." ); } } } |
Javascript
// JavaScript Program for the above approach function find_kth_odd_element(array, K) { let count = 0; for (let element of array) { // Checking if the element is odd if (element % 2 != 0) { count += 1; if (count == K) { return element; } } } return -1; } // Driver Code let array = [1, 2, 3, 4, 5]; let K = 2; let result = find_kth_odd_element(array, K); console.log(result); // This code is contributed by Kanchan Agarwal |
3
Time Complexity: O(N), where N is the length of the input array.
Auxiliary Space: O(1)
Contact Us