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







© 2021, kalkicode.com, All rights reserved