Smallest positive integer that does not divide any elements of the given array
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
