Given an array arr[] consisting of N positive integers, the task is to determine the smallest positive integer K such that none of the array elements is divisible by K.
Examples:
Input: arr[] = {3, 2, 6, 9, 2}
Output: 4
Explanation: None of the array elements is divisible by 4(the smallest positive).Input: arr[] = {3, 5, 1, 19, 11}
Output: 2
Approach: Follow the steps below to solve the problem:
- Find the maximum element of the given array, say maxE.
- Iterate over the range [1, maxE + 1] using the variable i and check if there is an integer in the given array which is divisible by i or not. If found to be true, then check for the next integer in this range.
- Otherwise, print the current number i.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;Â
// Function to find the smallest number// which doesn't divides any integer in// the given array arr[]void smallestNumber(int arr[], int len){Â Â Â Â int maxi = 0;Â
    // Traverse the array arr[]    for (int i = 0; i < len; i++) {Â
        // Maximum array element        maxi = std::max(maxi, arr[i]);    }Â
    // Initialize variable    int ans = -1;Â
    // Traverse from 2 to max    for (int i = 2; i < maxi + 2; i++) {Â
        // Stores if any such        // integer is found or not        bool flag = true;Â
        for (int j = 0; j < len; j++) {Â
            // If any array element            // is divisible by j            if (arr[j] % i == 0) {Â
                flag = false;                break;            }        }Â
        if (flag) {Â
            // Smallest integer            ans = i;            break;        }    }Â
    // Print the answer    cout << ans;}Â
// Driver Codeint main(){Â Â Â Â int arr[] = { 3, 2, 6, 9, 2 };Â Â Â Â int N = sizeof(arr) / sizeof(arr[0]);Â
    // Function Call    smallestNumber(arr, N);Â
    return 0;} |
Java
// Java program for the above approachclass GFG{Â
// Function to find the smallest number// which doesn't divides any integer in// the given array arr[]static void smallestNumber(int arr[], int len){Â Â Â Â int maxi = 0;Â
    // Traverse the array arr[]    for (int i = 0; i < len; i++)    {Â
        // Maximum array element        maxi = Math.max(maxi, arr[i]);    }Â
    // Initialize variable    int ans = -1;Â
    // Traverse from 2 to max    for (int i = 2; i < maxi + 2; i++)    {Â
        // Stores if any such        // integer is found or not        boolean flag = true;        for (int j = 0; j < len; j++)         {Â
            // If any array element            // is divisible by j            if (arr[j] % i == 0)            {                flag = false;                break;            }        }Â
        if (flag)         {Â
            // Smallest integer            ans = i;            break;        }    }Â
    // Print the answer    System.out.print(ans);}Â
// Driver Codepublic static void main(String[] args){Â Â Â Â int arr[] = { 3, 2, 6, 9, 2 };Â Â Â Â int N = arr.length;Â
    // Function Call    smallestNumber(arr, N);}}Â
// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approachÂ
# Function to find the smallest number# which doesn't divides any integer in# the given array arr[]def smallestNumber(arr, lenn):Â Â Â Â maxi = 0Â
    # Traverse the array arr[]    for i in range(lenn):Â
        # Maximum array element        maxi = max(maxi, arr[i])Â
    # Initialize variable    ans = -1Â
    # Traverse from 2 to max    for i in range(2, maxi + 2):Â
        # Stores if any such        # integer is found or not        flag = True        for j in range(lenn):Â
            # If any array element            # is divisible by j            if (arr[j] % i == 0):                flag = False                break        if (flag):Â
            # Smallest integer            ans = i            breakÂ
    # Print the answer    print (ans)Â
# Driver Codeif __name__ == '__main__':Â Â Â Â arr = [3, 2, 6, 9, 2]Â Â Â Â N = len(arr)Â
    #Function Call    smallestNumber(arr, N)Â
# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG{Â
  // Function to find the smallest number  // which doesn't divides any integer in  // the given array arr[]  static void smallestNumber(int []arr, int len)  {    int maxi = 0;Â
    // Traverse the array arr[]    for (int i = 0; i < len; i++)    {Â
      // Maximum array element      maxi = Math.Max(maxi, arr[i]);    }Â
    // Initialize variable    int ans = -1;Â
    // Traverse from 2 to max    for (int i = 2; i < maxi + 2; i++)    {Â
      // Stores if any such      // integer is found or not      bool flag = true;      for (int j = 0; j < len; j++)       {Â
        // If any array element        // is divisible by j        if (arr[j] % i == 0)        {          flag = false;          break;        }      }      if (flag)       {Â
        // Smallest integer        ans = i;        break;      }    }Â
    // Print the answer    Console.WriteLine(ans);  }Â
  // Driver Code  public static void Main(string[] args)  {    int []arr = { 3, 2, 6, 9, 2 };    int N = arr.Length;Â
    // Function Call    smallestNumber(arr, N);  }}Â
// This code is contributed by AnkThon |
Javascript
<script>// javascript program of the above approachÂ
// Function to find the smallest number// which doesn't divides any integer in// the given array arr[]function smallestNumber(arr, len){Â Â Â Â let maxi = 0;Â
    // Traverse the array arr[]    for (let i = 0; i < len; i++)    {Â
        // Maximum array element        maxi = Math.max(maxi, arr[i]);    }Â
    // Initialize variable    let ans = -1;Â
    // Traverse from 2 to max    for (let i = 2; i < maxi + 2; i++)    {Â
        // Stores if any such        // integer is found or not        let flag = true;        for (let j = 0; j < len; j++)         {Â
            // If any array element            // is divisible by j            if (arr[j] % i == 0)            {                flag = false;                break;            }        }Â
        if (flag)         {Â
            // Smallest integer            ans = i;            break;        }    }Â
    // Print the answer    document.write(ans);}Â
    // Driver Code         let arr = [ 3, 2, 6, 9, 2 ];    let N = arr.length;Â
    // Function Call    smallestNumber(arr, N);Â
</script> |
Output:Â
4
Â
Time Complexity: O(N*max) where max is the maximum element in the given array
Auxiliary Space: O(1) as it is using constant space for variables
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
