Horje
Break a number into 3 positive integers (p1, p2, p3) such that p2 > p1 > p3

Given a positive integer N, the task is to divide a number N into 3 positive integers p1, p2, p3 such that p2 > p1 > p3 > 0. The distribution must be as equal as possible. If it is impossible to do so then print -1.

Examples:

Input: N = 6
Output: 2 3 1
Explanation: p1 = 2, p2 = 3 and p3 = 1, so 3 > 2 > 1 > 0.

Input: N = 3
Output: -1
Explanation: It is impossible to distribute N=3 based on the condition p2 > p1 > p3 > 0.

Approach: To solve the problem, follow the below idea:

As we need to distribute N as equally as possible among 3 heights, the problem boils down toward the divisibility of N by 3 based upon the below conditions:

  • If N%3 = 0 then p1 = N/3, p2 = N/3+1 and p3 = N/3-1.
  • If N%3 = 1 then p1 = floor(N/3), p2 = floor(N/3)+2 and p3 = floor(N/3)-1.
  • If N%3 = 2 then p1 = floor(N/3) +1, p2 = floor(N/3)+2 and p3 = floor(N/3)-1.

It is impossible to divide N when N<6 as the minimum value of p1, p2 and p3 can be 2, 3 and 1 respectively whose sum = 2 + 3 + 1 = 6.

Step-by-step algorithm:

  • Check if N < 6, then print -1 as it is impossible to divide N.
  • Else if N >= 6,
    • Calculate x = floor(n/3) and y = n % 3.
    • Print the partitions p1, p2 and p3 according to the value of y.

Below is the implementation of the above approach:

C++

// C++ code for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the partitions
// if possible
void solve(int n)
{
 
    // Edge Case
    if (n < 6) {
        cout << -1 << endl;
    }
 
    // Find n/3 and n%3
    int x = n / 3;
    int y = n % 3;
 
    // Print the parts accordingly
    if (y == 0) {
        cout << x << " " << x + 1 << " " << x - 1 << endl;
    }
    else if (y == 1) {
        cout << x << " " << x + 2 << " " << x - 1 << endl;
    }
    else {
        cout << x + 1 << " " << x + 2 << " " << x - 1
            << endl;
    }
}
 
// Driver Code
 
int main()
{
 
    int N = 6;
    solve(N);
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    static void solve(int n){
        // Edge Case
        if (n < 6) {
            System.out.println("-1");
        }
 
        // Find n/3 and n%3
        int x = n / 3;
        int y = n % 3;
 
        // Print the parts accordingly
        if (y == 0) {
              System.out.println(x + " " + (x+1) + " " + (x-1));
        }
        else if (y == 1) {
              System.out.println(x + " " + (x+2) + " " + (x-1));
        }
        else {
              System.out.println((x+1) + " " + (x+2) + " " + (x-1));
        }
    }
    public static void main(String[] args)
    {
        int N = 6;
          solve(N);
    }
}

Python3

# Function to print the partitions if possible
def solve(n):
    # Edge Case
    if n < 6:
        print(-1)
        return
 
    # Find n/3 and n%3
    x = n // 3
    y = n % 3
 
    # Print the parts accordingly
    if y == 0:
        print(x, x + 1, x - 1)
    elif y == 1:
        print(x, x + 2, x - 1)
    else:
        print(x + 1, x + 2, x - 1)
 
# Driver Code
if __name__ == "__main__":
    N = 6
    solve(N)

C#

using System;
 
class MainClass
{
    // Function to print the partitions
    // if possible
    static void Solve(int n)
    {
        // Edge Case
        if (n < 6)
        {
            Console.WriteLine(-1);
            return;
        }
 
        // Find n/3 and n%3
        int x = n / 3;
        int y = n % 3;
 
        // Print the parts accordingly
        if (y == 0)
        {
            Console.WriteLine(x + " " + (x + 1) + " " + (x - 1));
        }
        else if (y == 1)
        {
            Console.WriteLine(x + " " + (x + 2) + " " + (x - 1));
        }
        else
        {
            Console.WriteLine((x + 1) + " " + (x + 2) + " " + (x - 1));
        }
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int N = 6;
        Solve(N);
    }
}

Javascript

// Function to print the partitions if possible
function solve(n) {
    // Edge Case
    if (n < 6) {
        console.log(-1);
    }
    else {
        // Find n/3 and n%3
        let x = Math.floor(n / 3);
        let y = n % 3;
 
        // Print the parts accordingly
        if (y === 0) {
            console.log(x, x + 1, x - 1);
        }
        else if (y === 1) {
            console.log(x, x + 2, x - 1);
        }
        else {
            console.log(x + 1, x + 2, x - 1);
        }
    }
}
 
// Driver Code
let N = 6;
solve(N);

Output

2 3 1

Time Complexity: O(1)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Geeks Premier League

Related
Charts.js Introduction Charts.js Introduction
Best Software development Courses [2023] Best Software development Courses [2023]
Mongoose Documents vs Models Mongoose Documents vs Models
Create a Cryptocurrency wallet using React-Native Create a Cryptocurrency wallet using React-Native
Create a Weather app using React and Tailwind Create a Weather app using React and Tailwind

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje