Check if a subarray of size K exists whose elements form a number divisible by 3

0 0 6 minutes read

Given an array arr[], of size N and a positive integer K, the task is to find a subarray of size K whose elements can be used to generate a number which is divisible by 3. If no such subarray exists, then print -1.

Examples:

Input: arr[] = {84, 23, 45, 12 56, 82}, K = 3
Output: 12, 56, 82
Explanation:
Number formed by the subarray {12, 56, 82} is 125682, which is divisible by 3.

Input: arr[] = {84, 23, 45, 14 56, 82}, K = 3
Output : -1

Naive Approach: The simplest approach is to generate all possible subarrays of size K from the given array and for each subarray, check if the number formed by that subarray is divisible by 3 or not.

Time Complexity: O(N * K)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, the idea is based on the following observation:

A number is divisible by 3 if and only if the summation of the digits of the number is divisible by 3.

Follow the steps below to solve the problem:

Store the sum of first K elements of the array in a variable, say sum.
Traverse the remaining elements of the array
Using the Sliding window technique, subtract the first element of the subarray from the sum and add the next array element into the subarray.
At each step, check if the sum is divisible by 3 or not.
If found to be true, then print the current K size subarray.
If no such subarray is found, then print -1.

Below is the implementation of the above approach.

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// K size subarray
void findSubArray(vector<int> arr, int k)
{
    pair<int, int> ans;
    int i, sum = 0;
 
    // Check if the first K elements
    // forms a number which is
    // divisible by 3
    for (i = 0; i < k; i++) {
        sum += arr[i];
    }
 
    int found = 0;
    if (sum % 3 == 0) {
        ans = make_pair(0, i - 1);
        found = 1;
    }
 
    // Using Sliding window technique
    for (int j = i; j < arr.size(); j++) {
 
        if (found == 1)
            break;
 
        // Calculate sum of next K
        // size subarray
        sum = sum + arr[j] - arr[j - k];
 
        // Check if sum is divisible by 3
        if (sum % 3 == 0) {
 
            // Update the indices of
            // the subarray
            ans = make_pair(j - k + 1, j);
            found = 1;
        }
    }
 
    // If no such subarray is found
    if (found == 0)
        ans = make_pair(-1, 0);
 
    if (ans.first == -1) {
        cout << -1;
    }
    else {
        // Print the subarray
        for (i = ans.first; i <= ans.second;
             i++) {
            cout << arr[i] << " ";
        }
    }
}
 
// Driver's code
int main()
{
    // Given array and K
    vector<int> arr = { 84, 23, 45,
                        12, 56, 82 };
    int K = 3;
 
    // Function Call
    findSubArray(arr, K);
 
    return 0;
}

Java

// Java implementation of the above approach
import java.util.*;
import java.awt.Point;
 
class GFG{
     
// Function to find the 
// K size subarray 
public static void findSubArray(Vector<Integer> arr,
                                int k) 
{ 
    Point ans = new Point(0, 0);
    int i, sum = 0; 
   
    // Check if the first K elements 
    // forms a number which is 
    // divisible by 3 
    for(i = 0; i < k; i++) 
    { 
        sum += arr.get(i); 
    } 
   
    int found = 0; 
    if (sum % 3 == 0)
    { 
        ans = new Point(0, i - 1); 
        found = 1; 
    } 
   
    // Using Sliding window technique 
    for(int j = i; j < arr.size(); j++)
    { 
        if (found == 1) 
            break; 
   
        // Calculate sum of next K 
        // size subarray 
        sum = sum + arr.get(j) - arr.get(j - k); 
   
        // Check if sum is divisible by 3 
        if (sum % 3 == 0) 
        { 
             
            // Update the indices of 
            // the subarray 
            ans = new Point(j - k + 1, j); 
            found = 1; 
        } 
    } 
   
    // If no such subarray is found 
    if (found == 0) 
        ans = new Point(-1, 0); 
   
    if (ans.x == -1)
    { 
        System.out.print(-1);
    } 
    else
    {
         
        // Print the subarray 
        for(i = ans.x; i <= ans.y; i++)
        { 
            System.out.print(arr.get(i) + " ");
        } 
    } 
} 
 
// Driver code 
public static void main(String[] args)
{
     
    // Given array and K 
    Vector<Integer> arr = new Vector<Integer>();
    arr.add(84);
    arr.add(23);
    arr.add(45);
    arr.add(12);
    arr.add(56);
    arr.add(82);
     
    int K = 3; 
   
    // Function call 
    findSubArray(arr, K); 
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 implementation of the 
# above approach
 
# Function to find the
# K size subarray
def findSubArray(arr, k):
     
    ans = [(0, 0)]
    sm = 0
    i = 0
     
    found = 0
     
    # Check if the first K elements
    # forms a number which is
    # divisible by 3
    while (i < k):
        sm += arr[i]
        i += 1
 
    if (sm % 3 == 0):
        ans = [(0, i - 1)]
        found = 1
 
    # Using Sliding window technique
    for j in range(i, len(arr), 1):
        if (found == 1):
            break
 
        # Calculate sum of next K
        # size subarray
        sm = sm + arr[j] - arr[j - k]
 
        # Check if sum is divisible by 3
        if (sm % 3 == 0):
             
            # Update the indices of
            # the subarray
            ans = [(j - k + 1, j)]
            found = 1
 
    # If no such subarray is found
    if (found == 0):
        ans = [(-1, 0)]
 
    if (ans[0][0] == -1):
        print(-1)
    else:
         
        # Print the subarray
        for i in range(ans[0][0],  
                       ans[0][1] + 1, 1):
            print(arr[i], end = " ")
 
# Driver code
if __name__ == '__main__':
     
    # Given array and K
    arr = [ 84, 23, 45, 12, 56, 82 ]
    K = 3
 
    # Function call
    findSubArray(arr, K)
 
# This code is contributed by SURENDRA_GANGWAR

C#

// C# implementation of 
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
class Point
{ 
  public int x, y; 
  public Point(int first, 
               int second)  
  { 
    this.x = first; 
    this.y = second; 
  }    
} 
 
// Function to find the 
// K size subarray 
public static void findSubArray(List<int> arr,
                                int k) 
{ 
  Point ans = new Point(0, 0);
  int i, sum = 0; 
 
  // Check if the first K elements 
  // forms a number which is 
  // divisible by 3 
  for(i = 0; i < k; i++) 
  { 
    sum += arr[i]; 
  } 
 
  int found = 0; 
  if (sum % 3 == 0)
  { 
    ans = new Point(0, i - 1); 
    found = 1; 
  } 
 
  // Using Sliding window technique 
  for(int j = i; j < arr.Count; j++)
  { 
    if (found == 1) 
      break; 
 
    // Calculate sum of next K 
    // size subarray 
    sum = sum + arr[j] - 
          arr[j - k]; 
 
    // Check if sum is 
    // divisible by 3 
    if (sum % 3 == 0) 
    { 
      // Update the indices of 
      // the subarray 
      ans = new Point(j - k + 1, j); 
      found = 1; 
    } 
  } 
 
  // If no such subarray is found 
  if (found == 0) 
    ans = new Point(-1, 0); 
 
  if (ans.x == -1)
  { 
    Console.Write(-1);
  } 
  else
  {
    // Print the subarray 
    for(i = ans.x; i <= ans.y; i++)
    { 
      Console.Write(arr[i] + " ");
    } 
  } 
} 
 
// Driver code 
public static void Main(String[] args)
{
  // Given array and K 
  List<int> arr = new List<int>();
  arr.Add(84);
  arr.Add(23);
  arr.Add(45);
  arr.Add(12);
  arr.Add(56);
  arr.Add(82);
 
  int K = 3; 
 
  // Function call 
  findSubArray(arr, K); 
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Function to find the
// K size subarray
function findSubArray(arr, k)
{
    var ans = [];
    var i, sum = 0;
 
    // Check if the first K elements
    // forms a number which is
    // divisible by 3
    for(i = 0; i < k; i++) 
    {
        sum += arr[i];
    }
 
    var found = 0;
    if (sum % 3 == 0) 
    {
        ans = [0, i - 1];
        found = 1;
    }
 
    // Using Sliding window technique
    for(var j = i; j < arr.length; j++) 
    {
        if (found == 1)
            break;
 
        // Calculate sum of next K
        // size subarray
        sum = sum + arr[j] - arr[j - k];
 
        // Check if sum is divisible by 3
        if (sum % 3 == 0) 
        {
             
            // Update the indices of
            // the subarray
            ans = [j - k + 1, j];
            found = 1;
        }
    }
 
    // If no such subarray is found
    if (found == 0)
        ans = [-1, 0];
 
    if (ans.first == -1) 
    {
        cout << -1;
    }
    else
    {
         
        // Print the subarray
        for(i = ans[0]; i <= ans[1]; i++)
        {
            document.write( arr[i] + " ");
        }
    }
}
 
// Driver code
 
// Given array and K
var arr = [ 84, 23, 45, 12, 56, 82 ];
var K = 3;
 
// Function Call
findSubArray(arr, K);
 
// This code is contributed by importantly
 
</script>

Output:

12 56 82

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

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 zambiatek!