Ways to arrange N balls of K colors with no adjacent same colors
Given infinite balls of K distinct colors. Count the number of ways to arrange N balls in a line such that no two adjacent balls are of same color. Since the answer may be very large, output the result MOD 1000000007.
Examples:
Input: N = 2, K = 2
Output: 2
Explanation: We will denote the colors by ‘R’ and ‘G’. There are two possible ways: “RG” and “GR”.Input: N = 1, K = 100
Output: 100
Explanation: As there is only 1 box and 100 different colored balls, we can put any of the 100 balls in the box.Input: N = 3, K = 2
Output: 2
Explanation: There are only two possible ways: “RGR” and “GRG”.
Approach: To solve the problem, follow the below idea:
If the number of balls to be arranged is 1, then the number of ways = K as we can choose one ball from any of the K different colors. For N > 1, we have K choices for the first ball and for every subsequent ball, we can choose from any of the K colors except the one which was used in the previous ball. So, the total number of ways are: N * ((K – 1) ^ (N – 1)). This can be easily calculated using Binary Exponentiation.
Below is the implementation of the approach:
#include <iostream>
using namespace std;
class BinaryExponentiation {
public:
static const long long MOD = 1000000007;
// Binary Exponentiation
static long long power(long long base, long long expo)
{
long long ans = 1;
while (expo > 0) {
if ((expo & 1) == 1)
ans = (ans * base) % MOD;
base = (base * base) % MOD;
expo >>= 1;
}
return ans;
}
static void main()
{
int N = 5, K = 3;
// Calculate the result using the formula
// (K)*(K-1)^(N-1)
long long ways = (K * power(K - 1, N - 1)) % MOD;
cout << ways << endl;
}
};
int main()
{
BinaryExponentiation::main();
return 0;
}
import java.util.Scanner;
public class BinaryExponentiation {
static long MOD = 1000000007;
// Binary Exponentiation
static long power(long base, long expo)
{
long ans = 1;
while (expo > 0) {
if ((expo & 1) == 1)
ans = (ans * base) % MOD;
base = (base * base) % MOD;
expo >>= 1;
}
return ans;
}
public static void main(String[] args)
{
int N = 5, K = 3;
// Calculate the result using the formula
// (K)*(K-1)^(N-1)
long ways = (K * power(K - 1, N - 1)) % MOD;
System.out.println(ways);
}
}
// This code is contributed by rambabuguphka
# Define the modulus value
MOD = 1000000007
# Binary Exponentiation function to calculate (base^expo) % MOD
def power(base, expo):
ans = 1
# Iterate through each bit of the exponent
while expo > 0:
# If the current bit is set, multiply ans by base
if expo & 1:
ans = (ans * base) % MOD
# Update base to base^2 % MOD
base = (base * base) % MOD
# Shift the exponent right by 1 (divide by 2)
expo >>= 1
return ans
# Main function
def main():
# Given values for N and K
N = 5
K = 3
# Calculate the result using the formula (K)*(K-1)^(N-1)
# and taking modulo MOD
ways = (K * power(K - 1, N - 1)) % MOD
# Print the calculated result
print(ways)
# Call the main function to execute the program
main()
using System;
class Program
{
// Define the modulus constant
const int MOD = 1000000007;
// Binary Exponentiation
static long Power(long baseValue, long expo)
{
long ans = 1;
while (expo > 0)
{
// If expo is odd, multiply ans by baseValue
if ((expo & 1) == 1)
ans = (ans * baseValue) % MOD;
// Square the baseValue
baseValue = (baseValue * baseValue) % MOD;
// Right shift expo by 1
expo >>= 1;
}
return ans;
}
static void Main()
{
int N = 5, K = 3;
// Calculate the result using the formula (K)*(K-1)^(N-1)
long ways = (K * Power(K - 1, N - 1)) % MOD;
Console.WriteLine(ways);
}
}
const MOD = 1000000007;
// Binary Exponentiation
function power(base, expo) {
let ans = 1;
while (expo > 0) {
if (expo & 1)
ans = (ans * base) % MOD;
base = (base * base) % MOD;
expo >>= 1;
}
return ans;
}
function main() {
let N = 5, K = 3;
// Calculate the result using the formula
// (K)*(K-1)^(N-1)
let ways = (K * power(K - 1, N - 1)) % MOD;
console.log(ways);
}
main();
<?php
class BinaryExponentiation {
const MOD = 1000000007;
// Binary Exponentiation
static function power($base, $expo)
{
$ans = 1;
while ($expo > 0) {
if (($expo & 1) == 1)
$ans = ($ans * $base) % self::MOD;
$base = ($base * $base) % self::MOD;
$expo >>= 1;
}
return $ans;
}
public static function main()
{
$N = 5;
$K = 3;
// Calculate the result using the formula
// (K)*(K-1)^(N-1)
$ways = ($K * self::power($K - 1, $N - 1)) % self::MOD;
echo $ways . "\n";
}
}
// Call main function
BinaryExponentiation::main();
?>
Output
48
Time Complexity: O(log2N), where N is the number of balls to arrange.
Auxiliary Space: O(1)
Contact Us