|
Given A, the number of “1” strings, B number of “10” strings, and C number of “0” strings. The task is to count the maximum inversion count by concatenating these strings
Note: Inversion count is defined as the number of pairs (i, j) such that 0 ≤ i < j ≤ N-1 and S[i] = ‘1’ and S[j] = ‘0’.
Examples:
Input: A = 2, B = 1, C = 0
Output: 3
Explanation: Optimal string = “1110”, hence total number of inversions is 3.
Input: A = 0, B = 0, C = 1
Output: 0
Explanation: Only possible string = “0”, hence total number of inversions is 0.
Approach: This can be solved with the following idea:
It is always optimal to include A and B strings in our answer. Try to form maximum strings from A and B, Increase the inversion by concatinating C at last. As it always contains 0 in it’s string.
Below are the steps involved:
- Initialize a integer ans = 0.
- Form A * (B + C), add it to ans.
- Then form B and C, by B * C add it to ans.
- Try forming the ones with B to increase inversion.
- Return ans.
Below is the implementation of the code:
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int maxInversion(int A, int B, int C)
{
long long ans = A * 1LL * (B + C);
ans += (B * 1LL * C);
ans += (B * 1LL * (B + 1) / 2);
return ans;
}
int main()
{
int A = 2;
int B = 1;
int C = 0;
cout << maxInversion(A, B, C);
return 0;
}
|
Java
public class Main {
public static void main(String[] args) {
int A = 2;
int B = 1;
int C = 0;
System.out.println(maxInversion(A, B, C));
}
public static long maxInversion(int A, int B, int C) {
long ans = A * (long) (B + C);
ans += (B * (long) C);
ans += (B * (long) (B + 1) / 2);
return ans;
}
}
|
Python3
def max_inversion(A, B, C):
ans = A * (B + C)
ans += B * C
ans += B * (B + 1) // 2
return ans
if __name__ == "__main__":
A = 2
B = 1
C = 0
print(max_inversion(A, B, C))
|
C#
using System;
class Program
{
static long MaxInversion(int A, int B, int C)
{
long ans = A * 1L * (B + C);
ans += B * 1L * C;
ans += B * 1L * (B + 1) / 2;
return ans;
}
static void Main()
{
int A = 2;
int B = 1;
int C = 0;
Console.WriteLine(MaxInversion(A, B, C));
}
}
|
Javascript
function GFG(A, B, C) {
let ans = A * (B + C);
ans += B * C;
ans += (B * (B + 1)) / 2;
return ans;
}
function main() {
const A = 2;
const B = 1;
const C = 0;
console.log(GFG(A, B, C));
}
main();
|
Time Complexity: O(1)
Auxiliary Space: O(1)
|
