Count minimum factor jumps required to reach the end of an Array

0 0 16 minutes read

Given an array of positive integers arr[], the task is to count the minimum factor jumps required to reach the end of an array. From any particular index i, the jump can be made only for K indices where K is a factor of arr[i].

Examples:

Input: arr[] = {2, 8, 16, 55, 99, 100}
Output: 2
Explanation:
The optimal jumps are:
a) Start from 2.
b) Since factors of 2 are [1, 2]. So only 1 or 2 index jumps are available. Therefore, jump 1 index to reach 8.
c) Since factors of 8 are [1, 2, 4, 8]. So only 1, 2, 4 or 8 index jumps are available. Therefore, they jumped 4 indices to reach 100.
d) We have reached the end, so no more jumps are required.
So, 2 jumps were required.

Input: arr[] = {2, 4, 6}
Output: 1

Approach: This problem can be solved using Recursion.

Firstly, we need to precompute the factors of every number from 1 to 1000000, so that we can get different choices of jumps in O(1) time.
Then, recursively calculate the minimum jumps required to reach the end of the array and print it.

C++

// C++ code to count minimum factor jumps
// to reach the end of array
#include <bits/stdc++.h>
using namespace std;
 
// vector to store factors of each integer
vector<int> factors[100005];
 
// Precomputing all factors of integers
// from 1 to 100000
void precompute()
{
    for (int i = 1; i <= 100000; i++) {
        for (int j = i; j <= 100000; j += i) {
            factors[j].push_back(i);
        }
    }
}
 
// Recursive function to count the minimum jumps
int solve(int arr[], int k, int n)
{
    // If we reach the end of array,
    // no more jumps are required
    if (k == n - 1) {
        return 0;
    }
 
    // If the jump results in out of index,
    // return INT_MAX
    if (k >= n) {
        return INT_MAX;
    }
 
    // Else compute the answer
    // using the recurrence relation
    int ans = INT_MAX;
 
    // Iterating over all choices of jumps
    for (auto j : factors[arr[k]]) {
 
        // Considering current factor as a jump
        int res = solve(arr, k + j, n);
 
        // Jump leads to the destination
        if (res != INT_MAX) {
            ans = min(ans, res + 1);
        }
    }
 
    // Return ans
    return ans;
}
 
// Driver code
int main()
{
    // pre-calculating the factors
    precompute();
 
    int arr[] = { 2, 8, 16, 55, 99, 100 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << solve(arr, 0, n);
}

Java

// Java code to count minimum 
// factor jumps to reach the 
// end of array
import java.util.*;
public class GFG{
 
// vector to store factors 
// of each integer
static Vector<Integer> []factors = 
              new Vector[100005];
 
// Precomputing all factors 
// of integers from 1 to 100000
static void precompute()
{
  for (int i = 0; i < factors.length; i++)
    factors[i] = new Vector<Integer>();
  for (int i = 1; i <= 100000; i++) 
  {
    for (int j = i; j <= 100000; j += i) 
    {
      factors[j].add(i);
    }
  }
}
 
// Function to count the 
// minimum jumps
static int solve(int arr[], 
                 int k, int n)
{
  // If we reach the end of 
  // array, no more jumps 
  // are required
  if (k == n - 1) 
  {
    return 0;
  }
 
  // If the jump results in 
  // out of index, return 
  // Integer.MAX_VALUE
  if (k >= n) 
  {
    return Integer.MAX_VALUE;
  }
 
  // Else compute the answer
  // using the recurrence relation
  int ans = Integer.MAX_VALUE;
 
  // Iterating over all choices 
  // of jumps
  for (int j : factors[arr[k]]) 
  {
    // Considering current factor 
    // as a jump
    int res = solve(arr, k + j, n);
 
    // Jump leads to the destination
    if (res != Integer.MAX_VALUE) 
    {
      ans = Math.min(ans, res + 1);
    }
  }
 
  // Return ans
  return ans;
}
 
// Driver code
public static void main(String[] args)
{
  // pre-calculating 
  // the factors
  precompute();
 
  int arr[] = {2, 8, 16, 
               55, 99, 100};
  int n = arr.length;
  System.out.print(solve(arr, 0, n));
}
}
 
// This code is contributed by Samim Hossain Mondal.

C#

// C# code to count minimum 
// factor jumps to reach the 
// end of array
using System;
using System.Collections.Generic;
class GFG{
 
// vector to store factors 
// of each integer
static List<int> []factors = 
            new List<int>[100005];
 
// Precomputing all factors 
// of integers from 1 to 100000
static void precompute()
{
  for (int i = 0; 
           i < factors.Length; i++)
    factors[i] = new List<int>();
  for (int i = 1; i <= 100000; i++) 
  {
    for (int j = i; 
             j <= 100000; j += i) 
    {
      factors[j].Add(i);
    }
  }
}
 
// Function to count the 
// minimum jumps
static int solve(int []arr, 
                 int k, int n)
{
  // If we reach the end of 
  // array, no more jumps 
  // are required
  if (k == n - 1) 
  {
    return 0;
  }
 
  // If the jump results in 
  // out of index, return 
  // int.MaxValue
  if (k >= n) 
  {
    return int.MaxValue;
  }
 
  // Else compute the answer
  // using the recurrence relation
  int ans = int.MaxValue;
 
  // Iterating over all choices 
  // of jumps
  foreach (int j in factors[arr[k]]) 
  {
    // Considering current  
    // factor as a jump
    int res = solve(arr, k + j, n);
 
    // Jump leads to the 
    // destination
    if (res != int.MaxValue) 
    {
      ans = Math.Min(ans, res + 1);
    }
  }
 
  // Return ans
  return ans;
}
 
// Driver code
public static void Main(String[] args)
{
  // pre-calculating 
  // the factors
  precompute();
 
  int []arr = {2, 8, 16, 
               55, 99, 100};
  int n = arr.Length;
  Console.Write(solve(arr, 0, n));
}
}
 
// This code is contributed by Samim Hossain Mondal.

Python

# Python3 code to count minimum factor jumps
# to reach the end of array
 
# vector to store factors of each integer
factors = [[] for i in range(100005)]
 
# Precomputing all factors of integers
# from 1 to 100000
def precompute():
 
    for i in range(1, 100001):
        for j in range(i, 100001, i):
 
            factors[j].append(i)
 
# Function to count the minimum jumps
def solve(arr, k, n):
 
    # If we reach the end of array,
    # no more jumps are required
    if (k == n - 1):
        return 0
 
    # If the jump results in out of index,
    # return INT_MAX
    if (k >= n):
        return 1000000000
 
    # Else compute the answer
    # using the recurrence relation
    ans = 1000000000
 
    # Iterating over all choices of jumps
    for j in factors[arr[k]]:
 
        # Considering current factor as a jump
        res = solve(arr, k + j, n)
 
        # Jump leads to the destination
        if (res != 1000000000):
            ans = min(ans, res + 1)
 
    # Return ans
    return ans
 
 
# Driver code
if __name__ == '__main__':
 
    # pre-calculating the factors
    precompute()
 
    arr = [2, 8, 16, 55, 99, 100]
    n = len(arr)
 
    print(solve(arr, 0, n))
 
# This code is contributed by Samim Hossain Mondal.

Javascript

<script>
// Javascript code to count minimum factor jumps
// to reach the end of array
 
// vector to store factors of each integer
let factors = new Array();
 
for (let i = 0; i < 100005; i++) {
    factors.push(new Array());
}
 
// Precomputing all factors of integers
// from 1 to 100000
function precompute() {
    for (let i = 1; i <= 100000; i++) {
        for (let j = i; j <= 100000; j += i) {
            factors[j].push(i);
        }
    }
}
 
// Function to count the minimum jumps
function solve(arr, k, n) {
 
    // If we reach the end of array,
    // no more jumps are required
    if (k == n - 1) {
        return 0;
    }
 
    // If the jump results in out of index,
    // return INT_MAX
    if (k >= n) {
        return Number.MAX_SAFE_INTEGER;
    }
 
    // Else compute the answer
    // using the recurrence relation
    let ans = Number.MAX_SAFE_INTEGER;
 
    // Iterating over all choices of jumps
    for (let j of factors[arr[k]]) {
 
        // Considering current factor as a jump
        let res = solve(arr, k + j, n);
 
        // Jump leads to the destination
        if (res != Number.MAX_SAFE_INTEGER) {
            ans = Math.min(ans, res + 1);
        }
    }
 
    // Return ans
    return ans;
}
 
// Driver code
 
// pre-calculating the factors
precompute();
 
let arr = [2, 8, 16, 55, 99, 100];
let n = arr.length;
 
document.write(solve(arr, 0, n));
 
// This code is contributed by Samim Hossain Mondal.
</script>

Output

Time Complexity: O(100005*2^N)

Auxiliary Space: O(100005)

Another Approach: Dynamic Programming using Memoization.

Firstly, we need to precompute the factors of every number from 1 to 1000000, so that we can get different choices of jumps in O(1) time.
Then, let dp[i] be the minimum jump required to reach i, we need to find dp[n-1].
So, the recurrence relation becomes:

$dp[i] = min(dp[i], 1 + solve(i+j))$

where j is one of the factors of arr[i] & solve() is the recursive function

Find the minimum jumps using this recurrence relation and print it.

Below is the recursive implementation of the above approach:

C++

// C++ code to count minimum factor jumps
// to reach the end of array
 
#include <bits/stdc++.h>
using namespace std;
 
// vector to store factors of each integer
vector<int> factors[100005];
 
// dp array
int dp[100005];
 
// Precomputing all factors of integers
// from 1 to 100000
void precompute()
{
    for (int i = 1; i <= 100000; i++) {
        for (int j = i; j <= 100000; j += i) {
            factors[j].push_back(i);
        }
    }
}
 
// Function to count the minimum jumps
int solve(int arr[], int k, int n)
{
 
    // If we reach the end of array,
    // no more jumps are required
    if (k == n - 1) {
        return 0;
    }
 
    // If the jump results in out of index,
    // return INT_MAX
    if (k >= n) {
        return INT_MAX;
    }
 
    // If the answer has been already computed,
    // return it directly
    if (dp[k]) {
        return dp[k];
    }
 
    // Else compute the answer
    // using the recurrence relation
    int ans = INT_MAX;
 
    // Iterating over all choices of jumps
    for (auto j : factors[arr[k]]) {
 
        // Considering current factor as a jump
        int res = solve(arr, k + j, n);
 
        // Jump leads to the destination
        if (res != INT_MAX) {
            ans = min(ans, res + 1);
        }
    }
 
    // Return ans and memorize it
    return dp[k] = ans;
}
 
// Driver code
int main()
{
 
    // pre-calculating the factors
    precompute();
 
    int arr[] = { 2, 8, 16, 55, 99, 100 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << solve(arr, 0, n);
}

Java

// Java code to count minimum 
// factor jumps to reach the 
// end of array
import java.util.*;
class GFG{
 
// vector to store factors 
// of each integer
static Vector<Integer> []factors = 
              new Vector[100005];
 
// dp array
static int []dp = new int[100005];
 
// Precomputing all factors 
// of integers from 1 to 100000
static void precompute()
{
  for (int i = 0; i < factors.length; i++)
    factors[i] = new Vector<Integer>();
  for (int i = 1; i <= 100000; i++) 
  {
    for (int j = i; j <= 100000; j += i) 
    {
      factors[j].add(i);
    }
  }
}
 
// Function to count the 
// minimum jumps
static int solve(int arr[], 
                 int k, int n)
{
  // If we reach the end of 
  // array, no more jumps 
  // are required
  if (k == n - 1) 
  {
    return 0;
  }
 
  // If the jump results in 
  // out of index, return 
  // Integer.MAX_VALUE
  if (k >= n) 
  {
    return Integer.MAX_VALUE;
  }
 
  // If the answer has been 
  // already computed, return 
  // it directly
  if (dp[k] != 0) 
  {
    return dp[k];
  }
 
  // Else compute the answer
  // using the recurrence relation
  int ans = Integer.MAX_VALUE;
 
  // Iterating over all choices 
  // of jumps
  for (int j : factors[arr[k]]) 
  {
    // Considering current factor 
    // as a jump
    int res = solve(arr, k + j, n);
 
    // Jump leads to the destination
    if (res != Integer.MAX_VALUE) 
    {
      ans = Math.min(ans, res + 1);
    }
  }
 
  // Return ans and memorize it
  return dp[k] = ans;
}
 
// Driver code
public static void main(String[] args)
{
  // pre-calculating 
  // the factors
  precompute();
 
  int arr[] = {2, 8, 16, 
               55, 99, 100};
  int n = arr.length;
  System.out.print(solve(arr, 0, n));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 code to count minimum factor jumps
# to reach the end of array
  
# vector to store factors of each integer
factors= [[] for i in range(100005)];
  
# dp array
dp = [0 for i in range(100005)];
  
# Precomputing all factors of integers
# from 1 to 100000
def precompute():
 
    for i in range(1, 100001):
        for j in range(i, 100001, i):
     
            factors[j].append(i);
  
# Function to count the minimum jumps
def solve(arr, k, n):
  
    # If we reach the end of array,
    # no more jumps are required
    if (k == n - 1):
        return 0;
     
    # If the jump results in out of index,
    # return INT_MAX
    if (k >= n):
        return 1000000000
     
    # If the answer has been already computed,
    # return it directly
    if (dp[k]):
        return dp[k];
     
    # Else compute the answer
    # using the recurrence relation
    ans = 1000000000
  
    # Iterating over all choices of jumps
    for j in factors[arr[k]]:
  
        # Considering current factor as a jump
        res = solve(arr, k + j, n);
  
        # Jump leads to the destination
        if (res != 1000000000):
            ans = min(ans, res + 1);
         
    # Return ans and memorize it
    dp[k] = ans;
    return ans
 
# Driver code
if __name__=='__main__':
  
    # pre-calculating the factors
    precompute()
  
    arr = [ 2, 8, 16, 55, 99, 100 ]
    n = len(arr)
     
    print(solve(arr, 0, n))
  
# This code is contributed by rutvik_56

C#

// C# code to count minimum 
// factor jumps to reach the 
// end of array
using System;
using System.Collections.Generic;
class GFG{
 
// vector to store factors 
// of each integer
static List<int> []factors = 
            new List<int>[100005];
 
// dp array
static int []dp = new int[100005];
 
// Precomputing all factors 
// of integers from 1 to 100000
static void precompute()
{
  for (int i = 0; 
           i < factors.Length; i++)
    factors[i] = new List<int>();
  for (int i = 1; i <= 100000; i++) 
  {
    for (int j = i; 
             j <= 100000; j += i) 
    {
      factors[j].Add(i);
    }
  }
}
 
// Function to count the 
// minimum jumps
static int solve(int []arr, 
                 int k, int n)
{
  // If we reach the end of 
  // array, no more jumps 
  // are required
  if (k == n - 1) 
  {
    return 0;
  }
 
  // If the jump results in 
  // out of index, return 
  // int.MaxValue
  if (k >= n) 
  {
    return int.MaxValue;
  }
 
  // If the answer has been 
  // already computed, return 
  // it directly
  if (dp[k] != 0) 
  {
    return dp[k];
  }
 
  // Else compute the answer
  // using the recurrence relation
  int ans = int.MaxValue;
 
  // Iterating over all choices 
  // of jumps
  foreach (int j in factors[arr[k]]) 
  {
    // Considering current  
    // factor as a jump
    int res = solve(arr, k + j, n);
 
    // Jump leads to the 
    // destination
    if (res != int.MaxValue) 
    {
      ans = Math.Min(ans, res + 1);
    }
  }
 
  // Return ans and 
  // memorize it
  return dp[k] = ans;
}
 
// Driver code
public static void Main(String[] args)
{
  // pre-calculating 
  // the factors
  precompute();
 
  int []arr = {2, 8, 16, 
               55, 99, 100};
  int n = arr.Length;
  Console.Write(solve(arr, 0, n));
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// Javascript code to count minimum factor jumps
// to reach the end of array
 
 
// vector to store factors of each integer
let factors = new Array();
 
// dp array
let dp = new Array(100005);
 
for (let i = 0; i < 100005; i++) {
    factors.push(new Array());
}
 
 
// Precomputing all factors of integers
// from 1 to 100000
function precompute() {
    for (let i = 1; i <= 100000; i++) {
        for (let j = i; j <= 100000; j += i) {
            factors[j].push(i);
        }
    }
}
 
// Function to count the minimum jumps
function solve(arr, k, n) {
 
    // If we reach the end of array,
    // no more jumps are required
    if (k == n - 1) {
        return 0;
    }
 
    // If the jump results in out of index,
    // return INT_MAX
    if (k >= n) {
        return Number.MAX_SAFE_INTEGER;
    }
 
    // If the answer has been already computed,
    // return it directly
    if (dp[k]) {
        return dp[k];
    }
 
    // Else compute the answer
    // using the recurrence relation
    let ans = Number.MAX_SAFE_INTEGER;
 
    // Iterating over all choices of jumps
    for (let j of factors[arr[k]]) {
 
        // Considering current factor as a jump
        let res = solve(arr, k + j, n);
 
        // Jump leads to the destination
        if (res != Number.MAX_SAFE_INTEGER) {
            ans = Math.min(ans, res + 1);
        }
    }
 
    // Return ans and memorize it
    return dp[k] = ans;
}
 
// Driver code
 
// pre-calculating the factors
precompute();
 
let arr = [2, 8, 16, 55, 99, 100];
let n = arr.length;
 
document.write(solve(arr, 0, n));
 
// This code is contributed by _saurabh_jaiswal
</script>

Output

Time Complexity: O(100000*N)

Auxiliary Space: O(100005)

Given below is the Iterative Bottom-Up Approach:

C++

// C++ program for bottom up approach
#include <bits/stdc++.h>
using namespace std;
 
// Vector to store factors of each integer
vector<int> factors[100005];
 
// Initialize the dp array
int dp[100005];
 
// Precompute all the
// factors of every integer
void precompute()
{
    for (int i = 1; i <= 100000; i++) {
        for (int j = i; j <= 100000; j += i)
            factors[j].push_back(i);
    }
}
 
// Function to count the
// minimum factor jump
int solve(int arr[], int n)
{
 
    // Initialise minimum jumps to
    // reach each cell as INT_MAX
    for (int i = 0; i <= 100005; i++) {
        dp[i] = INT_MAX;
    }
 
    // 0 jumps required to
    // reach the first cell
    dp[0] = 0;
 
    // Iterate over all cells
    for (int i = 0; i < n; i++) {
        // calculating for each jump
        for (auto j : factors[arr[i]]) {
            // If a cell is in bound
            if (i + j < n)
                dp[i + j] = min(dp[i + j], 1 + dp[i]);
        }
    }
    // Return minimum jumps
    // to reach last cell
    return dp[n - 1];
}
 
// Driver code
int main()
{
    // Pre-calculating the factors
    precompute();
    int arr[] = { 2, 8, 16, 55, 99, 100 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << solve(arr, n);
}

Java

// Java program for bottom up approach
import java.util.*;
 
class GFG{
 
// Vector to store factors of each integer
@SuppressWarnings("unchecked")
static Vector<Integer> []factors = new Vector[100005];
 
// Initialize the dp array
static int []dp = new int[100005];
 
// Precompute all the
// factors of every integer
static void precompute()
{
    for(int i = 1; i <= 100000; i++) 
    {
        for(int j = i; j <= 100000; j += i)
            factors[j].add(i);
    }
}
 
// Function to count the
// minimum factor jump
static int solve(int arr[], int n)
{
     
    // Initialise minimum jumps to
    // reach each cell as Integer.MAX_VALUE
    for(int i = 0; i < 100005; i++) 
    {
        dp[i] = Integer.MAX_VALUE;
    }
 
    // 0 jumps required to
    // reach the first cell
    dp[0] = 0;
 
    // Iterate over all cells
    for(int i = 0; i < n; i++)
    {
         
        // Calculating for each jump
        for(int j : factors[arr[i]]) 
        {
             
            // If a cell is in bound
            if (i + j < n)
                dp[i + j] = Math.min(dp[i + j], 
                                        1 + dp[i]);
        }
    }
     
    // Return minimum jumps
    // to reach last cell
    return dp[n - 1];
}
 
// Driver code
public static void main(String[] args)
{
    for(int i = 0; i < factors.length; i++)
        factors[i] = new Vector<Integer>();
         
    // Pre-calculating the factors
    precompute();
    int arr[] = { 2, 8, 16, 55, 99, 100 };
    int n = arr.length;
 
    // Function call
    System.out.print(solve(arr, n));
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program for bottom up approach
  
# Vector to store factors of each integer
factors=[[] for i in range(100005)];
  
# Initialize the dp array
dp=[1000000000 for i in range(100005)];
  
# Precompute all the
# factors of every integer
def precompute():
     
    for i in range(1, 100001):
         
        for j in range(i, 100001, i):
     
            factors[j].append(i);
      
# Function to count the
# minimum factor jump
def solve(arr, n):
   
    # 0 jumps required to
    # reach the first cell
    dp[0] = 0;
  
    # Iterate over all cells
    for i in range(n):
     
        # calculating for each jump
        for j in factors[arr[i]]:
         
            # If a cell is in bound
            if (i + j < n):
                dp[i + j] = min(dp[i + j], 1 + dp[i]);
         
    # Return minimum jumps
    # to reach last cell
    return dp[n - 1];
  
# Driver code
if __name__=='__main__':
     
    # Pre-calculating the factors
    precompute();
    arr = [ 2, 8, 16, 55, 99, 100 ]
    n=len(arr)
  
    # Function call
    print(solve(arr,n))
     
    # This code is contributed by pratham76

C#

// C# program for bottom up approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Vector to store factors of each integer
static List<List<int>> factors = new List<List<int>>();
 
// Initialize the dp array
static int[] dp;
 
// Precompute all the
// factors of every integer
static void precompute()
{
    for(int i = 1; i <= 100000; i++) 
    {
        for(int j = i; j <= 100000; j += i)
            factors[j].Add(i);
    }
}
 
// Function to count the
// minimum factor jump
static int solve(int[] arr, int n)
{
     
    // Initialise minimum jumps to
    // reach each cell as Integer.MAX_VALUE
    for(int i = 0; i < 100005; i++) 
    {
        dp[i] = int.MaxValue;
    }
 
    // 0 jumps required to
    // reach the first cell
    dp[0] = 0;
 
    // Iterate over all cells
    for(int i = 0; i < n; i++)
    {
         
        // Calculating for each jump
        foreach(int j in factors[arr[i]]) 
        {
             
            // If a cell is in bound
            if (i + j < n)
                dp[i + j] = Math.Min(dp[i + j], 
                                        1 + dp[i]);
        }
    }
     
    // Return minimum jumps
    // to reach last cell
    return dp[n - 1];
}
 
// Driver code
static public void Main ()
{
    for(int i = 0; i < 100005; i++)
        factors.Add(new List<int>());
     
    dp = new int[100005];
     
    // Pre-calculating the factors
    precompute();
    int[] arr = { 2, 8, 16, 55, 99, 100 };
    int n = arr.Length;
     
    // Function call
    Console.Write(solve(arr, n));
}
}
 
// This code is contributed by offbeat

Javascript

<script>
 
// Javascript program for bottom up approach
 
// Vector to store factors of each integer
var factors = Array.from(Array(100005), ()=>Array());
 
// Initialize the dp array
var dp = Array(100005);
 
// Precompute all the
// factors of every integer
function precompute()
{
    for (var i = 1; i <= 100000; i++) {
        for (var j = i; j <= 100000; j += i)
            factors[j].push(i);
    }
}
 
// Function to count the
// minimum factor jump
function solve(arr, n)
{
 
    // Initialise minimum jumps to
    // reach each cell as INT_MAX
    for (var i = 0; i <= 100005; i++) {
        dp[i] = 1000000000;
    }
 
    // 0 jumps required to
    // reach the first cell
    dp[0] = 0;
 
    // Iterate over all cells
    for (var i = 0; i < n; i++) {
        // calculating for each jump
        for (var j of factors[arr[i]]) {
            // If a cell is in bound
            if (i + j < n)
                dp[i + j] = Math.min(dp[i + j], 1 + dp[i]);
        }
    }
    // Return minimum jumps
    // to reach last cell
    return dp[n - 1];
}
 
 // Driver code
 // Pre-calculating the factors
 precompute();
 var arr = [2, 8, 16, 55, 99, 100];
 var n = arr.length
 // Function call
 document.write( solve(arr, n));
 
</script>

Output

Time Complexity: O(N²)

Auxiliary Space: O(100005)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!