1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
n200080 [17]
3 years ago
9

Given an array A of size N, and a number K. Task is to find out if it is possible to partition the array A into K contiguous sub

arrays such that the sum of elements within each of these subarrays is the same.Prerequisite : Count the number of ways to divide an array into three contiguous parts having equal sum
Computers and Technology
1 answer:
Dennis_Churaev [7]3 years ago
6 0

Answer: First lets solve the Prerequisite part

Lets say we have an input array of N numbers {3,2,5,0,5}. We have to  find number of ways to divide this array into 3 contiguous parts having equal sum. So the output for the above input array will be 2 as there are 2 ways to divide the array. One is (3,2),(5),(0,5) and the other is (3,2),(5,0),(5).

Following are the steps to achieve the above outcome.

  • Let p and q point to the index of array such that sum of array elements from 0 to p-1 is equal to sum of array elements from p to q which is equal to the sum of array elements from q+1 to N-1.  
  • If we see the array we can tell that the sum of 3 contiguous parts is 5. So the condition would be that sum of all array elements should be equal to 5 or sum of each contiguous part is equal to sum of all array elements divided by 5.
  • Now create 2 arrays prefix and postfix of size of input array. Index p of prefix array carries sum of input array elements from index 0 to index p. Index q of postfix array carries sum of input array elements from index p to index N-1
  • Next move through prefix array suppose at the index p of prefix array : value of prefix array == (sum of all input array elements)/5.
  • Search the postfix array for p index found above. Search it starting from p+2 index. Increment the count variable by 1 when the value of postfix array =(sum of all input array elements)/5 and push that index of postfix array into a new array. Use searching algorithm on new array to calculate number of values in postfix array.

Now lets solve the main task

We have an array A of size N and a number K. where A[]= {1,6,3,4,7} N=5 and K=3. We have to find if its possible to partition A into 3 contiguous subarrays such that sum of elements in each subarray is the same. It is possible in this example. Here we have 3 partitions (1,6),(3,4),(7) and sum of each of subarrays is same (1+6) (3+4) (7) which is 7.

Following are the steps to achieve the above outcome.

  • In order create K contiguous subarrays where each subarray has equal sum, first check the condition that sum of all elements in the given array should be divisible by K. Lets name another array as arrsum that will be the size of array A. Traverse A from first to  last index and keep adding current element of A with previous value in arrsum. Example A contains (1,6,3,4,7} and arrsum has {1,7,10,14,21}
  • If the above condition holds, now check the condition that each subarray or partition has equal sum. Suppose we represent sum1 to sum of all element in given array and sum2 of sum of each partition then: sum2 = sum2 / K.
  • Compare arrsum to subarray, begining from index 0 and when it becomes equal to sum2 this means that end of one subarray is reached. Lets say index q is pointing to that subarray.
  • Now from q+1 index find p index in which following condition holds: (arrsum[p] - arrsum[q])=sum2
  • Continue the above step untill K contigous subarrays are found. This loop will break if, at some index, sum2 of any subarray gets greater than required sum2 (as we know that every contiguous subarray should contain equal sum).

A easier function Partition for this task:

int Partition(int A[], int N, int k) // A arra y of size N and number k

{      int sum = 0;    int count = 0;  //variables initialization    

   for(int j = 0; j < N; j++)  //Loop that calculates sum of A

  sum = sum + A[j];        

  if(sum % k != 0) //checks condition that sum of all elements of A should be //divisible by k

   return 0;        

   sum = sum / k;  

   int sum2 = 0;  //represents sum of subarray

  for(int j = 0; j < N; j++) // Loop on subarrays

  {      sum2=sum2 + A[j];  

   if(sum2 == sum)    { //these lines locates subarrays and sum of elements //of subarrays should be equal

       sum2 = 0;  

       count++;  }  }  

/*calculate count of subarrays whose

sum is equal to (sum of complete array/ k.)

if count == k print Yes else print No*/

if(count == k)    

return 1;  

   else

   return 0;  }

You might be interested in
The difference between page break and section brek​
Lena [83]
Page break- A point that is marked where the page is about to end and the new page is about to begin.


Section break- break between two paragraphs, or extra space between two sections.

I hoped that helped.
7 0
3 years ago
Read 2 more answers
The standard qwerty keyboard has 47 keys that can place characters on the screen. each of these keys can also display a second c
stepladder [879]

The standard QWERTY keyboard has 47 keys that can place characters on the screen. Each of these keys can also display a second character by holding the "Shift" key at the same time. How many bits would you need to encode everything that could be typed on this keyboard?

The answer is 7 bits

7 0
3 years ago
Read 2 more answers
________ returns the last character in a StringBuilder variable named strBuf? Select one: A. strBuf.charAt(strBuf.length() - 1)
Lunna [17]

Answer:

A

Explanation:

strBuf.charAt(strBuf.length() - 1)

4 0
3 years ago
Why does temperature decrease with higher altitude?
Lelu [443]
It's B.

As you go up, the air thins out, meaning it is less dense. Since there are less molecules that can transfer heat, the temperature is lower.
4 0
3 years ago
Write a method so that the main() code below can be replaced by the simpler code that calls method mphAndMinutesToMiles(). Origi
defon

ANSWER

The JAVA program after simplification is as below.

import java.util.Scanner;

public class CalcMiles {

   

   // variables declaration

   static double milesPerHour;

   static double minutesTraveled;      

   static double hoursTraveled;

   static double milesTraveled;

   

   // method declared static

   public static void mphAndMinutesToMiles(double speed, double mins)

   {

       // computations to calculate distance travelled

       hoursTraveled = mins / 60.0;

       milesTraveled = hoursTraveled * speed;

       

       // result displayed on the screen  

     System.out.println("Miles: " + milesTraveled);

   }

   

   // Scanner object created inside main()

   // user input taken inside main()

   public static void main(String [] args)

   {

       Scanner scnr = new Scanner(System.in);

       System.out.println("Enter miles travelled per hour ");

       milesPerHour = scnr.nextDouble();

       System.out.println("Enter minutes required to travel ");

       minutesTraveled = scnr.nextDouble();

       

       mphAndMinutesToMiles(milesPerHour, minutesTraveled);

       

   }

}

OUTPUT

Enter miles travelled per hour  

2.3

Enter minutes required to travel  

1234

Miles: 47.30333333333333

EXPLANATION

The program is simplified as explained below.

1. User input is taken using the object of Scanner class.

2. This object of Scanner class can only be created inside main() method hence, user input can only be taken inside main().

3. The code to calculate the result is separated in another method, mphAndMinutesToMiles(). This method is declared with return type void since no value is returned.

4. After user input is taken in main() for miles travelled per hour and minutes required to travel, these values are passed as parameters to the mphAndMinutesToMiles() method.

5. These parameters are used in calculation part. The total miles travelled in total hours (obtained from minutes), is calculated. The code to display the result is added to this method.

6. Inside the main method, only the code to create Scanner object, code to take user input for two variables and code to call the mphAndMinutesToMiles() is included.

7. The variables are declared as static and declared at class level.

8. No variable is declared inside any of the two methods.

5 0
3 years ago
Read 2 more answers
Other questions:
  • What determines the method of controlling motor speed?
    5·1 answer
  • Word 2013 opens, by default, on a blank document?
    13·2 answers
  • What is an identifier? Give an example of an identifier.
    13·1 answer
  • Part 1 Create a program that asks the user for a temperature in Fahrenheit, and then prints the temperature in Celsius. Search t
    12·1 answer
  • The area on your screen where you can access the tab and menu options for word is called what?
    8·2 answers
  • Whic flag has a special role in debuging
    6·1 answer
  • Users of Adobe Reader, created by Adobe Systems Incorporated, are prompted to provide feedback on their experiences with the sof
    7·1 answer
  • WILL MARK BRAINLIEST FOR ANYONES ANSWER!
    12·1 answer
  • EMERGENCY- I am giving 55 points for this, please help. WITH working out
    7·1 answer
  • The first time that a particular visitor loads a web site page is called a(n) _____.
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!