Given an array arr[] of N integers, the task is to find the smallest subarray brr[] of size at least 2 such that by performing repeating operation on the array brr[] gives the original array arr[]. Print “-1” if it is not possible to find such a subarray.
A repeating operation on an array is to append all the current element of the array to the same array again.
For Example, if an array arr[] = {1, 2} then on repeating operation array becomes {1, 2, 1, 2}.
Examples:
Input: arr[] = {1, 2, 3, 3, 1, 2, 3, 3}
Output: {1, 2, 3, 3}
Explanation:
{1, 2, 3, 3} is the smallest subarray which when repeated 2 times gives the original array {1, 2, 3, 3, 1, 2, 3, 3}Input: arr[] = {1, 1, 6, 1, 1, 7}
Output: -1
Explanation:
There doesn’t exist any subarray.
Naive Approach: The idea is to generate all possible subarrays of length at least 2 and check whether repeating those subarrays gives the original array or not.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by observing the fact that the resultant subarray brr[] must start from the 1st index of the original array to generate arr[] on repeat. Therefore, generate only those subarrays which start from the 1st index and have a length of at least 2 and check whether repeating those subarrays gives the original array or not. Below are the steps:
- Create an auxiliary array brr[] and insert the first two elements of the original array into it as the resulting array must be of at least two in size.
- Traverse over the possible length of subarray [2, N/2 + 1] and check if the array brr[] of length i on repeating gives the original array arr[] or not.
- If yes then print this subarray and break the loop.
- Otherwise, insert the current element into the subarray and check again.
- Repeat the above steps until all the subarrays are checked.
- Print “-1” if the array brr[] is not found.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> #include <vector> using namespace std; // Function to print the array void printArray(vector<int>& brr) { for (auto& it : brr) { cout << it << ' '; } } // Function to find the smallest subarray void RepeatingSubarray(int arr[], int N) { // Corner Case if (N < 2) { cout << "-1"; } // Initialize the auxiliary subarray vector<int> brr; // Push the first 2 elements into // the subarray brr[] brr.push_back(arr[0]); brr.push_back(arr[1]); // Iterate over the length of // subarray for (int i = 2; i < N / 2 + 1; i++) { // If array can be divided into // subarray of i equal length if (N % i == 0) { bool a = false; int n = brr.size(); int j = i; // Check if on repeating the // current subarray gives the // original array or not while (j < N) { int K = j % i; if (arr[j] == brr[K]) { j++; } else { a = true; break; } } // Subarray found if (!a && j == N) { printArray(brr); return; } } // Add current element into // subarray brr.push_back(arr[i]); } // No subarray found cout << "-1"; return; } // Driver Code int main() { int arr[] = { 1, 2, 2, 1, 2, 2, 1, 2, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call RepeatingSubarray(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to print the array static void printArray(Vector<Integer> brr) { for(int it : brr) { System.out.print(it + " "); } } // Function to find the smallest subarray static void RepeatingSubarray(int arr[], int N) { // Corner Case if (N < 2) { System.out.print("-1"); } // Initialize the auxiliary subarray Vector<Integer> brr = new Vector<Integer>(); // Push the first 2 elements into // the subarray brr[] brr.add(arr[0]); brr.add(arr[1]); // Iterate over the length of // subarray for(int i = 2; i < N / 2 + 1; i++) { // If array can be divided into // subarray of i equal length if (N % i == 0) { boolean a = false; int n = brr.size(); int j = i; // Check if on repeating the // current subarray gives the // original array or not while (j < N) { int K = j % i; if (arr[j] == brr.get(K)) { j++; } else { a = true; break; } } // Subarray found if (!a && j == N) { printArray(brr); return; } } // Add current element into // subarray brr.add(arr[i]); } // No subarray found System.out.print("-1"); return; } // Driver Code public static void main(String[] args) { int arr[] = { 1, 2, 2, 1, 2, 2, 1, 2, 2 }; int N = arr.length; // Function call RepeatingSubarray(arr, N); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach # Function to print the array def printArray(brr): for it in brr: print(it, end = ' ') # Function to find the smallest subarray def RepeatingSubarray(arr, N): # Corner Case if (N < 2): print("-1") # Initialize the auxiliary subarray brr = [] # Push the first 2 elements into # the subarray brr[] brr.append(arr[0]) brr.append(arr[1]) # Iterate over the length of # subarray for i in range(2, N // 2 + 1): # If array can be divided into # subarray of i equal length if (N % i == 0): a = False n = len(brr) j = i # Check if on repeating the # current subarray gives the # original array or not while (j < N): K = j % i if (arr[j] == brr[K]): j += 1 else: a = True break # Subarray found if (not a and j == N): printArray(brr) return # Add current element into # subarray brr.append(arr[i]) # No subarray found print("-1") return # Driver Code if __name__ =="__main__": arr = [ 1, 2, 2, 1, 2, 2, 1, 2, 2 ] N = len(arr) # Function call RepeatingSubarray(arr, N) # This code is contributed by chitranayal |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to print the array static void printArray(List<int> brr) { foreach(int it in brr) { Console.Write(it + " "); } } // Function to find the smallest subarray static void RepeatingSubarray(int []arr, int N) { // Corner Case if (N < 2) { Console.Write("-1"); } // Initialize the auxiliary subarray List<int> brr = new List<int>(); // Push the first 2 elements into // the subarray brr[] brr.Add(arr[0]); brr.Add(arr[1]); // Iterate over the length of // subarray for(int i = 2; i < N / 2 + 1; i++) { // If array can be divided into // subarray of i equal length if (N % i == 0) { bool a = false; int n = brr.Count; int j = i; // Check if on repeating the // current subarray gives the // original array or not while (j < N) { int K = j % i; if (arr[j] == brr[K]) { j++; } else { a = true; break; } } // Subarray found if (!a && j == N) { printArray(brr); return; } } // Add current element into // subarray brr.Add(arr[i]); } // No subarray found Console.Write("-1"); return; } // Driver Code public static void Main(String[] args) { int []arr = {1, 2, 2, 1, 2, 2, 1, 2, 2}; int N = arr.Length; // Function call RepeatingSubarray(arr, N); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to print the array function printArray(brr) { for (let it of brr) { document.write(it + ' '); } } // Function to find the smallest subarray function RepeatingSubarray(arr, N) { // Corner Case if (N < 2) { document.write("-1"); } // Initialize the auxiliary subarray let brr = []; // Push the first 2 elements into // the subarray brr[] brr.push(arr[0]); brr.push(arr[1]); // Iterate over the length of // subarray for (let i = 2; i < Math.floor(N / 2) + 1; i++) { // If array can be divided into // subarray of i equal length if (N % i == 0) { let a = false; let n = brr.length; let j = i; // Check if on repeating the // current subarray gives the // original array or not while (j < N) { let K = j % i; if (arr[j] == brr[K]) { j++; } else { a = true; break; } } // Subarray found if (!a && j == N) { printArray(brr); return; } } // Add current element into // subarray brr.push(arr[i]); } // No subarray found document.write("-1"); return; } // Driver Code let arr = [ 1, 2, 2, 1, 2, 2, 1, 2, 2 ]; let N = arr.length; // Function call RepeatingSubarray(arr, N); // This code is contributed by Surbhi Tyagi. </script> |
Output:
1 2 2
Time Complexity: O(N2)
Auxiliary Space: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
