Check whether K times of a element is present in array
Given an array arr[] and an integer K, the task is to check whether K times of any element are also present in the array.
Examples :
Input: arr[] = {10, 14, 8, 13, 5}, K = 2
Output: Yes
Explanation:
K times of 5 is also present in an array, i.e. 10.Input: arr[] = {7, 8, 5, 9, 11}, K = 3
Output: No
Explanation:
K times of any element is not present in the array
Naive Approach: A simple solution is to run two nested loops and check for every element that K times of that element is also present in the array.
Below is the implementation of the above approach:
C++
// C++ implementation to check whether // K times of a element is present in // the array #include <bits/stdc++.h> using namespace std; // Function to find if K times of // an element exists in array void checkKTimesElement( int arr[], int n, int k) { bool found = false ; // Loop to check that K times of // element is present in the array for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (arr[j] == k * arr[i]) { found = true ; break ; } } } if (found) cout << "Yes" << endl; else cout << "No" << endl; } // Driver code int main() { int arr[] = { 10, 14, 8, 13, 5 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 2; // Function Call checkKTimesElement(arr, n, k); return 0; } |
Java
// Java implementation to check whether // K times of a element is present in // the array class GFG{ // Function to find if K times of // an element exists in array static void checkKTimesElement( int arr[], int n, int k) { boolean found = false ; // Loop to check that K times of // element is present in the array for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { if (arr[j] == k * arr[i]) { found = true ; break ; } } } if (found) System.out.print( "Yes" + "\n" ); else System.out.print( "No" + "\n" ); } // Driver code public static void main(String[] args) { int arr[] = { 10 , 14 , 8 , 13 , 5 }; int n = arr.length; int k = 2 ; // Function call checkKTimesElement(arr, n, k); } } // This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation to check whether # K times of a element is present in # the array # Function to find if K times of # an element exists in array def checkKTimesElement(arr, n, k): found = False # Loop to check that K times of # element is present in the array for i in range ( 0 , n): for j in range ( 0 , n): if arr[j] = = k * arr[i]: found = True break if found: print ( 'Yes' ) else : print ( 'No' ) # Driver code if __name__ = = '__main__' : arr = [ 10 , 14 , 8 , 13 , 5 ] n = len (arr) k = 2 # Function Call checkKTimesElement(arr, n, k) # This code is contributed by rutvik_56 |
C#
// C# implementation to check whether // K times of a element is present in // the array using System; class GFG{ // Function to find if K times of // an element exists in array static void checkKTimesElement( int []arr, int n, int k) { bool found = false ; // Loop to check that K times of // element is present in the array for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (arr[j] == k * arr[i]) { found = true ; break ; } } } if (found) Console.Write( "Yes" + "\n" ); else Console.Write( "No" + "\n" ); } // Driver code public static void Main(String[] args) { int []arr = { 10, 14, 8, 13, 5 }; int n = arr.Length; int k = 2; // Function call checkKTimesElement(arr, n, k); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript implementation to check whether // K times of a element is present in // the array // Function to find if K times of // an element exists in array function checkKTimesElement(arr, n, k) { var found = false ; // Loop to check that K times of // element is present in the array for ( var i = 0; i < n; i++) { for ( var j = 0; j < n; j++) { if (arr[j] == k * arr[i]) { found = true ; break ; } } } if (found) document.write( "Yes" ); else document.write( "No" ); } // Driver code var arr = [ 10, 14, 8, 13, 5 ]; var n = arr.length; var k = 2; // Function Call checkKTimesElement(arr, n, k); </script> |
Yes
Efficient Approach: The idea is to store all elements in hash-map and for each element check that K times of that element is present in the hash-map. If it exists in the hash-map, then return True otherwise False.
Below is the implementation of the above approach:
C++
// C++ implementation to check whether // K times of a element is present in // the array #include <bits/stdc++.h> using namespace std; // Function to check if K times of // an element exists in array bool checkKTimesElement( int arr[], int n, int k) { // Create an empty set unordered_set< int > s; for ( int i = 0; i < n; i++){ s.insert(arr[i]); } for ( int i = 0; i < n; i++) { // Check if K times of // element exists in set if (s.find(arr[i] * k) != s.end()) return true ; } return false ; } // Driven code int main() { int arr[] = { 5, 14, 8, 13, 10 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 2; if (checkKTimesElement(arr, n, k)) cout << "Yes\n" ; else cout << "No\n" ; return 0; } |
Java
// Java implementation to check whether // K times of a element is present in // the array import java.util.*; class GFG{ // Function to check if K times of // an element exists in array static boolean checkKTimesElement( int arr[], int n, int k) { // Create an empty set HashSet<Integer> s = new HashSet<Integer>(); for ( int i = 0 ; i < n; i++) { s.add(arr[i]); } for ( int i = 0 ; i < n; i++) { // Check if K times of // element exists in set if (s.contains(arr[i] * k)) return true ; } return false ; } // Driver code public static void main(String[] args) { int arr[] = { 5 , 14 , 8 , 13 , 10 }; int n = arr.length; int k = 2 ; if (checkKTimesElement(arr, n, k)) System.out.print( "Yes\n" ); else System.out.print( "No\n" ); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 implementation to # check whether K times of # a element is present in the array # Function to check if K times of # an element exists in array def checkKTimesElement(arr, n, k): # Create an empty set s = set ([]) for i in range (n): s.add(arr[i]) for i in range (n): # Check if K times of # element exists in set if ((arr[i] * k) in s): return True return False # Driver code if __name__ = = "__main__" : arr = [ 5 , 14 , 8 , 13 , 10 ] n = len (arr) k = 2 if (checkKTimesElement(arr, n, k)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Chitranayal |
C#
// C# implementation to check whether // K times of a element is present in // the array using System; using System.Collections.Generic; class GFG{ // Function to check if K times of // an element exists in array static bool checkKTimesElement( int [] arr, int n, int k) { // Create an empty set HashSet< int > s = new HashSet< int >(); for ( int i = 0; i < n; i++) { s.Add(arr[i]); } for ( int i = 0; i < n; i++) { // Check if K times of // element exists in set if (s.Contains(arr[i] * k)) return true ; } return false ; } // Driver code static public void Main () { int [] arr = { 5, 14, 8, 13, 10 }; int n = arr.Length; int k = 2; if (checkKTimesElement(arr, n, k)) Console.Write( "Yes\n" ); else Console.Write( "No\n" ); } } // This code is contributed by ShubhamCoder |
Javascript
<script> //Javascript implementation to check whether // K times of a element is present in // the array // Function to check if K times of // an element exists in array function checkKTimesElement(arr, n, k) { // Create an empty set s = new Set(); for ( var i = 0; i < n; i++){ s.add(arr[i]); } for ( var i = 0; i < n; i++) { // Check if K times of // element exists in set if (s.has(arr[i] * k)) return true ; } return false ; } // Driver program to test above var arr = [5, 14, 8, 13, 10]; var n = arr.length; var k = 2; if (checkKTimesElement(arr, n, k)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by shivani. </script> |
Yes
Time Complexity: O(n)