What are important math topics required for interview preparation?

Some important maths concepts a programmer should focus on includes Mathematical Induction, Calculus, Probability, and Statistics, Graph Theory, etc.

What is array partitioning?

In a given array of objects, in random order. You want to split the array in half, with the lower half containing objects that match the condition and the top half containing things that do not. This is called the partitioning of an array.

Divide 1 to n into two groups with a minimum sum difference

Question

Given a positive integer n, n > 2. The task is to divide numbers from 1 to n in two groups such that the absolute difference of the sum of each group is minimum.

Input: An integer n.

Output: Print the size of any of the two groups in the first line, then print the elements of that group in the second line. Similarly, print the size of the remaining group in the next line and then its elements.

The questions you should ask the interviewer:

What is the constraint on n?
If there are multiple groups possible, how to give output in that case?

Examples:

Alert Ninjas: Don't stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide.

Input: 5
Output: 2
5 2
3
4 3 1

Explanation: Group 1 has sum 7, and group 2 has sum 8.

Their absolute difference is one, which is the smallest possible.

Multiple correct responses are possible. Other groups can be (1, 2, 5) and (3, 4).

Input: 6

Output: 4

5 3 2 1
2
6 4

Recommended: Please try to solve it yourself before moving on to the solution.

Also see, Euclid GCD Algorithm

Solution:

Approach 1:

Idea: The idea is to use the fact that we can always divide 1 to n into two groups such that the absolute minimum difference of the sum is either 0 or 1. As the sum of all 'N' elements will be either odd or even. So partition will be,

if the total sum is odd => odd = odd + even, in this case, the absolute minimum difference can be 1.
if the total sum is even => even = o+o / e+ e, in this case, the absolute minimum difference can be 0.

Implementation

Consider two groups Group1 and Group2.
We define a variable halfSum as half of the sum of n components.
Now, in a loop from n to 1, enter i into group1 if the sum of the elements in group1 does not exceed halfSum; otherwise, insert that i into group2.

C++

#include <bits/stdc++.h>
using namespace std;

// To print the given output.
void print(vector<int> &A)
{

cout << A.size() << endl;

for (int i = 0; i < A.size(); i++)
cout << A[i] << " ";
cout << endl;
}

void findGroup(int n)
{

// sum of numbers 1 to n is n*(n+1)/2. Proof by induction.
int sum = n * (n + 1) / 2;

// Sum of elements of group1.
int halfSum = sum / 2;
int sumGroup1 = 0;
vector<int> group1, group2;

for (int i = n; i > 0; i--) {

if (sumGroup1 + i <= halfSum) {

group1.push_back(i);
sumGroup1 = sumGroup1 + i;
}
else {
group2.push_back(i);
}
}

// Print both the groups
print(group1);
print(group2);
}

// Driver program to test above functions
int main()
{
int n = 6;
findGroup(n);
return 0;
}

Output:

Time Complexity: O(N) as we are only using a for loop from range 1 to n, which uses O(N) time.

Space Complexity: The space complexity is O(N) as we are using extra space to create two groups of maximum size n.

Approach2:

Idea: As the elements are consecutive, we can always say that in a series of four continuous elements, the sum of extremes is always equal to the sum of middle elements.

Example:

1 2 3 4

1+4 = 2+3 = 5

5 6 7 8

5+8 = 6+7 = 13

And so on…

Implementation:

Check if n is odd or even.
If odd, divide the elements 1 to n in pairs. E.g., add (1,2) in group1, (3,4) in group2, then (5,6) in group1, and so on.
If even, consider the groups of 4. Add the extremes to one group and the central elements to the other group. There can be a chance that two elements remain in the end; add one-one element to each group.

C++

    // if n is odd.
  if( n % 2 ){

int flag = 1;
  for( int i = 1 ; i <= n ; i+=2){

  if(flag){
  if( i+1 <= n){
group1.push_back(i);
group1.push_back(i+1);
}
  else{
group1.push_back(i);
}
flag = 0;
}

  else{
  if( i+1 <= n){
group2.push_back(i);
group2.push_back(i+1);
}
  else{
group2.push_back(i);
}
flag = 1;
}

}
}

    // if n is even
  else if( n >= 4){

  for(int i = 1; i <= n ; i+=4){
  if( i+3 <= n){

            // add i,i+3 in one group and i+1,i+2 in other group
group1.push_back(i);
group2.push_back(i+1);
group2.push_back(i+2);
group1.push_back(i+3);
}

  else{
group1.push_back(i);
group2.push_back(i+1);
}
}
}

// Print both the groups
print(group1);
print(group2);
}

// Driver program to test above functions
int main()
{
int n = 6;
findGroup(n);
return 0;
}

Output:

Time Complexity: O(N)

Space Complexity: The space complexity is O(N) as we are using extra space to create two groups of maximum size n.
Check out this problem - Pair Sum In Array.

FAQs

What are important math topics required for interview preparation?
Some important maths concepts a programmer should focus on includes Mathematical Induction, Calculus, Probability, and Statistics, Graph Theory, etc.
What is array partitioning?
In a given array of objects, in random order. You want to split the array in half, with the lower half containing objects that match the condition and the top half containing things that do not. This is called the partitioning of an array.

Key Takeaways

Today we solved one mathematical coding question: divide 1 to n into two groups with a minimum sum difference with two approaches. In Approach 1, we solved by half sum calculation, and in the 2nd approach, we used the fact that in a series of four continuous numbers, the sum of extremes equals the sum of the middle elements.

Apart from that, you can use Coding Ninjas Studio to practice a wide range of DSA questions asked in lots of interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.