Splitting an array with coprime products
What is co prime? Coprime is determined between two integers which have highest common factor (HCF) will be always 1. For example.
{4, 7} HCF 1
{5, 11} HCF 1
{7, 15} HCF 1
In our problem splitting an array into two subarrays which products will be consequently co prime. For example.
Array {3, 4, 7, 8, 15, 29, 31}
Coprime product A
(3 * 4 * 7 * 8 * 15) (29 * 31)
⥥ ⥥
(10080) (899)
Coprime product B
(3 * 4 * 7 * 8 * 15 * 29) , (31)
⥥ ⥥
(292320) (31)
Both HCF is 1
Here given code implementation process.
// C program
// Splitting an array with coprime products
#include <stdio.h>
// Find GCD of two numbers
int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
return gcd(b, a % b);
}
// Print the all subarrays which is contains coprime product
void splitting(int arr[], int n)
{
int count = 0;
if(n > 1)
{
// Auxiliary space
int prefix[n];
int suffix[n];
// Get first element into prefix
prefix[0] = arr[0];
// Get last element into suffix
suffix[n-1] = arr[n-1];
int i = 1;
while(i < n)
{
// Calculate prefix [i*(i+1)*(i+2)..]
prefix[i] = arr[i] * prefix[i-1];
// Calculate suffix [n*(n-1)*(n-2)..]
suffix[n-1-i] = arr[n-1-i] * suffix[n-i];
// Change index location
i ++;
}
for (i = 0; i < n-1; ++i)
{
if(gcd(prefix[i],suffix[i+1])==1)
{
// Print subarray size
printf("\n (0-%d) (%d,%d) ",i,i+1,n-1);
// Change result status
count += 1;
}
}
}
if(count==0)
{
// When no coprime subarray
printf("\n None");
}
else
{
printf("\n Total result %d",count);
}
}
int main()
{
// Define integer elements
int arr[] = {3, 4, 7, 8, 15 ,29, 31};
// Get the number of elements
int n = sizeof(arr)/sizeof(arr[0]);
// First
// (3 * 4 * 7 * 8 * 15) , (29 * 31)
// ⥥ ⥥
//
// (10080) (899) HCF 1
// Second
// (3 * 4 * 7 * 8 * 15 * 29) , (31)
// ⥥ ⥥
//
// (292320) (31) HCF 1
// Test
splitting(arr,n);
return 0;
}input
(0-4) (5,6)
(0-5) (6,6)
Total result 2/*
Java Program
Splitting an array with coprime products
*/
public class Coprime
{
// Find GCD of two numbers
public int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
return gcd(b, a % b);
}
// Print the all subarrays which is contains coprime product
public void splitting(int[] arr, int n)
{
int count = 0;
if (n > 1)
{
// Auxiliary space
int[] prefix = new int[n];
int[] suffix = new int[n];
// Get first element into prefix
prefix[0] = arr[0];
// Get last element into suffix
suffix[n - 1] = arr[n - 1];
int i = 1;
while (i < n)
{
// Calculate prefix [i*(i+1)*(i+2)..]
prefix[i] = arr[i] *prefix[i - 1];
// Calculate suffix [n*(n-1)*(n-2)..]
suffix[n - 1 - i] = arr[n - 1 - i] *suffix[n - i];
// Change index location
i++;
}
for (i = 0; i < n - 1; ++i)
{
if (gcd(prefix[i], suffix[i + 1]) == 1)
{
// Print subarray size
System.out.print("\n (0-" + i + ") (" + (i + 1) + "," + (n - 1) + ") ");
// Change result counter
count++;
}
}
}
if (count == 0)
{
// When no coprime subarray
System.out.print("\n None");
}
else
{
// When no coprime subarray
System.out.print("\n Total result " + count);
}
}
public static void main(String[] args)
{
Coprime task = new Coprime();
// Define integer elements
int[] arr = {
3 , 4 , 7 , 8 , 15 , 29 , 31
};
// Get the number of elements
int n = arr.length;
// First
// (3 *4 *7 *8 *15) , (29 *31)
// ⥥ ⥥
//
// (10080) (899) HCF 1
// Second
// (3 *4 *7 *8 *15 *29) , (31)
// ⥥ ⥥
//
// (292320) (31) HCF 1
// Test
task.splitting(arr, n);
}
}input
(0-4) (5,6)
(0-5) (6,6)
Total result 2// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Splitting an array with coprime products
*/
class Coprime
{
public:
// Find GCD of two numbers
int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
return this->gcd(b, a % b);
}
// Print the all subarrays which is contains coprime product
void splitting(int arr[], int n)
{
int count = 0;
if (n > 1)
{
// Auxiliary space
int prefix[n];
int suffix[n];
// Get first element into prefix
prefix[0] = arr[0];
// Get last element into suffix
suffix[n - 1] = arr[n - 1];
int i = 1;
while (i < n)
{
// Calculate prefix [i*(i+1)*(i+2)..]
prefix[i] = arr[i] *prefix[i - 1];
// Calculate suffix [n*(n-1)*(n-2)..]
suffix[n - 1 - i] = arr[n - 1 - i] *suffix[n - i];
// Change index location
i++;
}
for (i = 0; i < n - 1; ++i)
{
if (this->gcd(prefix[i], suffix[i + 1]) == 1)
{
// Print subarray size
cout << "\n (0-" << i << ") (" << (i + 1) << "," << (n - 1) << ") ";
// Change result counter
count++;
}
}
}
if (count == 0)
{
// When no coprime subarray
cout << "\n None";
}
else
{
// When no coprime subarray
cout << "\n Total result " << count;
}
}
};
int main()
{
Coprime *task = new Coprime();
// Define integer elements
int arr[] = {
3 , 4 , 7 , 8 , 15 , 29 , 31
};
// Get the number of elements
int n = sizeof(arr) / sizeof(arr[0]);
// First
// (3 *4 *7 *8 *15) , (29 *31)
// ⥥ ⥥
//
// (10080) (899) HCF 1
// Second
// (3 *4 *7 *8 *15 *29) , (31)
// ⥥ ⥥
//
// (292320) (31) HCF 1
// Test
task->splitting(arr, n);
return 0;
}input
(0-4) (5,6)
(0-5) (6,6)
Total result 2// Include namespace system
using System;
/*
Csharp Program
Splitting an array with coprime products
*/
public class Coprime
{
// Find GCD of two numbers
public int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
return this.gcd(b, a % b);
}
// Print the all subarrays which is contains coprime product
public void splitting(int[] arr, int n)
{
int count = 0;
if (n > 1)
{
// Auxiliary space
int[] prefix = new int[n];
int[] suffix = new int[n];
// Get first element into prefix
prefix[0] = arr[0];
// Get last element into suffix
suffix[n - 1] = arr[n - 1];
int i = 1;
while (i < n)
{
// Calculate prefix [i*(i+1)*(i+2)..]
prefix[i] = arr[i] * prefix[i - 1];
// Calculate suffix [n*(n-1)*(n-2)..]
suffix[n - 1 - i] = arr[n - 1 - i] * suffix[n - i];
// Change index location
i++;
}
for (i = 0; i < n - 1; ++i)
{
if (this.gcd(prefix[i], suffix[i + 1]) == 1)
{
// Print subarray size
Console.Write("\n (0-" + i + ") (" + (i + 1) + "," + (n - 1) + ") ");
// Change result counter
count++;
}
}
}
if (count == 0)
{
// When no coprime subarray
Console.Write("\n None");
}
else
{
// When no coprime subarray
Console.Write("\n Total result " + count);
}
}
public static void Main(String[] args)
{
Coprime task = new Coprime();
// Define integer elements
int[] arr = {
3 , 4 , 7 , 8 , 15 , 29 , 31
};
// Get the number of elements
int n = arr.Length;
// First
// (3 *4 *7 *8 *15) , (29 *31)
// ⥥ ⥥
//
// (10080) (899) HCF 1
// Second
// (3 *4 *7 *8 *15 *29) , (31)
// ⥥ ⥥
//
// (292320) (31) HCF 1
// Test
task.splitting(arr, n);
}
}input
(0-4) (5,6)
(0-5) (6,6)
Total result 2<?php
/*
Php Program
Splitting an array with coprime products
*/
class Coprime
{
// Find GCD of two numbers
public function gcd($a, $b)
{
if ($b == 0)
{
return $a;
}
return $this->gcd($b, $a % $b);
}
// Print the all subarrays which is contains coprime product
public
function splitting($arr, $n)
{
$count = 0;
if ($n > 1)
{
// Auxiliary space
$prefix = array_fill(0, $n, 0);
$suffix = array_fill(0, $n, 0);
// Get first element into prefix
$prefix[0] = $arr[0];
// Get last element into suffix
$suffix[$n - 1] = $arr[$n - 1];
$i = 1;
while ($i < $n)
{
// Calculate prefix [i*(i+1)*(i+2)..]
$prefix[$i] = $arr[$i] * $prefix[$i - 1];
// Calculate suffix [n*(n-1)*(n-2)..]
$suffix[$n - 1 - $i] = $arr[$n - 1 - $i] * $suffix[$n - $i];
// Change index location
$i++;
}
for ($i = 0; $i < $n - 1; ++$i)
{
if ($this->gcd($prefix[$i], $suffix[$i + 1]) == 1)
{
// Print subarray size
echo "\n (0-". $i .") (". ($i + 1) .",". ($n - 1) .") ";
// Change result counter
$count++;
}
}
}
if ($count == 0)
{
// When no coprime subarray
echo "\n None";
}
else
{
// When no coprime subarray
echo "\n Total result ". $count;
}
}
}
function main()
{
$task = new Coprime();
// Define integer elements
$arr = array(3, 4, 7, 8, 15, 29, 31);
// Get the number of elements
$n = count($arr);
// First
// (3 *4 *7 *8 *15) , (29 *31)
// ⥥ ⥥
//
// (10080) (899) HCF 1
// Second
// (3 *4 *7 *8 *15 *29) , (31)
// ⥥ ⥥
//
// (292320) (31) HCF 1
// Test
$task->splitting($arr, $n);
}
main();input
(0-4) (5,6)
(0-5) (6,6)
Total result 2/*
Node JS Program
Splitting an array with coprime products
*/
class Coprime
{
// Find GCD of two numbers
gcd(a, b)
{
if (b == 0)
{
return a;
}
return this.gcd(b, a % b);
}
// Print the all subarrays which is contains coprime product
splitting(arr, n)
{
var count = 0;
if (n > 1)
{
// Auxiliary space
var prefix = Array(n).fill(0);
var suffix = Array(n).fill(0);
// Get first element into prefix
prefix[0] = arr[0];
// Get last element into suffix
suffix[n - 1] = arr[n - 1];
var i = 1;
while (i < n)
{
// Calculate prefix [i*(i+1)*(i+2)..]
prefix[i] = arr[i] * prefix[i - 1];
// Calculate suffix [n*(n-1)*(n-2)..]
suffix[n - 1 - i] = arr[n - 1 - i] * suffix[n - i];
// Change index location
i++;
}
for (i = 0; i < n - 1; ++i)
{
if (this.gcd(prefix[i], suffix[i + 1]) == 1)
{
// Print subarray size
process.stdout.write("\n (0-" + i + ") (" + (i + 1) + "," + (n - 1) + ") ");
// Change result counter
count++;
}
}
}
if (count == 0)
{
// When no coprime subarray
process.stdout.write("\n None");
}
else
{
// When no coprime subarray
process.stdout.write("\n Total result " + count);
}
}
}
function main()
{
var task = new Coprime();
// Define integer elements
var arr = [3, 4, 7, 8, 15, 29, 31];
// Get the number of elements
var n = arr.length;
// First
// (3 *4 *7 *8 *15) , (29 *31)
// ⥥ ⥥
//
// (10080) (899) HCF 1
// Second
// (3 *4 *7 *8 *15 *29) , (31)
// ⥥ ⥥
//
// (292320) (31) HCF 1
// Test
task.splitting(arr, n);
}
main();input
(0-4) (5,6)
(0-5) (6,6)
Total result 2# Python 3 Program
# Splitting an array with coprime products
class Coprime :
# Find GCD of two numbers
def gcd(self, a, b) :
if (b == 0) :
return a
return self.gcd(b, a % b)
# Print the all sublists which is contains coprime product
def splitting(self, arr, n) :
count = 0
if (n > 1) :
prefix = [0] * (n)
suffix = [0] * (n)
# Get first element into prefix
prefix[0] = arr[0]
# Get last element into suffix
suffix[n - 1] = arr[n - 1]
i = 1
while (i < n) :
# Calculate prefix[i * (i + 1) * (i + 2)..]
prefix[i] = arr[i] * prefix[i - 1]
# Calculate suffix[n * (n - 1) * (n - 2)..]
suffix[n - 1 - i] = arr[n - 1 - i] * suffix[n - i]
# Change index location
i += 1
i = 0
while (i < n - 1) :
if (self.gcd(prefix[i], suffix[i + 1]) == 1) :
# Print sublist size
print("\n (0-", i ,") (", (i + 1) ,",", (n - 1) ,") ", end = "")
# Change result counter
count += 1
i += 1
if (count == 0) :
# When no coprime sublist
print("\n None", end = "")
else :
# When no coprime sublist
print("\n Total result ", count, end = "")
def main() :
task = Coprime()
arr = [3, 4, 7, 8, 15, 29, 31]
n = len(arr)
# First
# (3 * 4 * 7 * 8 * 15), (29 * 31)
# ⥥ ⥥
# (10080) (899) HCF 1
# Second
# (3 * 4 * 7 * 8 * 15 * 29), (31)
# ⥥ ⥥
# (292320) (31) HCF 1
# Test
task.splitting(arr, n)
if __name__ == "__main__": main()input
(0- 4 ) ( 5 , 6 )
(0- 5 ) ( 6 , 6 )
Total result 2# Ruby Program
# Splitting an array with coprime products
class Coprime
# Find GCD of two numbers
def gcd(a, b)
if (b == 0)
return a
end
return self.gcd(b, a % b)
end
# Print the all subarrays which is contains coprime product
def splitting(arr, n)
count = 0
if (n > 1)
# Auxiliary space
prefix = Array.new(n) {0}
suffix = Array.new(n) {0}
# Get first element into prefix
prefix[0] = arr[0]
# Get last element into suffix
suffix[n - 1] = arr[n - 1]
i = 1
while (i < n)
# Calculate prefix[i * (i + 1) * (i + 2)..]
prefix[i] = arr[i] * prefix[i - 1]
# Calculate suffix[n * (n - 1) * (n - 2)..]
suffix[n - 1 - i] = arr[n - 1 - i] * suffix[n - i]
# Change index location
i += 1
end
i = 0
while (i < n - 1)
if (self.gcd(prefix[i], suffix[i + 1]) == 1)
# Print subarray size
print("\n (0-", i ,") (", (i + 1) ,",", (n - 1) ,") ")
# Change result counter
count += 1
end
i += 1
end
end
if (count == 0)
# When no coprime subarray
print("\n None")
else
# When no coprime subarray
print("\n Total result ", count)
end
end
end
def main()
task = Coprime.new()
# Define integer elements
arr = [3, 4, 7, 8, 15, 29, 31]
# Get the number of elements
n = arr.length
# First
# (3 * 4 * 7 * 8 * 15), (29 * 31)
# ⥥ ⥥
# (10080) (899) HCF 1
# Second
# (3 * 4 * 7 * 8 * 15 * 29), (31)
# ⥥ ⥥
# (292320) (31) HCF 1
# Test
task.splitting(arr, n)
end
main()input
(0-4) (5,6)
(0-5) (6,6)
Total result 2/*
Scala Program
Splitting an array with coprime products
*/
class Coprime()
{
// Find GCD of two numbers
def gcd(a: Int, b: Int): Int = {
if (b == 0)
{
return a;
}
return gcd(b, a % b);
}
// Print the all subarrays which is contains coprime product
def splitting(arr: Array[Int], n: Int): Unit = {
var count: Int = 0;
if (n > 1)
{
// Auxiliary space
var prefix: Array[Int] = Array.fill[Int](n)(0);
var suffix: Array[Int] = Array.fill[Int](n)(0);
// Get first element into prefix
prefix(0) = arr(0);
// Get last element into suffix
suffix(n - 1) = arr(n - 1);
var i: Int = 1;
while (i < n)
{
// Calculate prefix [i*(i+1)*(i+2)..]
prefix(i) = arr(i) * prefix(i - 1);
// Calculate suffix [n*(n-1)*(n-2)..]
suffix(n - 1 - i) = arr(n - 1 - i) * suffix(n - i);
// Change index location
i += 1;
}
i = 0;
while (i < n - 1)
{
if (gcd(prefix(i), suffix(i + 1)) == 1)
{
// Print subarray size
print("\n (0-" + i + ") (" + (i + 1) + "," + (n - 1) + ") ");
// Change result counter
count += 1;
}
i += 1
}
}
if (count == 0)
{
// When no coprime subarray
print("\n None");
}
else
{
// When no coprime subarray
print("\n Total result " + count);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Coprime = new Coprime();
// Define integer elements
var arr: Array[Int] = Array(3, 4, 7, 8, 15, 29, 31);
// Get the number of elements
var n: Int = arr.length;
// First
// (3 *4 *7 *8 *15) , (29 *31)
// ⥥ ⥥
//
// (10080) (899) HCF 1
// Second
// (3 *4 *7 *8 *15 *29) , (31)
// ⥥ ⥥
//
// (292320) (31) HCF 1
// Test
task.splitting(arr, n);
}
}input
(0-4) (5,6)
(0-5) (6,6)
Total result 2/*
Swift 4 Program
Splitting an array with coprime products
*/
class Coprime
{
// Find GCD of two numbers
func gcd(_ a: Int, _ b: Int)->Int
{
if (b == 0)
{
return a;
}
return self.gcd(b, a % b);
}
// Print the all subarrays which is contains coprime product
func splitting(_ arr: [Int], _ n: Int)
{
var count: Int = 0;
if (n > 1)
{
// Auxiliary space
var prefix: [Int] = Array(repeating: 0, count: n);
var suffix: [Int] = Array(repeating: 0, count: n);
// Get first element into prefix
prefix[0] = arr[0];
// Get last element into suffix
suffix[n - 1] = arr[n - 1];
var i: Int = 1;
while (i < n)
{
// Calculate prefix [i*(i+1)*(i+2)..]
prefix[i] = arr[i] * prefix[i - 1];
// Calculate suffix [n*(n-1)*(n-2)..]
suffix[n - 1 - i] = arr[n - 1 - i] * suffix[n - i];
// Change index location
i += 1;
}
i = 0;
while (i < n - 1)
{
if (self.gcd(prefix[i], suffix[i + 1]) == 1)
{
// Print subarray size
print("\n (0-", i ,") (", (i + 1) ,",", (n - 1) ,") ", terminator: "");
// Change result counter
count += 1;
}
i += 1
}
}
if (count == 0)
{
// When no coprime subarray
print("\n None", terminator: "");
}
else
{
// When no coprime subarray
print("\n Total result ", count, terminator: "");
}
}
}
func main()
{
let task: Coprime = Coprime();
// Define integer elements
let arr: [Int] = [3, 4, 7, 8, 15, 29, 31];
// Get the number of elements
let n: Int = arr.count;
// First
// (3 *4 *7 *8 *15) , (29 *31)
// ⥥ ⥥
//
// (10080) (899) HCF 1
// Second
// (3 *4 *7 *8 *15 *29) , (31)
// ⥥ ⥥
//
// (292320) (31) HCF 1
// Test
task.splitting(arr, n);
}
main();input
(0- 4 ) ( 5 , 6 )
(0- 5 ) ( 6 , 6 )
Total result 2/*
Kotlin Program
Splitting an array with coprime products
*/
class Coprime
{
// Find GCD of two numbers
fun gcd(a: Int, b: Int): Int
{
if (b == 0)
{
return a;
}
return this.gcd(b, a % b);
}
// Print the all subarrays which is contains coprime product
fun splitting(arr: Array < Int > , n: Int): Unit
{
var count: Int = 0;
if (n > 1)
{
// Auxiliary space
var prefix: Array < Int > = Array(n)
{
0
};
var suffix: Array < Int > = Array(n)
{
0
};
// Get first element into prefix
prefix[0] = arr[0];
// Get last element into suffix
suffix[n - 1] = arr[n - 1];
var i: Int = 1;
while (i < n)
{
// Calculate prefix [i*(i+1)*(i+2)..]
prefix[i] = arr[i] * prefix[i - 1];
// Calculate suffix [n*(n-1)*(n-2)..]
suffix[n - 1 - i] = arr[n - 1 - i] * suffix[n - i];
// Change index location
i += 1;
}
i = 0;
while (i < n - 1)
{
if (this.gcd(prefix[i], suffix[i + 1]) == 1)
{
// Print subarray size
print("\n (0-" + i + ") (" + (i + 1) + "," + (n - 1) + ") ");
// Change result counter
count += 1;
}
i += 1
}
}
if (count == 0)
{
// When no coprime subarray
print("\n None");
}
else
{
// When no coprime subarray
print("\n Total result " + count);
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Coprime = Coprime();
// Define integer elements
val arr: Array < Int > = arrayOf(3, 4, 7, 8, 15, 29, 31);
// Get the number of elements
val n: Int = arr.count();
// First
// (3 *4 *7 *8 *15) , (29 *31)
// ⥥ ⥥
//
// (10080) (899) HCF 1
// Second
// (3 *4 *7 *8 *15 *29) , (31)
// ⥥ ⥥
//
// (292320) (31) HCF 1
// Test
task.splitting(arr, n);
}input
(0-4) (5,6)
(0-5) (6,6)
Total result 2
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment