Tutorialspoint.dev

Print array elements that are divisible by at-least one other

Given an array of length N that contains only integers, the task is to print the special numbers of array. A number in this array is called Special number if it is divisible by at least one other number in the array.

Examples :

Input : 1 2 3
Output : 2 3
Explanation : both 2 and 3 are divisible by 1.

Input : 2 3 4 6 8 9
Output : 4 6 8 9
Explanation : 2 and 3 are not divisible by any other element. Rest of the element are divisible by at-least 1 element. 6 is divisible by both 2 and 3, 4 divisible by 2, 8 divisible by 2 and 4 both, 9 divisible by 3.

Input : 3 5 7 11
Output :
Explanation : all elements are relatively prime so no special number.



A simple solution is to traverse through all elements, then check for every element if it is divisible by any other. Time complexity of this solution is O(n2)

Another solution that works better when there are many elements with not very big values. Store all array elements into hash and find out the max element in array then up-to max element find out the multiples of a given number then if multiple of array element is in hash then that number is divisible by at-least one element of array .To remove duplicate values we store the value into set because if array has 2, 3 and 6 then only 6 is divisible by at-least one element of array, both 2 and 3 divide 6 so 6 will be stored only one time.

C++

// C++ program to find special numbers
// in an array
#include <bits/stdc++.h>
using namespace std;
  
// Function to find special numbers
void divisibilityCheck(int arr[], int n)
{
    // Storing all array elements in a hash
    // and finding maximum element in array
    unordered_set<int> s;
    int max_ele = INT_MIN;
    for (int i = 0; i < n; i++) {
        s.insert(arr[i]);
  
        // finding maximum element of array
        max_ele = max(max_ele, arr[i]);
    }
  
    // traversing array element and storing the array 
    // multiples that are present in s in res.
    unordered_set<int> res;
    for (int i = 0; i < n; i++) {
  
        // Check for non-zero values only
        if (arr[i] != 0)
  
            // checking the factor of current element
            for (int j = arr[i] * 2; j <= max_ele;
                                        j += arr[i])
             {
  
                // if factor is already part of array
                // element then store it
                if (s.find(j) != s.end())
                    res.insert(j);
            }
    }
  
    // displaying elements that are divisible by
    // at least one other in array
    for (auto x : res)
        cout << x << " ";
}
  
// Driver code
int main()
{
    int arr[] = { 2, 3, 8, 6, 9, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    divisibilityCheck(arr, n);
    return 0;
}

Java

// Java program to find special 
// numbers in an array
import java.io.*;
import java.util.*;
  
class GFG
{
    // Function to find 
    // special numbers
    static void divisibilityCheck(List<Integer> arr, 
                                              int n)
    {
        // Storing all array elements 
        // in a hash and finding maximum
        // element in array
        List<Integer> s = new ArrayList<Integer>();
        int max_ele = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) 
        {
            s.add(arr.get(i));
      
            // finding maximum 
            // element of array
            max_ele = Math.max(max_ele, 
                               arr.get(i));
        }
      
        // traversing array element and 
        // storing the array multiples 
        // that are present in s in res.
        LinkedHashSet<Integer> res = 
                        new LinkedHashSet<Integer>();
        for (int i = 0; i < n; i++) 
        {
      
            // Check for non-zero values only
            if (arr.get(i) != 0)
      
                // checking the factor 
                // of current element
                for (int j = arr.get(i) * 2
                         j <= max_ele; 
                         j += arr.get(i))
                {
      
                    // if factor is already 
                    // part of array element
                    // then store it
                    if (s.contains(j))
                        res.add(j);
                }
        }
          
        // displaying elements that 
        // are divisible by at least
        // one other in array
        List<Integer> list = 
                 new ArrayList<Integer>(res);
        Collections.reverse(list);
          
        for (Integer temp : list)
        System.out.print(temp + " ");
    }
      
    // Driver Code
    public static void main(String args[])
    {
        List<Integer> arr = Arrays.asList(2, 3, 8
                                          6, 9, 10);
        int n = arr.size();
        divisibilityCheck(arr, n);
    }
}
  
// This code is contributed by 
// Manish Shaw(manishshaw1)

Python3

# Python3 program to find special numbers
# in an array
import math as mt

# Function to find special numbers
def divisibilityCheck(arr, n):

# Storing all array elements in a hash
# and finding maximum element in array
s = dict()
max_ele = -10**9
for i in range(n):
s[arr[i]] = 1

# finding maximum element of array
max_ele = max(max_ele, arr[i])

# traversing array element and storing
# the array multiples that are present
# in s in res.
res = dict()
for i in range(n):

# Check for non-zero values only
if (arr[i] != 0):

# checking the factor of current element
for j in range(arr[i] * 2,
max_ele + 1, arr[i]):

# if factor is already part of
# array element then store it
if (j in s.keys()):
res[j] = 1

# displaying elements that are divisible
# by at least one other in array
for x in res:
print(x, end = ” “)

# Driver code
arr = [ 2, 3, 8, 6, 9, 10]
n = len(arr)
divisibilityCheck(arr, n)

# This code is contributed by
# Mohit Kumar 29

C#

// C# program to find special 
// numbers in an array
using System;
using System.Linq;
using System.Collections.Generic;
  
class GFG
{
    // Function to find 
    // special numbers
    static void divisibilityCheck(List<int> arr, 
                                       int n)
    {
        // Storing all array elements 
        // in a hash and finding maximum
        // element in array
        List<int> s = new List<int>();
        int max_ele = Int32.MinValue;
        for (int i = 0; i < n; i++) 
        {
            s.Add(arr[i]);
      
            // finding maximum element of array
            max_ele = Math.Max(max_ele, 
                               arr[i]);
        }
      
        // traversing array element and 
        // storing the array multiples 
        // that are present in s in res.
        HashSet<int> res = new HashSet<int>();
        for (int i = 0; i < n; i++) 
        {
      
            // Check for non-zero values only
            if (arr[i] != 0)
      
                // checking the factor 
                // of current element
                for (int j = arr[i] * 2; j <= max_ele;
                                         j += arr[i])
                {
      
                    // if factor is already part 
                    // of array element then store it
                    if (s.Contains(j))
                        res.Add(j);
                }
        }
        // displaying elements that 
        // are divisible by at least
        // one other in array
        foreach (int i in res.Reverse())
            Console.Write(i + " ");
    }
      
    // Driver Code
    static void Main()
    {
        List<int> arr = new List<int>(){ 2, 3, 8, 
                                         6, 9, 10 };
        int n = arr.Count;
        divisibilityCheck(arr, n);
    }
}
  
// This code is contributed by 
// Manish Shaw(manishshaw1)

Output :

9 10 8 6


Note :
If we need result to be printed in sorted order, we can use set in place of unordered_set.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter