Check whether K times of a element is present in array

0 0 6 minutes read

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>

Output:

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>

Output:

Yes

Time Complexity: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!