|
You are given an array A[ ] of N integers. In one operation
- pick any subarray A[l….r]
- let x be the least positive integer present in this subarray
- If x exists then update A[i] = A[i] % x (l ≤ i ≤ r)
You can perform the above operation at most 10 times. Find a way to make every array element the same after completing all the operations.
Examples:
Input: N = 6, A[] = {2, 2, 2, 3, 3, 3}
Output:
1 3
4 6
Explanation:
After the first operation A = {0, 0, 0, 3, 3, 3}
After the 2nd operation A = {0, 0, 0, 0, 0, 0}
Input: N = 2, A[] = {1, 6}
Output:
1 2
Explanation: Only one operation is efficient.
Approach: Follow the below idea to solve the problem.
To make all array elements equal is always optimal to choose 1 to N subarray, as atmost 10 operation are allowed.
Below are the steps involved:
- Initialize a 2D vector ans of size 10.
- Iterate upto 10 times:
- Return ans vector.
Below is the implementation of the code:
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
vector<vector<int> > solve(int N, vector<int> A)
{
vector<vector<int> > ans(10);
for (int i = 0; i < 10; i++) {
ans[i] = { 1, N };
}
return ans;
}
int main()
{
int N = 6;
vector<int> A = { 2, 2, 2, 3, 3, 3 };
vector<vector<int> > arr = solve(N, A);
for (auto a : arr) {
cout << a[0] << " " << a[1] << endl;
}
return 0;
}
|
Java
import java.util.*;
public class GFG {
static List<List<Integer> > solve(int N,
List<Integer> A)
{
List<List<Integer> > ans = new ArrayList<>(10);
for (int i = 0; i < 10; i++) {
ans.add(List.of(1, N));
}
return ans;
}
public static void main(String[] args)
{
int N = 6;
List<Integer> A = List.of(2, 2, 2, 3, 3, 3);
List<List<Integer> > arr = solve(N, A);
for (List<Integer> a : arr) {
System.out.println(a.get(0) + " " + a.get(1));
}
}
}
|
Python3
def GFG(N, A):
ans = [[1, N] for _ in range(10)]
return ans
def main():
N = 6
A = [2, 2, 2, 3, 3, 3]
arr = GFG(N, A)
for a in arr:
print(f"{a[0]} {a[1]}")
if __name__ == "__main__":
main()
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static List<List<int>> Solve(int N, List<int> A)
{
List<List<int>> ans = new List<List<int>>(10);
for (int i = 0; i < 10; i++)
{
ans.Add(new List<int> { 1, N });
}
return ans;
}
public static void Main(string[] args)
{
int N = 6;
List<int> A = new List<int> { 2, 2, 2, 3, 3, 3 };
List<List<int>> arr = Solve(N, A);
foreach (var a in arr)
{
Console.WriteLine($"{a[0]} {a[1]}");
}
}
}
|
Javascript
function GFG(N, A) {
let ans = Array.from({ length: 10 }, () => []);
for (let i = 0; i < 10; i++) {
ans[i] = [1, N];
}
return ans;
}
function main() {
let N = 6;
let A = [2, 2, 2, 3, 3, 3];
let arr = GFG(N, A);
for (let a of arr) {
console.log(a[0] + " " + a[1]);
}
}
main();
|
Output
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
Complexity Analysis:
Time Complexity: O(1)
Auxiliary Space: O(1)
|
