Given two natural numbers A and B (B >= A) and an integer N, your task is to generate an array of natural numbers in non-decreasing order, such that both A and B must be part of the array and the difference between every pair of adjacent elements is the same keeping the maximum element of the array as minimum as possible.
Example:
Input: A = 10, B = 20, N = 4
Output: 5 10 15 20
Explanation: The array {5, 10, 15, 20} contains only natural numbers and both A=10 and B=20 are included in the array. The difference between every adjacent pair is 5 and the maximum element is 20 which can’t be further reduced.Input: A = 12, B = 33, N = 2
Output: 12 33Input: A = 7, B = 17, N = 5
Output: 2 7 12 17 22
Approach: The required array forms an AP series. Since A and B must be included in the AP, the common difference d between adjacent terms must be a divisor of (B – A). To minimize the largest term, the optimal approach is to generate the array with the smallest possible common difference that satisfies the given conditions. The problem can be solved by following below steps:
- Iterate over all values of d from 1 to B-A.
- If d is a factor of B-A and the number of elements from A to B with common difference d are not more than N, proceed further. Else, move to the next value of d.
- There are two possible cases
- Case 1 – Number of elements smaller than or equal B having common difference d is greater than N. In this case, the first element of the array will be B – (d*(N-1)).
- Case 2 – Number of elements smaller than or equal B having common difference d is smaller than N. In this case, the first element of the array will be B – d*( B-1 )/d (i.e. 1).
- Print the array using the first element and the common difference.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the array of N// natural numbers in increasing order// with equal difference of adjacent// elements and containing A and Bvoid generateAP(int A, int B, int N){ // maximum possible difference int d = B - A; int cd, f; // Iterating over all values of d for (int i = 1; i <= d; i++) { // Check if i is a factor of d // and number of elements from // a to b with common difference // d are not more than N if (d % i == 0 && (d / i) + 1 <= N) { // Number of natural numbers // less than B and having // difference as i int cnt = min((B - 1) / i, N - 1); // Calculate the 1st element of // the required array f = B - (cnt * i); cd = i; break; } } // Print the resulting array for (int i = 0; i < N; i++) { cout << (f + i * cd) << " "; }}// Driver codeint main(){ int A = 10, B = 20, N = 4; // Function call generateAP(A, B, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { public static int min(int a ,int b){ if(a < b){ return a; } return b; } public static void generateAP(int A, int B, int N) { // maximum possible difference int d = B - A; int cd = 0, f= 0; // Iterating over all values of d for (int i = 1; i <= d; i++) { // Check if i is a factor of d // and number of elements from // a to b with common difference // d are not more than N if (d % i == 0 && (d / i) + 1 <= N) { // Number of natural numbers // less than B and having // difference as i int cnt = min((B - 1) / i, N - 1); // Calculate the 1st element of // the required array f = B - (cnt * i); cd = i; break; } } // Print the resulting array for (int i = 0; i < N; i++) { System.out.print((f + i * cd) + " "); } } // Driver code public static void main(String[] args) { int A = 10, B = 20, N = 4; // Function call generateAP(A, B, N); }}// This code is contributed by maddler. |
Python3
# Python program for the above approach# Function to print array of N# natural numbers in increasing order# with equal difference of adjacent# elements and containing A and Bdef generateAP(A, B, N): # maximum possible difference d = B - A # Iterating over all values of d for i in range(1,d+1): # Check if i is a factor of d # and number of elements from # a to b with common difference # d are not more than N if (d % i == 0 and (d // i) + 1 <= N): # Number of natural numbers # less than B and having # difference as i cnt = min((B - 1) // i, N - 1) # Calculate the 1st element of # the required array f = B - (cnt * i) cd = i break # Print resulting array for i in range(N): print(f + i * cd , end=" ") # Driver codeA = 10B = 20N = 4# Function callgenerateAP(A, B, N)# This code is contributed by shivanisinghss2110 |
C#
// C# program for the above approachusing System;class GFG{ public static int min(int a ,int b){ if(a < b){ return a; } return b; } public static void generateAP(int A, int B, int N) { // maximum possible difference int d = B - A; int cd = 0, f= 0; // Iterating over all values of d for (int i = 1; i <= d; i++) { // Check if i is a factor of d // and number of elements from // a to b with common difference // d are not more than N if (d % i == 0 && (d / i) + 1 <= N) { // Number of natural numbers // less than B and having // difference as i int cnt = min((B - 1) / i, N - 1); // Calculate the 1st element of // the required array f = B - (cnt * i); cd = i; break; } } // Print the resulting array for (int i = 0; i < N; i++) { Console.Write((f + i * cd) + " "); } }// Driver Codepublic static void Main(){ int A = 10, B = 20, N = 4; // Function call generateAP(A, B, N);}}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript program for the above approachfunction min(a, b){ if (a < b) { return a; } return b;}// Function to print the array of N// natural numbers in increasing order// with equal difference of adjacent// elements and containing A and Bfunction generateAP(A, B, N){ // Maximum possible difference var d = B - A; var cd = 0, f = 0; // Iterating over all values of d for(var i = 1; i <= d; i++) { // Check if i is a factor of d // and number of elements from // a to b with common difference // d are not more than N if (d % i == 0 && (d / i) + 1 <= N) { // Number of natural numbers // less than B and having // difference as i var cnt = min((B - 1) / i, N - 1); // Calculate the 1st element of // the required array f = B - (cnt * i); cd = i; break; } } // Print the resulting array for(var i = 0; i < N; i++) { document.write((f + i * cd) + " "); }}// Driver codevar A = 10, B = 20, N = 4;// Function callgenerateAP(A, B, N);// This code is contributed by shivanisinghss2110</script> |
Output
5 10 15 20
Time Complexity: O(N + √B)
Auxiliary Space: O(1)
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!
